概要

一列に並んだ \(N\) 個のドミノに対して、左から順に「まだ倒れていなければ手で倒し、右隣のドミノが自分より低ければ連鎖的に倒す」というルールに従ってシミュレーションを行い、各ドミノを倒した直接の原因（手で倒した場合は \(0\)、他のドミノならその番号）を求める問題です。

考察

素朴なアプローチとその問題点

ドミノが倒れる連鎖を愚直にシミュレーションすることを考えます。 ドミノ \(i\) が倒れたとき、その右側にある「まだ倒れていないドミノ」を1つずつ探して、高さが自分より低いかを判定していきます。

しかし、この方法ではすでに倒れたドミノを何度も走査することになってしまいます。 例えば、すべてのドミノがすでに倒れている状態で、右端の方にあるドミノをチェックするために左から順番に走査すると、最悪の場合 \(O(N^2)\) の時間がかかってしまい、 \(N \le 5 \times 10^5\) という制約下では実行時間制限（TLE）に間に合いません。

高速化のアイデア：すでに倒れたドミノをスキップする

この問題の鍵は、「次に倒すべき『まだ倒れていない最も左のドミノ』をいかに高速に見つけるか」にあります。

ドミノは必ず左から順に処理され、連鎖も左から右へと進みます。したがって、「まだ倒れていない最小のドミノの番号」を管理する変数 head を用意しておけば、常に \(O(1)\) で次のドミノにアクセスできます。

具体的には、以下の情報を管理します。 - nxt[i]: ドミノ \(i\) が倒れたときに、その次に調べるべきドミノの番号（初期値は \(i + 1\)） - head: 現在まだ倒れていないドミノのうち、最も左にあるものの番号（初期値は \(1\)）

ドミノ \(v\) が倒れたとき、その右隣のまだ立っているドミノは nxt[v] になります。したがって、ドミノ \(v\) が倒れた瞬間に、次に調べるべき位置 head を nxt[v] に更新します。各ドミノは一生に一度しか倒れないため、この head が右に進む回数は全体で高々 \(N\) 回となり、非常に高速にシミュレーションを行うことができます。

---

アルゴリズム

1. 初期化:

   • 各ドミノの右隣を指すポインタ nxt[i] = i + 1 とします。
   • 各ドミノを倒した原因を格納する配列 ans を \(-1\)（未確定）で初期化します。
   • まだ倒れていない最小のドミノを指す head = 1 とします。

2. シミュレーション: \(i = 1\) から \(N\) まで順にループを回します。

   • もし ans[i] != -1 ならば、ドミノ \(i\) はすでに連鎖によって倒されているので、何もせずスキップします。
   • そうでない場合、ドミノ \(i\) を手で倒します。
     • ans[i] = 0 とします。
     • head を nxt[i] に更新します。
     • 現在連鎖の起点となっているドミノを curr = i とします。
     • 連鎖のループ:

          - 次に倒れる候補のドミノを $v = head$ とします。
          - もし $v > N$（ドミノの範囲外）なら、連鎖は終了します。
          - もし $A_v < A_{curr}$（候補のドミノ $v$ が現在のドミノ $curr$ より真に低い）ならば、ドミノ $v$ はドミノ $curr$ によって倒されます。
       

       • ans[v] = curr と記録します。
       • head を nxt[v] に進めます。
       • 次の連鎖の起点を \(curr = v\) に更新し、連鎖のループを続けます。

            - $A_v \geq A_{curr}$ ならば、連鎖はここでストップします。
         

---

計算量

• 時間計算量: \(O(N)\) 各ドミノ \(v\) について、head が \(v\) を指して ans[v] が更新される（＝ドミノが倒される）回数は高々1回です。また、連鎖がストップしてループを抜ける回数は、外側のループの回数と同じく高々 \(N\) 回です。したがって、全体の while ループの実行回数は高々 \(2N\) 回となり、時間計算量 \(O(N)\) で処理が完了します。
• 空間計算量: \(O(N)\) ドミノの高さ \(A\)、次のドミノを指す nxt、答えを記録する ans の各配列を保持するために、 \(O(N)\) のメモリを使用します。

---

実装のポイント

• 番兵の利用: nxt 配列のサイズを \(N + 2\) まで確保しておくことで、インデックスが \(N\) を超えた場合（すべてのドミノが倒れた場合）の境界値エラーを綺麗に防ぐことができます。

• 高速入出力: \(N \le 5 \times 10^5\) と入力サイズが大きいため、C++では cin.tie(NULL); ios_base::sync_with_stdio(false); を記述して入出力を高速化しておくことが重要です。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    // 各ドミノの右隣のドミノを指すポインタ
    vector<int> nxt(N + 2);
    for (int i = 1; i <= N + 1; ++i) {
        nxt[i] = i + 1;
    }

    vector<int> ans(N + 1, -1);
    int head = 1; // まだ倒れていない最小のドミノの番号

    for (int i = 1; i <= N; ++i) {
        if (ans[i] != -1) {
            // すでに倒れている場合はスキップ
            continue;
        }
        
        // 指で直接倒す
        ans[i] = 0;
        head = nxt[i];
        int curr = i;
        
        // 連鎖のシミュレーション
        while (true) {
            int v = head;
            if (v > N) {
                break;
            }
            if (A[v] < A[curr]) {
                ans[v] = curr;
                head = nxt[v];
                curr = v;
            } else {
                break;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << (i == N ? "" : " ");
    }
    cout << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。