概要

\(N\) 個のドミノを左から順に倒していくシミュレーション問題。倒れたドミノを効率的にスキップするために、Union-Find風の「次の立っているドミノ」を管理するデータ構造を使う。

考察

問題の本質

左から順にドミノを指で倒し、連鎖ルールに従って右方向にドミノが倒れていく。各ドミノについて「誰に倒されたか」を記録する必要がある。

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

愚直にシミュレーションすると、連鎖のたびに「次のまだ立っているドミノ」を線形探索する必要がある。最悪ケースでは \(O(N^2)\) となり、\(N \leq 5 \times 10^5\) では TLE になる。

例えば、高さが \([5, 4, 3, 2, 1]\) の場合、ドミノ1を倒すと全ドミノが連鎖で倒れるが、次に立っているドミノを毎回探索していると非効率。

解決の鍵

倒れたドミノは二度と参照する必要がないので、「集合から削除して次の要素を高速に見つける」操作が必要。これはUnion-Find（経路圧縮付き）のテクニックで実現できる。

アルゴリズム

1. next_standing 配列の準備: next_standing[i] = i で初期化（自分自身がまだ立っている）。next_standing[N] = N を番兵とする。

2. find_next(x) 関数: 位置 \(x\) 以降で最初のまだ立っているドミノを見つける。経路圧縮により、途中の倒れたドミノを飛ばして高速にたどり着く。

3. mark_fallen(x) 関数: ドミノ \(x\) が倒れたとき、next_standing[x] = x + 1 とする。次回 find_next で \(x\) を訪問したとき、自動的に \(x+1\) 以降を探索するようになる。

4. メインループ:

   • \(i = 0, 1, \ldots, N-1\) の順に処理
   • find_next(i) で \(i\) がまだ立っているか確認。立っていなければスキップ
   • 立っていれば指で倒す（result[i] = 0）
   • 連鎖処理: 現在のドミノの高さを基準に、次の立っているドミノの高さが真に小さければ倒す。倒したドミノの高さが新たな基準になる

具体例

入力: \(A = [3, 1, 2, 1, 4]\)

• ドミノ1（高さ3）を指で倒す → 次はドミノ2（高さ1）、\(1 < 3\) なので倒す → 次はドミノ3（高さ2）、\(2 \geq 1\) なので停止
• ドミノ2は既に倒れている → スキップ
• ドミノ3（高さ2）を指で倒す → 次はドミノ4（高さ1）、\(1 < 2\) なので倒す → 次はドミノ5（高さ4）、\(4 \geq 1\) なので停止
• ドミノ4は既に倒れている → スキップ
• ドミノ5（高さ4）を指で倒す

結果: 0 1 0 3 0

計算量

• 時間計算量: \(O(N \cdot \alpha(N))\)（ほぼ \(O(N)\)）
  • 各ドミノは一度だけ倒れ、mark_fallen は各要素に対して1回。find_next は経路圧縮によりならし定数時間。
• 空間計算量: \(O(N)\)
  • next_standing 配列と result 配列の分。

実装のポイント

• 経路圧縮: find_next 内で next_standing[x] = next_standing[next_standing[x]] として2段飛ばし圧縮を行うことで、再帰なしでも十分高速化できる。

• 番兵: next_standing の長さを \(N+1\) とし、next_standing[N] = N としておくことで、配列範囲外チェックを nxt >= N の一つの条件で済ませられる。

• 1-indexed 出力: 問題文ではドミノ番号が1始まりなので、出力時に current + 1 とする点に注意。

• 連鎖時の高さの基準: 連鎖では「新たに倒れたドミノの高さ」が次の基準になる点を見落とさないようにする（倒した側の高さではない）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    result = [0] * N
    
    # We process dominoes 1..N in order.
    # For each domino i (0-indexed), if not yet fallen, we push it by hand (result[i]=0),
    # then start a chain: the current domino tries to topple the next standing domino to its right,
    # but only if the next one's height is strictly less than the current one's height.
    #
    # Key insight: when a domino falls, it's removed from the "standing" set.
    # We need to efficiently find the next standing domino to the right.
    # We can use a "next" array (like a linked list / union-find style) to skip fallen dominoes.
    
    # next_standing[i] = the next standing domino index >= i
    # We use path compression similar to union-find
    next_standing = list(range(N + 1))  # next_standing[N] = N means "no more"
    
    def find_next(x):
        while next_standing[x] != x:
            next_standing[x] = next_standing[next_standing[x]]
            x = next_standing[x]
        return x
    
    def mark_fallen(x):
        # Remove x from standing: point x to x+1
        next_standing[x] = x + 1
    
    for i in range(N):
        # Find if domino i is still standing
        pos = find_next(i)
        if pos != i:
            # Already fallen
            continue
        
        # Push domino i by hand
        result[i] = 0
        
        # Start chain from domino i
        current = i
        current_height = A[i]
        mark_fallen(current)
        
        while True:
            # Find next standing domino
            nxt = find_next(current + 1)
            if nxt >= N:
                break
            if A[nxt] < current_height:
                # Topple nxt
                result[nxt] = current + 1  # 1-indexed
                mark_fallen(nxt)
                current = nxt
                current_height = A[nxt]
            else:
                break
    
    sys.stdout.write(' '.join(map(str, result)) + '\n')

main()

---

この解説は claude4.6opus-thinking によって生成されました。