2025-01-09

KUPC 2024 M - Mahjong 2 (3D)

KUPC AtCoder 大学コンテスト有志コン左右からそれぞれ走査する累積和テク:左右両端からの累積和や累積結果を前処理 Greedy 前処理場合分け：小さい場合は愚直に解ける考察：順序を工夫して解く単純化：操作の流れを単純化して考える考察：mod3で考える NoviSteps3D 各kに対して

実装が少し大変だった。そして、両端から Greedy で追い詰めていけばよいのは思いつかなかった。チームメイトが思いついていた。

問題へのリンク

問題概要

1 から $N$ までの整数が書かれたカードが合計で $3M−1$ 枚あり、整数 $i$ の書かれたカードは $A_{i}$ 枚ある。各 $x = 1, 2, \dots, N$ に対して、整数 $x$ の書かれたカードを追加して以下の条件を満たせるかを判定せよ。

【条件】
「同じ数字の書かれた 3 枚のカード」または「連続した数字の書かれた 3 枚のカード」を選び取り除くことを $M$ 回繰り返して、持っているカードを空にすることができる。

制約

$1 \le N \le 5 \times 10^{5}$
$1 \le M \le 10^{8}$

考えたこと

まず、 $3M$ 枚のカードに対して、条件を満たせるかを判定する方法から考えてみよう。

もし、1 の書かれたカードに対して、「1, 2, 3」という操作を 3 回行ったとしたとき、それは「1, 1, 1」「2, 2, 2」「3, 3, 3」という操作と等価であるから、操作「1, 2, 3」は高々 2 回までとしてよい。言い換えれば、 $A_{1} \ge 3$ であるならば、 $A_{1} \le 2$ になるまで操作「1, 1, 1」を繰り返せば良い。

$A_{1} \le 2$ の状態にしたあと、操作「1, 2, 3」を $A_{1}$ 回行う必要がある。このとき、 $A_{2} \lt A_{1}$ または $A_{3} \lt A_{1}$ ならば、その時点で条件を満たさないと判定できる。 $A_{2} \ge A_{1}$ かつ $A_{3} \ge A_{1}$ であるならば、 $A_{2}, A_{3}$ から $A_{1}$ を引く。

その後は、2 の書かれたカードに対して、先ほどと同様の考察をすればよい。これで、 $3M$ 枚のカードに対して条件を満たせるかどうかを判定する方法がわかった。

左右両端から

その後、チームメイトのアトリウム君が「右側からも同じ Greedy ができるから、左右両端から Greedy していって、最後の 5 枚をアドホックに見ればいいじゃん」と言った。それでいいじゃんとなって、アトリウム君が実装して AC となった。

僕自身も復習のために実装することにした。整数 $x$ の書かれたカードを加えて条件を満たすかどうかは、次の方法によって判定することができる。

整数 $1, 2, \dots, x-3$ の書かれたカードをすべて 0 枚にする（左から Greedy に基づく操作を施して、整数 $x-2, x-1$ の書かれたカードもそれに合わせた枚数を除去する）
整数 $x+3, x+4, \dots, N$ の書かれたカードをすべて 0 枚にする（右から Greedy に基づく操作を施して、整数 $x+2, x+1$ の書かれたカードもそれに合わせた枚数を除去する）
その後、整数 $x-2, x-1, x, x+1, x+2$ の書かれたカードについて、3 枚ずつ作れるかを判定する

よって、次の値を前処理で求めておくことにした。

left[l]：先述の Greedy 解法に基づいて数字 $1, 2, \dots, l$ の書かれたカードをすべて 0 枚にするように操作したとき、数字 $l+1$ の書かれたカードを除去する枚数と、数字 $l+2$ の書かれたカードを除去する枚数
right[r]：先述の Greedy 解法に基づいて数字 $N-r, N-r+1, \dots, N$ の書かれたカードをすべて 0 枚にするように操作したとき、数字 $N-r-1$ の書かれたカードを除去する枚数と、数字 $N-r-2$ の書かれたカードを除去する枚数

これらを $O(N)$ の計算量であらかじめ求めておくことで、各 $x$ について条件を満たすかどうかを $O(1)$ の計算量で判定できる。

全体として $O(N)$ の計算量の解法が得られた。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    // res[l] := A を左からの Greedy で値 [0, l) を全消しするとき、値 l+1, l+2 を何個消す必要があるか
    auto calc = [&](vector<int> A) -> vector<pint> {
        vector<pint> res({pint(0, 0)});
        for (int i = 0; i < A.size(); i++) {
            auto [a, b] = res.back();

            // 区間 [0, i) ができないとき、区間 [0, i+1) もできない
            if (a == -1) {
                res.emplace_back(-1, -1);
                continue;
            }
            if (A[i] < a) {
                res.emplace_back(-1, -1);
                continue;
            }
            A[i] -= a, A[i] %= 3;
            res.emplace_back(b + A[i], A[i]);
        }
        return res;
    };

    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // A の左から left 個、右から right 個のみを 0 にしたときの影響を求める
    auto left = calc(A);
    reverse(A.begin(), A.end());
    auto right = calc(A);
    reverse(A.begin(), A.end());

    // 各 x について条件判定する
    vector<int> res;
    for (int x = 0; x < N; x++) {
        int l = max(x-2, 0), r = min(x+3, N);
        vector<int> B(r-l, 0);
        for (int i = l; i < r; i++) B[i-l] = A[i];
        B[x-l]++;
        if (left[l].first == -1 || right[N-r].first == -1) continue;
        B[0] -= left[l].first, B[1] -= left[l].second;
        B[r-l-1] -= right[N-r].first, B[r-l-2] -= right[N-r].second;
        auto tmp = calc(B);
        if (tmp.back() == pint(0, 0)) res.emplace_back(x);
    }

    cout << res.size() << endl;
    for (auto val : res) cout << val+1 << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

KUPC 2024 M - Mahjong 2 (3D)

問題概要

制約

考えたこと

左右両端から

コード