DP雑記⑥ - ぺんぎんメモ

Convex-Hull Trickについては理解したけど、DPの遷移式をどのように変形するかがわからない。そこで、問題にあるタグ「Monge」で検索すると、何だかそれらしい情報がヒットする。しかし、これについても結局よくわからなかった。

Mongeを知っていく過程でこちらの問題を解いてみたけど、いまいち腑に落ちなかった。というか、使える場面が限定的すぎる気がする。現段階での僕の認識は「区間DPのO(N³)をO(N²)に落とすテクニック」であり、他のケースにうまく応用できる気がしない。

とはいえ、「DPテーブルを斜めに埋めていくと、区間DPの区切り位置を端から端まで試す必要がなくなる」というのは勉強になった。

Convex-Hull TrickとMongeについてはこれくらいでいいかな。

ということで、引き続きDPの問題を解いている。解いた問題は以下。

「既に選ぶピザが決まっているとき、価格の高いものから順に有料→無料→有料→…というように交互に選んでいくのが最善」の証明ができなかった。無念。

Convex-Hull TrickとMongeのタグがついている問題。DP遷移式の変形がわからない。

ずんだ餅を食べたかどうかを状態として持って左からDPしていく。制約が大きくて解法が限られてくるのが考察の助けになった。

問題文そのままの操作順序では解くのが難しそうだったので逆順にした。初期状態は2人合わせてN回飲酒した状態、そこから1回ずつ飲酒回数を減らしていく。まだ解いていない問題のうち、最も難易度が低い問題を解く、という操作を繰り返す。

ひとつわかるのは、下の桁から見ていったとき、初めて1が現れた場所では必ずどちらかの操作をしなければいけないということ。そしてこの操作は、それより上の桁にのみ影響を与え、下の桁には影響を与えない。よって、下の桁からDPするのが良さそうだとわかる。

連続部分文字列と聞くと以下のイメージを思い浮かべる。

f:id:penguinshunya:20200126104229p:plain

範囲の右側を固定したときに、左側を効率的に数えられないかを考える（愚直に数えると全体でO(N²)になって間に合わない）。こういったとき、prev(c, i)やnext(c, i)を定義すると、左側の数を効率的に数えられることが多い気がする。実際この問題でもその方法で効率的に数えられる。

面白い状態の持ち方をする。dp[i][j]のjを「iに線を引いたかどうか」と定義する。こうすることで、遷移がうまく書ける。

累積和やnext(c, i)などもDPの一種ということに改めて気付かされた。この事実はけっこう忘れがち。