接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 298（ABC298）

AtCoder Beginner Contest 298（ABC298）

AtCoderBeginnerContest AtCoderBeginnerContest298 ABC ABC298

atcoder.jp

A - Job Interview

o があるかどうかとxがあるかどうかをそれぞれ確認する

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    bool ok1 = false;
    bool ok2 = true;
    REP(i, N) {
        if (S[i] == 'o') ok1 |= true;
        if (S[i] == 'x') ok2 = false;
    }
    cout << (ok1 and ok2 ? "Yes" : "No") << endl;
}

B - Coloring Matrix

4回回転させれば元に戻るので全探索する

提出コード

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    auto B = A;
    REP(i, N) REP(j, N) cin >> A[i][j];
    REP(i, N) REP(j, N) cin >> B[i][j];
    REP(_, 4) {
        bool ok = true;
        REP(i, N) REP(j, N) {
            if (A[i][j] == 1 and B[i][j] == 0) ok = false;
        }
        if (ok) {
            cout << "Yes" << endl;
            return;
        }
        auto a = A;
        REP(i, N) REP(j, N) { A[i][j] = a[N - j - 1][i]; }
    }
    cout << "No" << endl;
}

C - Cards Query Problem

箱は重複を許すmultiset、数は重複なしのsetで管理する

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<multiset<int>> hako(202020);
    vector<set<int>> number(202020);
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int i, j;
            cin >> i >> j;
            hako[j].emplace(i);
            number[i].emplace(j);
        }
        else if (q == 2) {
            int i;
            cin >> i;
            for (auto x : hako[i]) {
                cout << x << " ";
            }
            cout << endl;
        }
        else {
            int i;
            cin >> i;
            for (auto x : number[i]) {
                cout << x << " ";
            }
            cout << endl;
        }
    }
}

D - Writing a Numeral

先頭の要素取得と削除が可能なdequeで管理しながら追加、削除で差分計算をしていく
よく考えるとqueueでも良かった

提出コード

void solve() {
    int Q;
    cin >> Q;
    mint sum = 1;
    deque<int> dq;
    dq.push_front(1);
    while (Q--) {
        int q;
        cin >> q;
        if (q == 1) {
            int x;
            cin >> x;
            dq.push_back(x);
            sum = sum * 10 + x;
        }
        else if (q == 2) {
            int d = dq.size();
            int x = dq.front();
            dq.pop_front();
            sum = sum - modpow(mint(10), d - 1) * x;
        }
        else cout << sum << endl;
    }
}

E - Unfair Sugoroku

青木くんと高橋くんそれぞれ独立に考えていいので、以下のDPを求める
$ dp[i][j] := i $ 回目に地点 $ x $ にいる確率
高橋くんが $ i $ 回目に勝つ確率は、高橋くんが$ i $ 回目に地点 $ N $ にいる確率と青木くんが $ i - 1 $ 回目に地点 $ N $ 以外にいる確率との積になるのでその総和を求めればいい

提出コード

void solve() {
    int N, A, B, P, Q;
    cin >> N >> A >> B >> P >> Q;
    vector<vector<mint>> aoki(N + 1, vector<mint>(N + 1, 0));
    aoki[0][B] = 1;
    REP(k, N) {
        REP(i, N) REP(j, 1, Q + 1) {
            int to = (i + j > N ? N : i + j);
            aoki[k + 1][to] += aoki[k][i] / Q;
        }
    }
    vector<vector<mint>> takahashi(N + 1, vector<mint>(N + 1, 0));
    takahashi[0][A] = 1;
    REP(k, N) {
        REP(i, N) REP(j, 1, P + 1) {
            int to = (i + j > N ? N : i + j);
            takahashi[k + 1][to] += takahashi[k][i] / P;
        }
    }
    mint ans = 0;
    REP(i, 1, N + 1) {
        if (takahashi[i][N] == 0) continue;
        mint p = 0;
        REP(j, N) p += aoki[i - 1][j];
        ans += p * takahashi[i][N];
    }
    cout << ans << endl;
}

F - Rook Score

座圧をして平面走査を行う
$ r $ 行目の総和をセグメント木で管理し、その最大値を求める
$ w $ 列目の総和をそれぞれ求めながら重複する$ r $行目の差分計算を行い最大値を更新していく

提出コード

void solve() {
    int N;
    cin >> N;
    Compress<ll> cmp_h;
    vector<ll> h(N), w(N), x(N);
    REP(i, N) {
        cin >> h[i] >> w[i] >> x[i];
        cmp_h.add(h[i]);
    }
    cmp_h.build();
    int sz = cmp_h.size() + 1;
    map<ll, vector<LP>> mpw;
    vector<ll> h_val(sz + 1);
    REP(i, N) {
        mpw[w[i]].emplace_back(cmp_h.get(h[i]), x[i]);
        h_val[cmp_h.get(h[i])] += x[i];
    }
    ll ans = 0;
    segtree<ll, op, e> seg(h_val);
    for (auto [k, v] : mpw) {
        ll sum = 0;
        for (auto [h_idx, x] : v) {
            seg.set(h_idx, seg.get(h_idx) - x);
            sum += x;
        }
        chmax(ans, sum + seg.all_prod());
        for (auto [h_idx, x] : v) {
            seg.set(h_idx, seg.get(h_idx) + x);
        }
    }
    cout << ans << endl;
}