Day 151-Q1 | 大洪水法（Great Deluge Algorithm）

問題

数直線上に $N$ 個の地点が一列に並んでいる（1-indexed、地点 $i$ の高さは $A_i$）。地点 $i$ から移動できるのは隣接地点 $i-1, i+1$（範囲内のみ）に限られる。開始地点 $S$、水位下降率 $B$、最大反復回数 $T$ が与えられる。以下の大洪水法の手続きに従って探索し、実際に移動が成功した回数と、探索終了時点の地点・高さを出力せよ。

手続き

現在地点を $\mathrm{pos} \gets S$、水位を $L \gets A_S$ で初期化する。
$\mathrm{it}=1,\dots,T$ の順に：水位を下げる（$L \gets L-B$）→ 隣接候補のうち高さ$\le L$のものを実行可能とする → 実行可能な候補が無ければその場で終了（失敗、成功回数に含めない）→ あれば高さ最小（同点は地点番号最小）へ移動（成功）。

水位が反復ごとに一方的に下がる（＝洪水の水位が上がり逃げ場が狭まる、という比喩）ため、下降率 $B$ が大きすぎると探索はすぐに行き詰まる。

入力形式

N S B T
A_1 A_2 ... A_N

制約

$2 \le N \le 1000$

$1 \le S \le N$

$0 \le B \le 10^4$

$1 \le T \le 1000$

$1 \le A_i \le 10^9$

入出力例

入力例1

10 1 1 5
9 7 8 4 5 2 6 3 9 1

出力例1

1
2 7

概念図：水位の下降と行き詰まり

ヒント（段階的開示）

ヒント1（方向性）

焼きなまし法は「確率」で改悪を受理するかどうかを決めるが、大洪水法は完全に決定的な「水位」という1本の閾値だけで判定する。水位より高い場所には行けない、というルールだけを守って隣接地点を見ていけばよい。

ヒント2（アプローチ）

各反復で水位を先に下げてから、隣接候補のうち水位以下のものだけを候補にする。候補が無ければそこで探索は終わり。「水位を下げてから候補を絞る」順序を間違えないこと。

ヒント3（誘導）

pos = S
level = A[pos - 1]
executed = 0
for it in range(1, T + 1):
    level -= B
    cands = []
    if pos - 1 >= 1:
        cands.append(pos - 1)
    if pos + 1 <= N:
        cands.append(pos + 1)
    feasible = [c for c in cands if A[c - 1] <= level]
    if not feasible:
        break
    pos = min(feasible, key=lambda c: (A[c - 1], c))
    executed = it

模範解答 (Python)

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); ptr += 1
    s = int(data[ptr]); ptr += 1
    b = int(data[ptr]); ptr += 1
    t = int(data[ptr]); ptr += 1
    a = [int(data[ptr + i]) for i in range(n)]
    ptr += n

    pos = s
    level = a[pos - 1]
    executed = 0
    for it in range(1, t + 1):
        level -= b
        cands = []
        if pos - 1 >= 1:
            cands.append(pos - 1)
        if pos + 1 <= n:
            cands.append(pos + 1)
        feasible = [c for c in cands if a[c - 1] <= level]
        if not feasible:
            break
        best = min(feasible, key=lambda c: (a[c - 1], c))
        pos = best
        executed = it

    print(executed)
    print(pos, a[pos - 1])

main()

Step-by-Step 解説

1反復1回目を追う
$L\gets 9-1=8$。pos=1の隣接候補は地点2のみ。$A_2=7\le8$なので移動、executed=1。

2反復2回目で行き詰まる
$L\gets8-1=7$。pos=2の隣接候補は地点1($A=9$)と地点3($A=8$)。どちらも7以下でなく実行可能な候補が無いので探索終了。

3出力を確定する
成功回数1、最終地点2、その高さ$A_2=7$。

4下降率0との対比
$B=0$なら水位は常に9のまま。地点2からは$A_1=9\le9$、$A_3=8\le9$がともに真になり探索は続行できる。下降率が探索の寿命を直接左右することが確認できる。

よくあるミス

ミス	原因	正しい書き方
水位を下げる前に候補を判定	手順の順序を逆にする	「水位を下げる→候補判定」の順を厳守
複数候補で先頭要素を採用	`min`を使わない	高さ最小・同点は地点番号最小の2段階タイブレーク
終了した反復もexecutedに含める	break前にカウント加算	移動が成功した反復のみカウント
範囲外の地点を候補に入れる	境界チェック漏れ	`pos-1>=1`と`pos+1<=N`を確認
確率で改悪を受理してしまう	焼きなまし法と混同	大洪水法は完全に決定的な閾値判定のみ

次のステップ

発展: 下降率$B$を可変にして、探索が$T$回すべて成功する最大の$B$を二分探索で求めてみる。
次回予告: 蟻コロニー最適化（Ant Colony Optimization）

自己評価

完全理解おおむね理解要復習

Day 151-Q1 — 大洪水法（Great Deluge Algorithm）

問題

手続き