接着剤の精進日記

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

AtCoder Heuristic Contest 060

AtCoder AHC

atcoder.jp

※ AIに（略）

概要

N=100 頂点のグラフ上に K=10 のアイスクリームショップと 90 本のアイスクリームの木がある。頂点 0 から出発し、木でアイスを収穫してコーンに積み上げ、ショップに納品する。各ショップの在庫は集合（重複なし）で管理され、全ショップの在庫数の合計を最大化したい。木は初期状態ではすべてバニラ（W）だが、ストロベリー（R）に変換できる（不可逆）。最大 T=10000 ステップ。

方針

ビームサーチで各ステップの行動を決定した。

チャンク単位のビームサーチ

T=10000 ステップ全体を一度にビームサーチするのはメモリ的に不可能なので、CHUNK_SIZE（≈30）ステップごとに区切って計画する。各チャンクでビームサーチを実行し、最良パスを確定させて次のチャンクに進む。

状態表現

ビームの各状態は以下を持つ。

  • cur, prev_node: 現在位置と直前の位置（移動制約のため）
  • cone_hash, cone_len: コーンの内容をローリングハッシュと長さで管理
  • is_vanilla[2]: 各木がバニラかストロベリーかを 128bit のビットセットで保持
  • score_delta: そのパスで得た新規納品数
  • convert_count, turns_since_convert: 変換回数とクールダウン管理

評価関数

ビームの選別に使う評価関数は複数の要素の重み付き和で構成した。

要素 重み 説明
新規納品数 W_DELIVERY=40000 確定スコアへの寄与（最重要）
ショップへの距離 W_DIST=170 コーンを持っているとき、最寄りショップへの距離が近いほど高評価
コーンの長さ W_CONE_LEN=60 長い文字列ほど多様性に寄与しやすい（上限6）
新規性ボーナス W_NOVEL=3500 現在のコーンが最寄りショップで未納品ならボーナス
重複ペナルティ W_DUP=500 既に納品済みの文字列を持っている場合のペナルティ
次数ボーナス W_DEGREE=40 分岐の多い頂点を好む
ノイズ EVAL_NOISE=300 探索の多様性を確保するランダムノイズ

新規性チェック

納品時に「その文字列が本当に新しいか」を正確に判定する必要がある。グローバルの FlatHashSet（ショップごとの在庫管理）に加えて、ビームの親チェーンを遡って同じチャンク内で先に納品された文字列との重複も検出するようにした。

適応的ビーム幅

各チャンクの実行時間を計測し、時間に余裕があればビーム幅を広げ、時間が足りなければ狭める。これにより制限時間（2秒）をギリギリまで使い切る。

木の変換戦略

全 90 本の木のうち半分（45本）をストロベリーに変換する。変換はクールダウン（T / 変換上限 ≈ 222ステップ間隔）を設けて均等に分散させた。これにより序盤はバニラ系の文字列を集め、徐々にストロベリー混じりの文字列も生成できるようになる。

高速化

  • FlatHashSet: オープンアドレッシングの自作ハッシュセットで O(1) の挿入・検索
  • ローリングハッシュ: コーン文字列の比較をハッシュ値の比較に置き換え
  • CSR 隣接リスト: キャッシュ効率の良いグラフ表現
  • BFS 前計算: 全点間最短距離と各頂点から最寄りショップへの距離を事前計算
  • 出力バッファリング: 200KB バッファに書き溜めて最後に一括出力

ハイパーパラメータ調整

Optuna で評価関数の重みやビーム幅を探索した。50 試行の TPE サンプラー + MedianPruner で以下の値に落ち着いた。

パラメータ 値
BEAM_WIDTH 1700
CHUNK_SIZE 30
W_DELIVERY 40000
W_DIST 170
W_CONE_LEN 60
W_NOVEL 3500
W_DUP 500
W_DEGREE 40
EVAL_NOISE 300

ビジュアライザ

