概要

左から順にドミノを倒すシミュレーションを行い、各ドミノが「高橋君の指」または「直前のドミノ」のどちらによって倒されたかを、ポインタの走査を用いて \(O(N)\) で求める問題です。

考察

重要な気づき

この問題のポイントは、「左から順に処理を行う」というルールにあります。

1. 次に指で倒すドミノの決定 左から順にドミノを見ていくとき、すでに倒れているドミノはスキップされます。したがって、ある時点で「まだ倒れていないドミノのうち、最も左にあるもの」は、左からの連鎖が届かなかったドミノです。このドミノは必ず高橋君が指で直接倒すことになります。

2. 連鎖の挙動 指で倒されたドミノを \(i\) とします。このドミノの右隣にあるドミノ \(i+1\) は、まだ倒れていません。

   • もし \(A_{i+1} < A_i\) ならば、ドミノ \(i\) はドミノ \(i+1\) を倒します。このとき、ドミノ \(i+1\) を倒した直接の原因はドミノ \(i\) です。
   • 次に、新しく倒れたドミノ \(i+1\) を起点として、さらに右隣の \(i+2\) が倒せるかを判定します。基準となる高さは \(A_{i+1}\) に更新されます。
   • この連鎖は、右隣のドミノの高さが起点のドミノの高さ以上になる（\(A_j \geq A_{curr}\)）か、右端に達するまで右隣へ一つずつ進んでいきます。

なぜ \(O(N)\) で解けるのか？

連鎖が止まった位置を \(R\) とすると、それより左側のドミノはすべて倒れた状態になります。 次に指で倒すのは、まだ立っているドミノの中で最も左にあるドミノ \(R\) です。

このように、ドミノを左から右へと1回だけ走査（スキャン）していくだけで、すべてのドミノが「誰によって倒されたか」をシミュレーションできます。一度走査したドミノを戻って確認する必要がないため、非常に高速に処理できます。

---

アルゴリズム

ポインタ \(R\) を用いて、現在注目している（まだ倒れていない最も左の）ドミノの位置を管理します。

1. 答えを格納する配列 ans をサイズ \(N\) で用意し、初期値を \(0\) とします。
2. \(R = 0\) から開始し、\(R < N\) である限り以下の処理を繰り返します。
   • 指で倒す処理:
     • ドミノ \(R\) は高橋君が直接倒すため、ans[R] = 0 とします。
     • 現在の起点を表す変数 curr に \(R\) を代入し、ポインタ \(R\) を \(1\) 進めます。
   • 連鎖の処理:
     • \(R < N\) かつ \(A_R < A_{curr}\)（右隣のドミノが手前のドミノより真に低い）である限り、連鎖を続けます。
     • ドミノ \(R\) はドミノ curr によって倒されるため、ans[R] = curr + 1（1-indexedにするため \(+1\) する）と記録します。
     • 次の連鎖の起点とするため curr = R と更新し、ポインタ \(R\) を \(1\) 進めます。
3. すべてのドミノを処理し終えたら、ans の内容を出力します。

具体例（\(A = [4, 2, 5, 3, 1]\) の場合）

• ステップ 1: \(R = 0\)
  • ドミノ \(1\)（高さ \(4\)）を指で倒す。ans[0] = 0。curr = 0 とし、\(R = 1\) に進む。
• ステップ 2 (連鎖): \(R = 1\)
  • \(A_1 (2) < A_{curr} (4)\) なので連鎖する。
  • ドミノ \(2\) はドミノ \(1\) によって倒される。ans[1] = 1。curr = 1 とし、\(R = 2\) に進む。
• ステップ 3 (連鎖判定): \(R = 2\)
  • \(A_2 (5) \geq A_{curr} (2)\) なので連鎖はストップ。
• ステップ 4: \(R = 2\)
  • ドミノ \(3\)（高さ \(5\)）を指で倒す。ans[2] = 0。curr = 2 とし、\(R = 3\) に進む。
• ステップ 5 (連鎖): \(R = 3\)
  • \(A_3 (3) < A_{curr} (5)\) なので連鎖する。
  • ドミノ \(4\) はドミノ \(3\) によって倒される。ans[3] = 3。curr = 3 とし、\(R = 4\) に進む。
• ステップ 6 (連鎖): \(R = 4\)
  • \(A_4 (1) < A_{curr} (3)\) なので連鎖する。
  • ドミノ \(5\) はドミノ \(4\) によって倒される。ans[4] = 4。curr = 4 とし、\(R = 5\) に進む。
• 終了: \(R = 5\) となり、すべてのドミノが倒れました。
• 出力: 0 1 0 3 4

---

計算量

• 時間計算量: \(O(N)\)

  • 外側と内側の while ループの二重構造になっていますが、ポインタ \(R\) は常に右に進む（インクリメントされる）だけで、決して左に戻ることはありません。したがって、配列 \(A\) の各要素へのアクセスは高々数回であり、全体としての時間計算量は \(O(N)\) となり、制約 \(N \le 5 \times 10^5\) に対して十分高速に動作します。

• 空間計算量: \(O(N)\)

  • 入力配列 \(A\) と、答えを格納する配列 ans を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 1-indexed への変換

  • プログラム内ではドミノの番号を \(0\) から \(N-1\)（0-indexed）で管理していますが、出力は \(1\) から \(N\)（1-indexed）で答える必要があります。そのため、連鎖元を記録する際には curr + 1 とする必要があります。

• 高速な入出力

  • \(N\) が最大 \(5 \times 10^5\) と大きいため、Pythonでは sys.stdin.read を用いて入力を一括で取得し、join を使って一括出力することで、入出力によるボトルネックを防いでいます。

    ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = [int(x) for x in input_data[1:]]

    ans = [0] * N
    R = 0
    while R < N:
        ans[R] = 0
        curr = R
        R += 1
        while R < N and A[R] < A[curr]:
            ans[R] = curr + 1
            curr = R
            R += 1

    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    solve()

---

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