接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

AtCoderBeginnerContest AtCoderBeginnerContest186 ABC ABC186

atcoder.jp

A - Brick

$ \lceil \frac{N}{W} \rceil $ を出力
提出コード

void solve(){
    int N, W;
    cin >> N >> W;
    cout << N / W << endl;
}

B - Blocks on Grid

一番小さい値に合わせればいいのでその差分の和が答え
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0));
    int mi = INF;
    REP(i,H) REP(j,W){
        cin >> A[i][j];
        chmin(mi, A[i][j]);
    }
    int ans = 0;
    REP(i,H) REP(j,W) ans += A[i][j] - mi;
    cout << ans << endl;
}

C - Unlucky 7

正の整数を10進法と8進法に変換するのは愚直にやっても間に合うので全探索すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i=1;i<=N;i++){
        int tmp = i;
        bool ok = false;
        while(tmp > 0){
            int num = tmp % 10;
            if(num == 7) ok = true;
            tmp /= 10;
        }
        tmp = i;
        while(tmp > 0){
            int num = tmp % 8;
            if(num == 7) ok = true;
            tmp /= 8;
        }
        if(ok) ans++;
    }
    cout << N - ans << endl;
}

D - Sum of difference

絶対値が扱いにくいので降順ソートをすると$ A_i - A_j \geq 0 $となって扱いやすい
$ A_i $を固定すると
$ A_i - A_{i + 1} + A_i - A_{i+2} + ... + A_i - A_{N - 1} = A_i * (N - i - 1) - \sum _{j = i + 1} ^{N - 1} A_j $
となるので、予め累積和を求めておけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    vector<ll> cum(N+1);
    for(int i=N-1;i>=0;i--) cum[i] = cum[i+1] + A[i];
    ll ans = 0;
    REP(i,N){
        ans += A[i] * (N - i -1) - cum[i+1];
    }
    cout << ans << endl;
}

E - Throne

何回移動したかを$ x $とすると$ S + Kx \equiv 0 \pmod N $を満たす$ x $を求められればいい
これは$ K $の逆元が存在すれば求めることが出来る
まず、$ g = gcd(N, S, K) $とし、$N = N / g, S = S / g, K = K / g $と置き換える
$gcd(N, K) \neq 1 $のとき、$ K $の逆元が存在しないので-1
それ以外の場合逆元を求めれば良く、ACLのinv_modを使えばこれを求められる
また、$ y = Kx $とし、$ S + Kx \equiv 0 \pmod N $を

  • $ y \equiv 0 \pmod K $
  • $ y \equiv -S \pmod N $

とすれば、中国剰余定理で解が存在するかどうかと、存在すればその解を求めることが出来る
提出コード

void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    ll g = gcd(gcd(N, S), K);
    N /= g, S /= g, K /= g;
    if(gcd(N, K) != 1){
        cout << -1 << endl;
        return;
    }
    cout << (N - S + N) % N * inv_mod(K, N) % N << endl;
}

提出コード（中国剰余定理）

void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    auto [y, z] = crt({0, N-S}, {K, N});
    if(y == 0) cout << -1 << endl;
    else cout << y / K << endl;
}

F - Rook on Grid

移動方法を考えると、最初に右に移動し、次に下に移動する、もしくは最初に下に移動し、次に右に移動するの2パターン考えられる
右・下の移動を考えると、各列において最初にぶつかる障害物までの位置を求めることで移動可能なマスを数えられ、下・右の場合も同様に求められる
$ w_i $を$ i $列目に一番上にある障害物の位置、$ h_i $を$ i $行目の一番左にある障害物の位置とすると
それぞれの移動可能なマスは$ \sum _{i = 0} ^{h_0} w_i + \sum _{i = 0} ^{w_0} h_i $となる
ただし、重複して数えているマスがあるので重複マスを引いて上げる必要がある
上から順に各行を見ていき、各マスがすでに障害物が出現したかどうかをBITなどで管理し、その総和を引いていけばいい
提出コード

void solve(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> h(H, W), w(W, H);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        --x, --y;
        chmin(w[y], x);
        chmin(h[x], y);
    }
    ll ans = 0;
    REP(i,w[0]) ans += h[i];
    REP(i,h[0]) ans += w[i];
    BIT<int> bit(W);
    REP(i,h[0]) bit.add(i,1);
    vector<vector<int>> obj(H+1);
    REP(i,h[0]) obj[w[i]].emplace_back(i);
    REP(i,w[0]){
        for(auto j : obj[i]) bit.add(j, -1);
        ans -= bit.sum(0, h[i]);
    }
    cout << ans << endl;
}