やらなかったこと / 試さなかったこと

  • Chokudai Search: 制限時間いっぱいビームの深さを伸ばし続ける方式。チャンク分割より柔軟だが実装が間に合わなかった
  • パス列挙による計画: 「ショップ→木→…→ショップ」のパスを BFS で列挙し、新規文字列を生成するルートを明示的に計画する方式
  • 変換タイミングの最適化: 変換する木の選択や順序を評価関数に組み込んで最適化すること
  • ショップ間の分担戦略: 各ショップに異なる文字列セットを割り当てて効率的にスコアを稼ぐ戦略

感想

  • 最初は貪欲 + ランダムプレイアウトで実装したが、スコアが伸びずビームサーチに切り替えた
  • 評価関数の設計が肝で、新規性ボーナスと距離ペナルティのバランスが重要だった
  • LLM にビームサーチの骨格や高速化テクニックの実装を手伝ってもらった
  • Optuna でのパラメータ調整は安定した改善をもたらしたが、劇的な変化はなかった
  • ローカルでの最終スコアは 100 ケース平均 1139 点

AtCoder Heuristic Contest 059

AtCoder AHC

atcoder.jp

※ ほぼAIに書かせました

概要

20x20 のグリッド上にペアのカード（0〜199、各番号2枚ずつ）が配置されている。(0,0) から出発し、山札（スタック）を使ってカードを回収する。山札の上2枚が同じ番号なら自動的に消える仕組みを利用して、全カードを消すことを目指す。移動回数をできるだけ少なくしたい。

方針

問題を TSP（巡回セールスマン問題）として定式化し、反復局所探索法（ILS）＋焼きなまし法（SA）で解いた。

2フェーズ戦略

スタックの LIFO 性質を利用して、以下の2フェーズで全カードを消す。

  1. 往路（収集フェーズ）: カード番号の順列 order[0..199] に従い、各番号のペアのうち片方を拾う。2枚のうち近い方を貪欲に選ぶ
  2. 復路（回収フェーズ）: 往路の逆順で、もう片方を拾う。逆順で拾うことでスタックの上から順にペアが揃い、自動的にすべて消える

この構造により、問題は「どの順番でカードを集めるか」という順列の最適化に帰着される。

初期解：最近傍法（Nearest Neighbor）

(0,0) から出発して、未訪問のカードのうち最も近いものを貪欲に選ぶ。TSP の定番手法。

局所探索：2-opt

順列に対して 2-opt（区間反転）を適用。改善が見つかるまで全ペアを試す。

高速化のために O(1) の差分評価 を実装した。2-opt で変化するのは反転区間の両端の辺だけなので、往路・復路それぞれで変化する4辺分のみ計算し、改善が見込まれる場合のみフル評価で検証する。ただし、差分評価は pick_choice（2枚のうちどちらを先に拾うか）が変わらない前提の近似なので、デルタが負の場合にフル評価で正確なスコアを確認している。

ILS + SA

2-opt の局所最適に陥るのを防ぐため、ILS（反復局所探索）で摂動→局所探索を繰り返す。

  • 摂動: 約98%の確率で Double-bridge（4箇所で切断して再接続する TSP 定番の強い摂動）、残りはランダムスワップ
  • 受理判定: SA 方式。温度は線形に冷却（初期温度 ≈ 1.1）
  • 適応的な摂動強度: 進捗に応じてスワップ数を 2〜5 で変化

ハイパーパラメータ調整

最後に Optuna で SA の初期温度と Double-bridge の確率を探索した。30 試行で以下の値に落ち着いた。

パラメータ 値
SA 初期温度 1.099
Double-bridge 確率 0.979

ビジュアライザ

やらなかったこと / 試さなかったこと

  • バッチ分割（Chunking）: 全収集→全回収ではなく、一定サイズごとに収集・回収を繰り返す方式。実装計画は立てたが最終的には採用しなかった
  • Or-opt: 1〜3個の連続ノードを別の場所に挿入する近傍。実装する時間がなかった
  • 近傍リスト: 2-opt の相手候補を近い地点に限定する枝刈り。効果はありそうだったが未実装
  • ペア選択のビット探索: 「どちらのカードを先に拾うか」を近傍操作として明示的に最適化すること

