packer_jp https://blog.hatena.ne.jp/packer_jp/ Australia https://packer-jp.hatenadiary.jp/ 問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_d 解法 高さが同じ列のヒストグラムを考えます。 左の列の塗り方が決まっているとき、その塗り方が赤青赤青……のように交互（以下マダラと呼びます）であれば、右の列の塗り方はそれと全く同じにするか真逆にするかの通りの選択肢があり、マダラでなければ真逆にするしかありません。 これを念頭に置いて、次のDPを考えます。左から列目までを順に決めた時の、列目の下マスがマダラである（下マスはマダラでない）パターン数先ほど述べたことを使い、次のように場合分けして漸化式が立てられます。 の場合 の場合 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpacker-jp.hatenadiary.jp%2Fentry%2F2018%2F10%2F13%2F110443" title="AtCoder Grand Contest 026 D - Histogram Coloring - Australia" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%202 Hatena Blog https://hatena.blog 2018-10-13 11:04:43 rich https://packer-jp.hatenadiary.jp/entry/2018/10/13/110443 1.0 100%