【3完】ABC455 振り返り #C++

はじめに

ABC455に参加したため、振り返っていきます。結果は3完でした（あと8分あれば4完でした...）。

A - 455

シンプルな条件判定の問題でした。3つの整数$A, B, C$を読み込み、$A≠B$かつ$B=C$を満たすか判定するだけです。

abc455_a.c

#include <stdio.h>

int main(void) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);

    if (A != B && B == C) printf("Yes\n");
    else printf("No\n");

    return 0;
}

B - Spiral Galaxy

グリッド内のすべての長方形において点対象を全探索で求める問題でした。方針として、全長方形を列挙した後に対照か否かを判別します。
実際の実装は、以下の3ステップになります。

1. (h1, h2, w1, w2)の4重ループですべての長方形を列挙（$O(H^2W^2)$通り）
2. 各長方形について、マス(i, j)と対称点(h1 + h2 - i, w1 + w2 - j)の色が一致するか2重ループで確認
3. 全マスが一致していればカウント

にしても、B問題で6重ループってすごいですね...。

abc455_b.c

#include <stdio.h>

int H, W;
char S[11][11];

// 判別式を関数として分けたため、6重ループの圧巻が伝わってこない
int is_symmetric(int h1, int h2, int w1, int w2) {
    int i, j;
    for (i = h1; i <= h2; i++) {
        for (j = w1; j <= w2; j++) {
            if (S[i][j] != S[h1+h2-i][w1+w2-j]) {
                return 0;
            }
        }
    }
    return 1;
}

int main(void) {
    int h1, h2, w1, w2;
    int count = 0;

    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; i++) {
        scanf("%s", S[i]);
    }

    for (h1 = 0; h1 <= H-1; h1++) {
        for (h2 = h1; h2 <= H-1; h2++) {
            for (w1 = 0; w1 <= W-1; w1++) {
                for (w2 = w1; w2 <= W-1; w2++) {
                    if (is_symmetric(h1, h2, w1, w2)) {
                        count++;
                    }
                }
            }
        }
    }

    printf("%d\n", count);
    return 0;
}

計算量の内訳は、

• 長方形の選び方が$O(H-2W^2)$通り
• 各長方形の点対称チェックが最大$O(HW)$

なので合計は$O(H^3W^3)$です。$H, W \leq 10$のとき$10^6$程度なので十分間に合います。

C - Vanish

配列において同じ値の要素をすべて0にする操作を$K回$繰り返し、その際の和の最小値を求める問題でした。方針として、$K$回の操作で合計を最小にするには、合計が大きいグループから順に消せばよいです。
実際の実装は以下の3ステップになります。

1. 配列をソートして同じ値をまとめ、グループごとの合計を計算
2. グループの合計を降順ソート
3. 上位$K$個のグループの合計を全体の合計から引く（$K≥M$なら出力は$0$）

group_sumの宣言がlong longなのは、$A_i\leq10^9$、$N≤300,000$なので合計がintの範囲を超えるからです。
1回の操作ごとにグループを丸ごと$0$にするため、グループ単位の貪欲が妥当です。

abc455_c.c

#include <stdio.h>
#include <stdlib.h>

int N, K;
long long A[300001];
long long group_sum[300001];
int M;