感想

  • 最初にペアの片割れを山札に集めて、その後もう片割れを逆順に回収するというアイデアは早い段階で思いついた
  • TSP として定式化できることに気づいてからは、ILS + 2-opt の実装に集中した
  • 限界高速化や TSP の小手先テクはすべて LLM に丸投げした
  • 最後1時間くらいすることがなくて Optuna を回していたがそこまで改善せず
  • 最終結果は 96 位。もう少し近傍を増やしたり、バッチ分割を試したりできればよかった

AtCoder Beginner Contest 385（ABC385）

AtCoderBeginnerContest AtCoderBeginnerContest385 ABC ABC385

atcoder.jp

A - Equally

分け方を全通り試す

提出コード

void solve() {
    int A, B, C;
    cin >> A >> B >> C;
    if (A == B and B == C) {
        cout << "Yes" << endl;
    }
    else if (A + B == C or B + C == A or C + A == B) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

B - Santa Claus 1

シミュレーションする

提出コード

void solve() {
    int H, W, X, Y;
    cin >> H >> W >> X >> Y;
    --X, --Y;
    vector<string> S(H);
    REP(H) cin >> S[i];
    string T;
    cin >> T;
    vector<vector<int>> cnt(H, vector<int>(W, 0));
    for (auto c : T) {
        int dx = 0, dy = 0;
        if (c == 'U') dx = -1;
        if (c == 'D') dx = 1;
        if (c == 'L') dy = -1;
        if (c == 'R') dy = 1;
        if (0 <= X + dx and X + dx < H and 0 <= Y + dy and Y + dy < W and S[X + dx][Y + dy] != '#') {
            X += dx;
            Y += dy;
            if (S[X][Y] == '@') {
                cnt[X][Y]++;
                S[X][Y] = '.';
            }
        }
    }
    int ans = 0;
    REP(H) REP(j, W) ans += cnt[i][j];
    cout << X + 1 << " " << Y + 1 << " " << ans << endl;
}

C - Illuminate Buildings

$ dp[i][j] := i $ 番目まで見たときに、$ j $ 間隔で並んでいるときの最大としてDPをする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> H(N);
    REP(N) cin >> H[i];
    vector<vector<int>> dp(N, vector<int>(N));
    REP(i, N) {
        REP(w, 0, N) {
            if (i - w < 0) chmax(dp[i][w], 1);
            else if (H[i] == H[i - w]) chmax(dp[i][w], dp[i - w][w] + 1);
            else chmax(dp[i][w], 1);
        }
    }

    int ans = 0;
    REP(i, N) REP(j, N) chmax(ans, dp[i][j]);
    cout << ans << endl;
}

D - Santa Claus 2

家の数のみを考えると頂点は高々 $ 2 \times 10^5 $ となり、訪れた頂点を適宜消していくことで全体でも最大で家の数しか走査する必要がない
各x, y軸ごとに存在する頂点をsetなどで管理することで全体で $ O(N \log N) $ で解くことができる

提出コード

