ABC457 A-D問 振り返り

はじめに

ABC457へ参加したので振り返っていきます。結果は4完（A-D）でした。

A - Array

概要

配列$A$から$X$番目の値を取り出す問題でした（最初のテストケースでA[X + 1]で実装して出力がおかしくなったのは内緒です）。

計算量

入力は$O(N)$、クエリ（実質的に出力）は$O(1)$ですね。

abc457_a.c

#include <stdio.h>

int main(void) {
    int N; scanf("%d", &N);
    int A[N]; for (int i = 0; i < N; i++) scanf("%d", &A[i]);
    int X; scanf("%d", &X);

    int ans = A[X - 1];
    printf("%d\n", ans);

    return 0;
}

B - Arrays

概要

$N$個の長さが異なる数列からA[X][Y]を取り出す問題でした。

配列の設計

最初は2次元配列で保存した後、探索して出力する設計で提出しました（テストケースも通りましたし）。そしてRE（オーバーフロー）しました。制約が$N = 2 \times 10 ^ 5$だったので$N ^ 2 = 4 \times 10 ^ {10}$でスタックを破壊しました...（何をしているのやら）。

しかし問題文をよく読むと「$L_i$の総和には天井がある」とのことです。ということでフラットな（1次元の）配列にしたところ、無事にACできました。

計算量

入力は$O(\sum L_i)$、クエリは$O(1)$です（オフセットで直接アクセスできるため）。

abc457_b.c

#include <stdio.h>

#define MAXN 200001

int main(void) {
    int N; scanf("%d", &N);
    int A[MAXN];
    int L[MAXN];
    int start[MAXN + 1]; start[1] = 0;

    for (int i = 1; i <= N; i++) {
        scanf("%d", &L[i]);
        start[i+1] = start[i] + L[i];
        for (int j = 1; j <= L[i]; j++) {
            scanf("%d", &A[start[i] + j - 1]);
        }
    }

    int X, Y;
    scanf("%d %d", &X, &Y);

    int ans = A[start[X] + Y - 1];
    printf("%d\n", ans);

    return 0;
}

この問題はPythonのリストだとシンプルに実装できるそうです。

A = []
for _ in range(N):
    row = list(map(int, input().split()))
    A.append(row[1:]) # 先頭が L なので除く

また、C++のvectorでも同様に実装できます。

vector<vector<int>> A(N + 1);

for (int i = 1; i <= N; i++) {
    int l; cin >> l;
    A[i].resize(l);
    for (int j = 0; j < l; j++) cin >> A[i][j];
}

ただ、今回のようにCで通常の配列とオフセットで実装したのは、可変長配列が使えなかったりキャッシュ効率を重視する場面では重宝されます。

C - Long Sequence

概要

$N$個の数列$A_1{,}...{,}A_N$と、各数列の繰り返し回数$C_i$が与えられます。$A_i$を$C_i$回、$A_2$を$C_2$回、と順に連結して作られる数列$B$の$K$番目の要素を求めます。

なぜBを構築できないか

まず制約から$C_i$が最大$10^9$のため$B$の長さは最大$10 ^ {14}$になりえます。実際に$B$を作るのは不可能なので、$K$を削りながら答えを探します。

配列$A$はB問題と同じデータ構造なので、そのまま使い回しました。

$i$番目のブロックサイズは$C_i \times L_i$です。$K$がこのサイズ以下ならブロック内に答えがあります。そうでなければK -= C[i] * L[i]して次のブロックへ進みます。

答えが$A_i$のブロックに収まったとき、$A_i$は$C_i$回繰り返されているので$K$を$L_i$で割った余りが$A_i$内での位置になります。余りが0のときは$L_i$番目です。

計算量

$O(N)$で収まります（各ブロックを1回ずつ見るだけなので）。

abc457_c.c

#include <stdio.h>

#define MAXN 200001

int A[MAXN];
int L[MAXN];
int start[MAXN + 1];
long long C[MAXN];

int main(void) {
    int N;
    long long K;
    scanf("%d %lld", &N, &K);

    start[1] = 0;
    for (int i = 1; i <= N; i++) {
        scanf("%d",&L[i]);
        for (int j = 1; j <= L[i]; j++) {
            scanf("%d", &A[start[i] + j - 1]);
        }
        start[i + 1] = start[i] + L[i];
    }

    for (int i = 1; i <= N; i++) {
        scanf("%lld", &C[i]);
    }

    for (int i = 1; i <= N; i++) {
        long long block = C[i] * L[i];
        if (K <= block) {
            int pos = K % L[i];
            if (pos == 0) pos = L[i];
            printf("%d\n", A[start[i] + pos - 1]);
            return 0;
        } else {
            K -= C[i] * L[i];
        }
    }

    return 0;
}

D - Raise Minimum

概要

長さ$N$の数列$A$と整数$K$が与えられます。操作「$i$を選び$A_i$に$i$を加える」を$K$回以内行い、操作後の数列の最小値を最大化せよ、という問題でした。

最小値を固定する

まず、最小値を1ずつ増やしながら全通り試すと、$A_i$や$K$が最大$10^{18}$のためループが終わりません。

「最小値を最大化する」という最適化の問題を「最小値を$m$以上にできるか」という判定問題に言い換えましょう。$m$を固定したとき、各要素$A_i$を$m$以上にするのに必要な操作回数は、ceil((m - A_i) / i)となります（A_i >= mなら0回）。

1回の操作で$A_i$に$i$を加えるので、不足分m - A_iを$i$で割り切り上げた回数が必要になります。これを全要素について合計し、$K$以下なら$m$は達成可能と判定できます。

単調性

ここで $m$が大きくなるほど必要な操作数は増える （単調増加）という性質に気づきます。つまり、

• $m$が小さい → 操作数が少ない → 達成可能
• $m$が大きい → 操作数が多い → 達成不可能

達成可能 or 不可能の境界が必ず1箇所存在します。この単調性があるとき、二分探索で境界を効率よく探せます。

なぜ単調性があると二分探索できるのか

達成可能か否かの判定結果を$m$の小さい順に並べると、

m:   1   2   3  ...  答え  答え+1 ...
判定: ⚪︎  ⚪︎  ⚪︎ ...  ⚪︎     ×  ...

必ず⚪︎が続いた後に×が続く形になります。この境界を1から順に探すと最大$10^{18}$回の判定が必要ですが、二分探索なら毎回探索範囲を半分に絞れるため$\log_2(10^{18} \approx 60$回で済みます。
「最大化・最小化」問題で判定に単調性がある場合、この答えで二分探索というパターンが使えます。

計算量

二分探索のループ回数は$log_2(2 \times 10^{18}) \approx 61$回です。各ループでの確認が$O(N)$で、合計は$O(N log(解答))$で十分高速です。

abc457_d.c

#include <stdio.h>

#define MAXN 200001

int N;
long long K;
long long A[MAXN];

int check(long long m) {
    long long total = 0;
    for (int i = 1; i <= N; i++) {
        if (A[i] < m) total += (m - A[i] + i - 1) / i;
        if (total > K) return 0;
    }
    return 1;
}

int main(void) {
    scanf("%d %lld", &N, &K);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &A[i]);
    }

    long long lo = 1;
    long long hi = 2e18;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }

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

おわりに

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

A問：やるだけ
B問：フラットな配列
C問：数列の読み捨て
D問：二分探索（単調性に気づく）

全体的に配列がテーマの回でしたね。実装力の不足が目立った回だったので、精進していきたいです。