int cmp_asc (const void *a, const void *b) {
    long long x = *(long long *)a;
    long long y = *(long long*)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int cmp_desc(const void *a, const void *b) {
    return cmp_asc(b, a);
}

int main(void) {
    int i;
    long long total = 0;
    long long current_sum;
    long long ans;

    scanf("%d %d", &N, &K);
    for (i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
        total += A[i];
    }

    qsort(A, N, sizeof(long long), cmp_asc);

    M = 0;
    current_sum = A[0];
    for (i = 1; i < N; i++) {
        if (A[i] != A[i-1]) {
            group_sum[M++] = current_sum;
            current_sum = A[i];
        } else {
            current_sum += A[i];
        }
    }
    group_sum[M++] = current_sum;

    qsort(group_sum, M, sizeof(long long), cmp_desc);

    if (K >= M) {
        printf("0\n");
        return 0;
    }

    ans = total;
    for (i = 0; i < K; i++) {
        ans -= group_sum[i];
    }

    printf("%lld\n", ans);
    return 0;
}

計算量の内訳は、

• 2回のqsortがぞれぞれ$O(N\log N)$
• グループ合計の集計が$O(N)$

上位$K$個の除算が$O(K) \leq O(N)$なので、全体で$O(N \log N)$です。

D - Card Pile Query

複数のカードの山で最も上のカードを移動させて、最後の状態を出力する問題でした。最初の設計方針としてスタックで愚直に進めようとしました。しかし、「カード$C$をカード$P$の上に置く」操作を愚直にシミュレートすると、計算量が$O(NQ)$でタイムアウトします（というかしました）。そのため、操作中はポインタだけを更新し、最後にまとめて計算します。

abc455_d.c

#include <stdio.h>

int N, Q;
int below_card[300001];
int count_arr[300001];

int find_pile(int c) {
    if (below_card[c] == -1) return c;
    below_card[c] = find_pile(below_card[c]);
    return below_card[c];
}

int main(void) {
    int i, C, P;

    scanf("%d %d", &N, &Q);

    for (i = 1; i <= N; i++) {
        below_card[i] = -1;
    }

    for (i = 0; i < Q; i++) {
        scanf("%d %d", &C, &P);
        below_card[C] = P;
    }

    for (i = 1; i <= N; i++) {
        count_arr[find_pile(i)]++;
    }

    for (i = 1; i <= N; i++) {
        if (i > 1) printf(" ");
        printf("%d", count_arr[i]);
    }
    printf("\n");

    return 0;
}

隣接リストの復習

グラフを表現するデータ構造です。「各頂点から出るエッジの一覧」を持ちます。隣接行列と比較すると、以下のようになります。

	隣接行列	隣接リスト
メモリ	$O(V^2)$	$O(V + E)$
辺の存在確認	$O(1)$	$O(\text{次数})$
全隣接頂点の走査	$O(V)$	$O(\text{次数})$
向いているグラフ	密グラフ	疎グラフ

競プロでは頂点数・辺数が大きく疎なグラフになりやすいため、隣接リストが基本です。

1. below_card[C]はカード$C$の1つ下のカードを表す配列（初期値-1は山の底）
2. 操作ごとにbelow_card[C] = Pのみ更新（$O(1)$）
3. 全操作終了後、各カードについてfind_pile(c)で山の底（山番号）を求める
4. find_pileは経路圧縮付き再帰で、たどった経路をすべて短絡化する

経路圧縮とは？
愚直に根をたどると気が深くなるにつれて探索が遅くなります。経路圧縮は探索の途中で通ったノードをすべて根に直結する最適化です。

経路圧縮前：1 → 2 → 3 → 4（根）
経路圧縮後：1 → 4、2 → 4、3 → 4

ランクによるuniteと組み合わせることで、1操作あたりの計算量は$O(\alpha(N))$（アッカーマン逆関数）となり、実質$O(1)$ です。

最終的な山の構成だけが問われるため、途中の状態は不要です。よって操作中に更新しなくてよいです。計算量は$O(N+Q)$です。

なぜスタックだけではTLEしたか
スタックで各山を管理すると、「カード$C$をカード$P$の上に置く」操作のたびに、元の山でカード$C$より上にあったすべてのカードの所属情報を書き換える必要があります。

例えば、$N=300{,}000$枚が1つの山に積まれた状態で、毎回その山の2番目から下のカードを別の山に移動させる操作を考えます。1操作あたり$O(N)$の更新が発生し、$Q = 300{,}000$ 回繰り返すと計算量は$O(NQ) = O(9 \times 10^{10})$となり、制限時間内に終わりません。

そこで操作中はbelow_card[C] = Pという1行だけ記録し、山の所属は最後にまとめて求める、という方針に切り替えました。

Union-Find木とは？

互いに素な集合（素集合）を効率的に管理するデータ構造です。以下の2つの操作を高速に行えます。

• find(x)：要素xが属する集合の代表(根)を探す
• unite(x, y)：要素xとyが属する集合を1つに統合する

おわりに

今回のコンテストの解法をまとめると、以下のとおりです。

A問題：やるだけ（条件判定)
B問題：全探索
C問題：貪欲法
D問題：連結リスト + Union-Find

B - D問題では計算量の理解が試されていた感じがします。B問では制約から6重ループでも問題ない、しかしD問題ではポインタだけの操作にしないとタイムアウトする。
計算量は大学編入でも必須の要素なので、そこら辺を意識して精進していきたいです。