void solve() {
    ll N, M, Sx, Sy;
    cin >> N >> M >> Sx >> Sy;

    vector<pair<ll, ll>> houses;
    map<ll, vector<ll>> x_map;
    map<ll, vector<ll>> y_map;

    REP(N) {
        ll Xi, Yi;
        cin >> Xi >> Yi;
        houses.push_back({Xi, Yi});
        x_map[Xi].push_back(Yi);
        y_map[Yi].push_back(Xi);
    }

    for (auto &[x, ys] : x_map) {
        sort(ys.begin(), ys.end());
    }
    for (auto &[y, xs] : y_map) {
        sort(xs.begin(), xs.end());
    }

    ll current_x = Sx;
    ll current_y = Sy;
    ll count = 0;

    REP(M) {
        string Di;
        ll Ci;
        cin >> Di >> Ci;

        if (Di == "U") {
            ll target_y = current_y + Ci;
            auto &ys = x_map[current_x];

            auto left = upper_bound(ys.begin(), ys.end(), current_y);
            auto right = upper_bound(ys.begin(), ys.end(), target_y);

            vector<ll> found_ys(left, right);
            count += found_ys.size();

            x_map[current_x].erase(left, right);
            for (ll y : found_ys) {
                auto &xs = y_map[y];
                auto it = lower_bound(xs.begin(), xs.end(), current_x);
                if (it != xs.end() && *it == current_x) {
                    xs.erase(it);
                    if (xs.empty()) {
                        y_map.erase(y);
                    }
                }
            }
            current_y = target_y;
        }
        else if (Di == "D") {
            ll target_y = current_y - Ci;
            auto &ys = x_map[current_x];

            auto left = lower_bound(ys.begin(), ys.end(), target_y);
            auto right = lower_bound(ys.begin(), ys.end(), current_y);

            vector<ll> found_ys(left, right);
            count += found_ys.size();

            x_map[current_x].erase(left, right);
            for (ll y : found_ys) {
                auto &xs = y_map[y];
                auto it = lower_bound(xs.begin(), xs.end(), current_x);
                if (it != xs.end() && *it == current_x) {
                    xs.erase(it);
                    if (xs.empty()) {
                        y_map.erase(y);
                    }
                }
            }
            current_y = target_y;
        }
        else if (Di == "R") {
            ll target_x = current_x + Ci;
            auto &xs = y_map[current_y];

            auto left = upper_bound(xs.begin(), xs.end(), current_x);
            auto right = upper_bound(xs.begin(), xs.end(), target_x);

            vector<ll> found_xs(left, right);
            count += found_xs.size();

            y_map[current_y].erase(left, right);
            for (ll x : found_xs) {
                auto &ys = x_map[x];
                auto it = lower_bound(ys.begin(), ys.end(), current_y);
                if (it != ys.end() && *it == current_y) {
                    ys.erase(it);
                    if (ys.empty()) {
                        x_map.erase(x);
                    }
                }
            }
            current_x = target_x;
        }
        else if (Di == "L") {
            ll target_x = current_x - Ci;
            auto &xs = y_map[current_y];

            auto left = lower_bound(xs.begin(), xs.end(), target_x);
            auto right = lower_bound(xs.begin(), xs.end(), current_x);

            vector<ll> found_xs(left, right);
            count += found_xs.size();

            y_map[current_y].erase(left, right);
            for (int x : found_xs) {
                auto &ys = x_map[x];
                auto it = lower_bound(ys.begin(), ys.end(), current_y);
                if (it != ys.end() && *it == current_y) {
                    ys.erase(it);
                    if (ys.empty()) {
                        x_map.erase(x);
                    }
                }
            }
            current_x = target_x;
        }
    }

    cout << current_x << " " << current_y << " " << count << endl;
}

E - Snowflake Tree

中心にする頂点 $ u $ と $ x $ を全探索する
予め頂点 $ u $ に隣接する頂点について次数の降順にソートしておくと、$ y = deg_{v_x} - 1 $ となるユ木を構築できるためその最小値を求めれば良い

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> deg(N);
    vector<vector<int>> G(N);
    REP(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        deg[a]++;
        deg[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = N;
    REP(i, N) {
        vector<int> idx(G[i].size());
        iota(ALL(idx), 0);
        sort(ALL(idx), [&](int a, int b) { return deg[G[i][a]] > deg[G[i][b]]; });
        int x = 0, y = 0;
        REP(x, 1, G[i].size() + 1) {
            int v = G[i][idx[x - 1]];
            int y = deg[v] - 1;
            chmin(ans, N - (1 + x + x * y));
        }
    }
    cout << ans << endl;
}

F - Visible Buildings

二分探索で最大値を求める
各判定問題は前から順に見たときに、条件を満たすためには各ビルを見るのに必要な角度が単調増加になっているかを判定すれば良い
long double だと精度が足りないため、 __float128 を使うと通る

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> X(N), H(N);
    REP(N) cin >> X[i] >> H[i];
    int ma = *max_element(ALL(H));
    auto check = [&](__float128 m) {
        __float128 ma = -1e18;
        REP(i, N) {
            __float128 S = ((__float128)H[i] - m) / (__float128)X[i];
            if (S > ma) {
                ma = S;
            }
            else return false;
        }
        return true;
    };
    if (check(0)) {
        cout << -1 << endl;
        return;
    }
    __float128 ng = 0, ok = 1e18;
    REP(i, 100) {
        __float128 mid = (ok + ng) / 2;
        if (check(mid)) ok = mid;
        else ng = mid;
    }
    cout << setprecision(20) << (long double)ok << endl;
}

