書かないにしてはやりすぎたので。
ABC145 F Laminate
解説AC。DPにすればいいということと添字に削除した列をもたせると良いという情報を予め知っていたのでうまくやろうと考えたが失敗。
漸化式でやろうとするとハゲるのでメモ化再帰っぽくやるといいらしい。実際ハゲたので
やっぱりどういう場合にメモ化再帰を使えばいいかわからない。
AOJ 1635 計数カウンタ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1635&lang=ja
2019年国内予選D。類題らしいので解いた（なぜすぐに解き直さなかったのですか？）
上の問題に目を通していれば、カウンタを押す作業の最小回数というのは列を塗る回数とほとんど同じ操作なのだろうということが推測できる。ある範囲において上の問題で列を塗ることとある範囲でカウンタをまとめてインクリメントするのは、塗る高さが1で固定なので実際同じである。
したがって似たようなDPが適用できるが、こちらは列の削除ではなく列の高さの変更なので、この情報を先とは異なる方法でうまく持たせてやる必要がある。単純にはdp[i][j]としてdp[i][j]:=i番目の列の高さは(b[i]-a[i])+m*jのようにすればよい（実際には0未満にならないように気をつける）。あとは同じようにする。jをどこまで持たせるかが悩みどころだが、これを2として提出するとWA。テキトーに増やしてジャッジデータ眺めてもなかなか収束してくれない。
列が全体で大きな山型（上に凸）になるケースが最悪で、このときの高さはだいたい500*mぐらいありそうだということが分かった。怖いのでj=1000とすると、dpテーブルの更新が全体でO(N3)となり間に合わない。しかし、よく考えるとある列の高さを固定したとき前後の列はその列となるべく高さを合わせたほうがよいだろうという予測ができ1、それに合わせて書き直すと全体でO(N2)となり間に合う。
参考
厳密な証明を与えていますが、少し理解に及びません。
これ解けなくても仕方ないという評価だったけどこうやって見ると典型な気がしてきた。
-
誰か厳密な証明してください。。。っ参考リンク↩
