ABC 401-500/ABC438C - 1D puyopuyo - 競技プログラミング用 知識集積所

---

問題

ABC438C

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）※

考え方

ぷよを1つずつ落とし、一番上の4つが同じ色だった場合はそれらをすぐに消す、という貪欲法※でいい。
その実装自体はvectorかdeque※を使えば簡単なので、証明があやふやな状態で一か八かで提出してAC取るのは簡単。
（deque※を使う場合、後ろではなく前から詰めると、if分岐の条件が書きやすくなるかもしれない）

問題は、この貪欲法※が正しい証明が非常に難しいこと。
これは、以下のように証明できる。

あるぷよ列に対し、X以降の4つを消す選択肢とY以降の4つを消す選択肢があったとする。
これが、位置が全くかぶらない場合、Xを消した後でYを消しても、Yの後にXを消しても、結果として得られるぷよ列は同じである。
位置が一部かぶる場合、消すぷよの色はXでもYでも同じはずである。
ということは、Xを消してもYを消しても、同じぷよ列ができる。
従って、どんな場合でも、最終結果に影響を与えないように、好きな位置の4つを消すように順番を変更することができる。
したがって、どこから順に消しても消せる限り消せば最終結果は同じになるため、見つけたところから順に消してももちろん問題ない。

解答例

解答例

注意点

別解