AtCoder Beginner Contest 375（ABC375）

atcoder.jp

A - Seats

#.# の数を数える

提出コード

void solve() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    REP(i, 1, N - 1) {
        if (S[i - 1] == '#' and S[i] == '.' and S[i + 1] == '#') ans++;
    }
    cout << ans << endl;
}

B - Traveling Takahashi Problem

距離を順に足していく

提出コード

void solve() {
    int N;
    cin >> N;
    ll x = 0, y = 0;
    double ans = 0;
    REP(N) {
        ll a, b;
        cin >> a >> b;
        ans += hypot(x - a, y - b);
        x = a, y = b;
    }
    ans += hypot(x, y);
    cout << fixed << setprecision(10) << ans << endl;
}

C - Spiral Rotation

各点ごとに何回操作されるかが決まり、各操作は $ \pmod{4} $ でどこに移動するか求められるので各点ごとにどこに移動するかが定まる

提出コード

void solve() {
    int N;
    cin >> N;
    vector<string> A(N);
    REP(i, N) cin >> A[i];
    vector B = A;
    REP(x, N) {
        REP(y, N) {
            int cnt = (min({x, N - x - 1, y, N - y - 1}) + 1) % 4;
            int nx = x, ny = y;
            REP(k, cnt) {
                int tmp = nx;
                nx = ny;
                ny = N - 1 - tmp;
            }
            dump(x, y, nx, ny, cnt);
            B[nx][ny] = A[x][y];
        }
    }
    REP(i, N) cout << B[i] << endl;
}

D - ABA

中心を固定して考える
このとき、回文になる個数は中心から左右にある同じ文字の選び方の総和になる
そのため、中心から左右の文字ごとの個数を管理し、各文字ごとに選び方の総和を加算していく

提出コード

void solve() {
    string S;
    cin >> S;
    vector<ll> l_cnt(26, 0), r_cnt(26, 0);
    REP(S.size()) r_cnt[S[i] - 'A']++;
    ll ans = 0;
    int N = S.size();
    r_cnt[S[0] - 'A']--;
    l_cnt[S[0] - 'A']++;
    REP(i, 1, N - 1) {
        r_cnt[S[i] - 'A']--;
        ll cnt = 0;
        REP(j, 26) {
            if (l_cnt[j] > 0 && r_cnt[j] > 0) ans += l_cnt[j] * r_cnt[j];
        }
        l_cnt[S[i] - 'A']++;
    }
    cout << ans << endl;
}

E - 3 Team Division

$ dp[i][j][k] := i $ 番目まで見たときに、チーム2の総和が $ j $ 、チーム3の総和が $ k $ となるように必要な操作回数の最小としてDPをする

提出コード

