接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 297（ABC297）

AtCoder Beginner Contest 297（ABC297）

AtCoderBeginnerContest AtCoderBeginnerContest297 ABC ABC297

atcoder.jp

A - Double Click

$ T _ {i - 1} - T _ i \leq D $ を満たす最小の $ T _ {i + 1} $ を出力する

提出コード

void solve() {
    int N, D;
    cin >> N >> D;
    vector<int> T(N);
    REP(i, N) cin >> T[i];
    REP(i, N - 1) if (T[i + 1] - T[i] <= D) {
        cout << T[i + 1] << endl;
        return;
    }
    cout << -1 << endl;
}

B - chess960

問題文の条件を満たすがどうかを全探索で確認する

提出コード

void solve() {
    string S;
    cin >> S;
    int N = S.size();
    bool ok1 = false;
    bool ok2 = false;
    REP(x, N) REP(y, x + 1, N) {
        if (S[x] == S[y] and S[x] == 'B' and x % 2 != y % 2) ok1 = true;
    }
    REP(x, N) {
        REP(y, x + 2, N) {
            REP(z, x + 1, y) {
                if (S[x] == S[y] and S[x] == 'R' and S[z] == 'K') {
                    ok2 = true;
                }
            }
        }
    }
    cout << (ok1 and ok2 ? "Yes" : "No") << endl;
}

C - PC on the Table

左端から条件を満たすものに操作を行っていく

提出コード

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    REP(i, H) cin >> S[i];
    REP(i, H) {
        REP(j, W - 1) if (S[i][j] == S[i][j + 1] and S[i][j] == 'T') {
            S[i][j] = 'P';
            S[i][j + 1] = 'C';
        }
    }
    REP(i, H) cout << S[i] << endl;
}

D - Count Subtractions

ユークリッド互除法を行いながらその回数を計算する

提出コード

void solve() {
    ll A, B;
    cin >> A >> B;
    ll ans = 0;
    auto f = [&](auto &&self, ll x, ll y) -> ll {
        if (y) {
            ans += x / y;
            return self(self, y, x % y);
        }
        else {
            return x;
        }
    };
    f(f, A, B);
    cout << ans - 1 << endl;
}

E - 2xN Grid

priority_queue で操作によって得られる金額の最小値の候補を管理する
各操作では現在の最小値に対して $ A _ i $ を足した値を追加していく
このときすでにある値の場合は操作を行わないものとする

提出コード

void solve() {
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    set<ll> st;
    REP(i, N) {
        cin >> A[i];
        st.insert(A[i]);
        pq.emplace(A[i]);
    }
    REP(_, K + 100) {
        if (pq.empty()) break;
        ll mi = pq.top();
        pq.pop();
        REP(i, N) {
            if (st.count(A[i] + mi)) continue;
            st.insert(A[i] + mi);
            pq.emplace(A[i] + mi);
        }
    }
    int k = 0;
    for (auto x : st) {
        k++;
        if (k == K) {
            cout << x << endl;
            break;
        }
    }
}

F - Minimum Bounding Box 2

縦 $ h $ 、横 $ w $ のサイズの長方形領域への $ K $ 個のマスの置き方の個数を求める
個数が求められると、この長方形領域は全部で $ (H - h + 1)(W - w + 1) $ 個あり、そのサイズは $ hw $ なのでその積がスコアとなる
よって長方形領域の選び方を全探索し、その総和を 縦が $ H $ 、横が $ W $ の長方形領域への $ K $ 個のマスの置き方の個数で割ったものが答え
各長方形領域の置き方の個数は包除原理で求めることができる
参考：D - AtCoder社の冬

提出コード

void solve() {
    ll H, W, K;
    cin >> H >> W >> K;
    mint ans = 0;
    bc.init(2020202);
    REP(h, 1, H + 1) REP(w, 1, W + 1) {
        mint sum = 0;
        REP(i, 1 << 4) {
            ll x = h;
            ll y = w;
            if (i >> 0 & 1) x--;
            if (i >> 1 & 1) x--;
            if (i >> 2 & 1) y--;
            if (i >> 3 & 1) y--;
            if (x < 0 or y < 0) continue;
            if (__builtin_popcount(i) & 1) sum -= bc.nCr(x * y, K);
            else sum += bc.nCr(x * y, K);
        }
        sum *= (h * w) * (H - h + 1) * (W - w + 1);
        ans += sum;
    }
    ans /= bc.nCr(H * W, K);
    cout << ans << endl;
}