AtCoder Beginner Contest 271（ABC271）

atcoder.jp

過去最高パフォだったっぽい
Bondo416さんの京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)での成績：237位
パフォーマンス：2201相当
レーティング：1452→1553 (+101) :)#AtCoder #京セラプログラミングコンテスト2022(ABC271) https://t.co/RKnLgR9l0X

— ボンド@競プロ (@bond_cmprog) October 1, 2022

A - 484558

$ \frac{N}{16} $ と $ N \% 16 $ をそれぞれ16進数で出力

提出コード

void solve() {
    int N;
    cin >> N;
    string ans = "";
    if (N / 16 >= 10) ans += char('A' + N / 16 - 10);
    else ans += char('0' + N / 16);
    N %= 16;
    if (N >= 10) ans += char('A' + N - 10);
    else ans += char('0' + N);
    cout << ans << endl;
}

B - Maintain Multiple Sequences

二次元vectorで受け取った入力をクエリごとに答える

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<vector<int>> a(N);
    REP(i, N) {
        int l;
        cin >> l;
        a[i].resize(l);
        REP(j, l) cin >> a[i][j];
    }
    while (Q--) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        cout << a[s][t] << endl;
    }
}

C - Manga

multisetでシミュレートを行う
基本的には後ろの2つを削除していくが、同じ巻が重複している場合はそれらも削除していいので予め使うか、適当な大きい定数に置き換えておく

提出コード

void solve() {
    int N;
    cin >> N;
    vector<ll> a(N);
    multiset<ll> mst;
    REP(i, N) {
        cin >> a[i];
        if (mst.count(a[i])) mst.insert(LINF);
        else mst.insert(a[i]);
    }
    int cur = 0;
    while (!mst.empty()) {
        auto x = *mst.begin();
        if (x == cur + 1) {
            mst.erase(mst.begin());
            cur++;
        }
        else {
            if (mst.size() < 2) break;
            mst.erase(prev(mst.end()));
            mst.erase(prev(mst.end()));
            cur++;
        }
    }
    cout << cur << endl;
}

D - Flip and Adjust

$ dp[i][j] := i $ 枚目のカードまで見たときに、その総和が $ j $ にできるかどうか、で部分和DPを解く
DPを更新する際に、$ prev[i][j] = (pre_i, pre_j) $ としてDPテーブルのどこから遷移してきたかの情報を持っておいて最後に復元を行う

提出コード

void solve() {
    int N, S;
    cin >> N >> S;
    vector<int> a(N), b(N);
    REP(i, N) cin >> a[i] >> b[i];
    vector<vector<int>> dp(N + 1, vector<int>(S + 10, 0));
    vector<vector<P>> prev(N + 1, vector<P>(S + 10, {-1, -1}));
    dp[0][0] = 1;
    REP(i, N) {
        REP(j, S + 1) if (dp[i][j]) {
            if (j + a[i] <= S) {
                dp[i + 1][j + a[i]] = 1;
                prev[i + 1][j + a[i]] = {i, j};
            }
            if (j + b[i] <= S) {
                dp[i + 1][j + b[i]] = 1;
                prev[i + 1][j + b[i]] = {i, j};
            }
        }
    }
    if (dp[N][S] == 0) {
        cout << "No" << endl;
        return;
    }
    P cur = {N, S};
    string ans = "";
    while (1) {
        P nxt = prev[cur.first][cur.second];
        if (nxt == make_pair(-1, -1)) break;
        if (cur.second - nxt.second == a[nxt.first]) {
            ans += 'H';
        }
        else ans += 'T';
        cur = nxt;
    }
    reverse(ALL(ans));
    cout << "Yes" << endl;
    cout << ans << endl;
}

E - Subsequence Path

ダイクストラっぽいDPで頂点 $ 1 $ から各頂点への最小距離を求める
priority_queueの代わりに $ E $ の昇順に辺を見ていき、各頂点への最小距離を更新していく

提出コード

void solve() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> A(M), B(M), C(M);
    REP(i, M) {
        cin >> A[i] >> B[i] >> C[i];
        --A[i], --B[i];
    }
    vector<int> E(K);
    REP(i, K) {
        cin >> E[i];
        --E[i];
    }
    vector<ll> dist(N, LINF);
    dist[0] = 0;
    REP(i, K) {
        if (dist[A[E[i]]] == LINF) continue;
        chmin(dist[B[E[i]]], dist[A[E[i]]] + C[E[i]]);
    }
    cout << (dist[N - 1] == LINF ? -1 : dist[N - 1]) << endl;
}

F - XOR on Grid Path

こどふぉにほぼ同じものがあった

codeforces.com

半分全列挙をする
スタートから $v1[i][j] := i $ 行 $j$ 列目にいるときのxorの値を列挙したもの
同様にゴールからの逆算で $v2[i][j] := i$ 行 $j$ 列目にいるときのxorの値を列挙したものとしてxorを値を列挙しておく
その後 $i+j = \frac{2n - 2}{2}$ の地点での $v1[i][j]$ の値を $x$ とすると $v2[i][j]$ に $x$ が存在すれば最終的なxorは $ 0 $ となる
そのため $v2[i][j]$ にこの値がいくつ存在するかを二分探索すればいい

提出コード

void solve() {
    int n;
    cin >> n;
    vector a(n, vector<ll>(n));
    REP(i, n) REP(j, n) cin >> a[i][j];
    vector v1(n, vector(n, vector<ll>()));
    auto v2 = v1;
    int l = 2 * n - 2;
    {
        v1[0][0].emplace_back(a[0][0]);
        int n2 = l / 2;
        REP(i, n) {
            REP(j, n) {
                if (i == 0 and j == 0) continue;
                if (i + j > n2) continue;
                if (i > 0) {
                    for (auto x : v1[i - 1][j])
                        v1[i][j].emplace_back(x ^ a[i][j]);
                }
                if (j > 0) {
                    for (auto x : v1[i][j - 1])
                        v1[i][j].emplace_back(x ^ a[i][j]);
                }
            }
        }
    }
    {
        v2[n - 1][n - 1].emplace_back(a[n - 1][n - 1]);
        int n2 = l - l / 2;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == n - 1 and j == n - 1) continue;
                if (n - 1 + n - 1 - (i + j) > n2) continue;
                if (i + 1 < n) {
                    for (auto x : v2[i + 1][j])
                        v2[i][j].emplace_back(x ^ a[i][j]);
                }
                if (j + 1 < n) {
                    for (auto x : v2[i][j + 1])
                        v2[i][j].emplace_back(x ^ a[i][j]);
                }
            }
        }
    }
    ll ans = 0;
    REP(i, n) {
        REP(j, n) {
            if (i + j == l / 2) {
                sort(v1[i][j].begin(), v1[i][j].end());
                sort(v2[i][j].begin(), v2[i][j].end());
                for (auto x : v1[i][j]) {
                    x ^= a[i][j];
                    ans += upper_bound(v2[i][j].begin(), v2[i][j].end(), x)
                           - lower_bound(v2[i][j].begin(), v2[i][j].end(), x);
                }
            }
        }
    }
    cout << ans << endl;
}