void solve() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    REP(i, N) { cin >> A[i] >> B[i]; }
    int sum = accumulate(ALL(B), 0);
    if (sum % 3) {
        cout << -1 << endl;
        return;
    }
    vector dp(501, vector<int>(501, INF));
    dp[0][0] = 0;
    REP(i, N) {
        vector ndp(501, vector<int>(501, INF));
        REP(j, 501) {
            REP(k, 501) {
                if (dp[j][k] == INF) continue;
                // チーム1から移動
                if (A[i] == 1) {
                    chmin(ndp[j][k], dp[j][k]);
                    if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k] + 1);
                    if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k] + 1);
                }
                // チーム2から移動
                if (A[i] == 2) {
                    chmin(ndp[j][k], dp[j][k] + 1);
                    if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k]);
                    if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k] + 1);
                }
                // チーム3から移動
                if (A[i] == 3) {
                    chmin(ndp[j][k], dp[j][k] + 1);
                    if (j + B[i] < 501) chmin(ndp[j + B[i]][k], dp[j][k] + 1);
                    if (k + B[i] < 501) chmin(ndp[j][k + B[i]], dp[j][k]);
                }
            }
        }
        swap(dp, ndp);
    }
    cout << (dp[sum / 3][sum / 3] == INF ? -1 : dp[sum / 3][sum / 3]) << endl;
}

F - Road Blocked

クエリを逆から見て、辺の削除を辺の追加クエリとして考える
あらかじめワーシャルフロイドで全点間の最短距離を求めておく
このとき、辺を追加したときの更新クエリは $ O(N^2) $ で更新でき、また更新クエリが $ 300 $ 以下であるので全体で $ O(N^3) $ で更新クエリを行うことができる

提出コード

void solve() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<ll> A(M), B(M), C(M);
    REP(i, M) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--, B[i]--;
    }
    using T = tuple<int, int, int>;
    vector<T> query(Q);
    set<int> removed_edge;
    REP(i, Q) {
        int x = -1, y = -1, z = -1;
        cin >> x;
        if (x == 1) cin >> y;
        else cin >> y >> z;
        query[i] = T(x, y - 1, z - 1);
        if (x == 1) removed_edge.insert(y - 1);
    }
    vector<vector<ll>> G(N, vector<ll>(N, LINF));
    REP(i, M) {
        if (removed_edge.contains(i)) continue;
        G[A[i]][B[i]] = C[i];
        G[B[i]][A[i]] = C[i];
    }
    REP(i, N) { G[i][i] = 0; }
    REP(k, N) REP(i, N) REP(j, N) {
        if (G[i][k] == LINF or G[k][j] == LINF) continue;
        chmin(G[i][j], G[i][k] + G[k][j]);
    }
    vector<ll> ans;
    reverse(ALL(query));
    for (auto [x, y, z] : query) {
        if (x == 1) {
            ll X = A[y], Y = B[y], Z = C[y];
            chmin(G[X][Y], Z);
            chmin(G[Y][X], Z);
            REP(i, N) {
                REP(j, N) {
                    if (i != j) {
                        chmin(G[i][j], G[i][X] + G[Y][j] + Z);
                        chmin(G[i][j], G[i][Y] + G[X][j] + Z);
                    }
                }
            }
        }
        else {
            if (G[y][z] == LINF) ans.push_back(-1);
            else ans.push_back(G[y][z]);
        }
    }
    reverse(ALL(ans));
    for (auto a : ans)
        cout << a << endl;
}

AtCoder Beginner Contest 367（ABC367）

AtCoderBeginnerContest AtCoderBeginnerContest367 ABC ABC367

atcoder.jp

A - Shout Everyday

for文などで寝ている時間のフラグを立てて、判定する

提出コード

void solve() {
    int A, B, C;
    cin >> A >> B >> C;
    vector<int> awake(24, true);
    for (int i = B;; i++) {
        awake[i] = false;
        if (i == 23) i = -1;
        if (i == C - 1) break;
    }
    cout << (awake[A] ? "Yes" : "No") << endl;
}

B - Cut .0

文字列で受け取って、後ろから連続する0を削除する

提出コード

void solve() {
    string X;
    cin >> X;
    string seisu = "";
    string shosu = "";
    bool ok = false;
    for (char c : X) {
        if (c == '.') {
            ok = true;
            continue;
        }
        if (!ok) seisu += c;
        if (ok) shosu += c;
    }
    for (int i = shosu.size() - 1; i >= 0; i--) {
        if (shosu[i] == '0') shosu.pop_back();
        else break;
    }
    if (shosu.empty()) cout << seisu << endl;
    else cout << seisu << "." << shosu << endl;
}

