脳log[20220705]

2022年07月05日 (火) [AtCoder] 精進。ABC133-D「Rain Flows into Dams」(緑 diff 下位)。水になるかならないかの頃に緑はほぼ埋まっていたのだけど、埋めきれずに残っている 10 数個のうちのひとつ。どれも一度は解こうとしたことがある。■提出 #33008639 (AC)。一端を決め打つ DP かなとか、値の１つが取り得る値を二分探索かなとか予想しながら問題文を改めて読んでみたら、階差数列で初期値の増減がジグザグに波及するので両端のつじつまを合わせましょうね、という問題だった。階差数列で解くのは何度か経験があるし、とくに先月(20220612) Lucky Number を解いたあとに読んだツイートによって階差数列とジグザグが結びついていたので、問題の構造がすごくはっきり見えた。今が解くのにちょうどいい時期だったのだ。