C - Enumerate Sequences

再帰関数などで実際に列挙して出力する

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N * 2);
    REP(i, N) {
        cin >> A[i];
        A[i + N] = A[i];
    }
    map<ll, ll> mp;
    vector<ll> cum(2 * N + 1);
    ll ans = 0;
    REP(i, N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i] % M]++;
    }
    REP(i, N, 2 * N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i - N] % M]--;
        ans += mp[cum[i] % M];
        mp[cum[i] % M]++;
    }
    cout << ans << endl;
}

D - Pedometer

Zero-Sum rangesみたいな感じ
1周分の長さを保ちながらしゃくとりっぽくやる

提出コード

void solve() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N * 2);
    REP(i, N) {
        cin >> A[i];
        A[i + N] = A[i];
    }
    map<ll, ll> mp;
    vector<ll> cum(2 * N + 1);
    ll ans = 0;
    REP(i, N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i] % M]++;
    }
    REP(i, N, 2 * N) {
        cum[i + 1] = cum[i] + A[i];
        mp[cum[i - N] % M]--;
        ans += mp[cum[i] % M];
        mp[cum[i] % M]++;
    }
    cout << ans << endl;
}

E - Permute K times

ダブリングをする
1回の操作を元の $ A $ のindexのうち、どのindexに移動するかと考えるとそれぞれのindexに対応する移動先は固定になるのでダブリングで求めることができる

提出コード

void solve() {
    ll N, K;
    cin >> N >> K;
    vector<int> X(N);
    vector<int> A(N);
    REP(i, N) {
        cin >> X[i];
        X[i]--;
    }
    REP(i, N) cin >> A[i];

    vector<vector<ll>> to(62, vector<ll>(N));
    REP(i, N) to[0][i] = X[i];
    REP(i, 61) REP(j, N) to[i + 1][j] = to[i][to[i][j]];

    REP(i, N) {
        ll cur = i;
        REP(j, 62) {
            if ((K >> j) & 1) {
                cur = to[j][cur];
            }
        }
        cout << A[cur] << " ";
    }
    cout << endl;
}

F - Rearrange Query

各要素にZobrist Hashでhashを割り当てておく
Mo法で各クエリにおける集合のhashを求め、それが一致するかどうかで判定ができる
同じ要素が複数ある時の場合でも、hashの加減算で一致判定が高い確率で行える

提出コード

void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N), b(N);
    REP(i, N) { cin >> a[i]; }
    REP(i, N) { cin >> b[i]; }
    vector<uint32_t> hash(202020);
    REP(i, 202020) { hash[i] = XorShift(); }
    vector<int> l(Q), r(Q), L(Q), R(Q);

    REP(i, Q) {
        cin >> l[i] >> r[i] >> L[i] >> R[i];
        --l[i], --L[i];
    }
    vector<uint32_t> ans1(Q), ans2(Q);
    uint32_t sum1 = 0, sum2 = 0;
    auto add1 = [&](int idx) { sum1 += hash[a[idx]]; };
    auto erase1 = [&](int idx) { sum1 -= hash[a[idx]]; };
    auto out1 = [&](int idx) { ans1[idx] = sum1; };
    auto add2 = [&](int idx) { sum2 += hash[b[idx]]; };
    auto erase2 = [&](int idx) { sum2 -= hash[b[idx]]; };
    auto out2 = [&](int idx) { ans2[idx] = sum2; };
    Mo mo1(N);
    Mo mo2(N);
    REP(i, Q) {
        mo1.add(l[i], r[i]);
        mo2.add(L[i], R[i]);
    }
    mo1.build(add1, erase1, out1);
    mo2.build(add2, erase2, out2);
    REP(i, Q) { cout << (ans1[i] == ans2[i] ? "Yes" : "No") << endl; }
}