DPできないので

2019年3月26日(火)現在、自分はDPができない状況です。

自分がこれからDPについて色々学んでいって、わかったことや考え方、感想などを、更新する形で書いていきたいと思います。基本的に日記的なのになります。

開始時点でのPocalaのレベル

Educational DP ContestをIまで解説を見ながら通せた

ナップサックDPをよく分かってないけど調べながら通せるくらいの実力です。何も見ずにDP問題を解け、と言われたらよほど簡単じゃない限り、無理です。

3月26日(火)

DPが分からない所を具体的に考えてみた。

自分が「DPできない」と思う理由は

そもそもこの問題がDPで解けるということに気づかない

DPの添字とか全く分かってないので実装ができない

の2つ。

そもそもこの問題がDPで解けるということに気づかない

このムーブメントが多すぎる。

〇〇に合う文字列の数を答えなさい→DFSで全探索できそう

l ~ r までの〇〇の数を何回も答える→累積和が使えそう

〇〇を満たす連続した部分列の中で、最長のものの長さ→絶対しゃくとりだろ

DPが色々なジャンルに応用できることの裏返しかもしれない。

DPの添字とか全く分かってないので実装ができない

そもそもさっきの段階で躓くことが多いんですが、次によくあるのはこれ。

自分「この問題がDPで解ける、というのはわかったんだけど、どうやって実装するの…」

解説「mとnを添え字にして、3次元DPで解けます」

自分「1次元で考えてた…」

こういう風になる。次元が増えてくると、遷移で頭がおかしくなってくる。

で、自分がこの状態を解決するために何を身につければいいか…

「DPのおきもち」を身につける必要がある

NOSSさんがDPのおきもちについて色々言及してくれたので参考にする。

とりあえず1次元DPテーブルを作って、そこから遷移を考えたり状態を加えたりすると考えやすい

多次元というよりはdp［何番目］［状態］で状態の変数がいくつかあるという感じ

DPの条件は問題を小さな部分に分割できてその解から元の問題の解が求められるみたいなやつ

1次元DPを多次元に拡張していく感じ（状態数を増やすイメージ）を掴むことが大切

DPは部分問題に分割でき、区別しないといけない状態が混ざらないように変数（添字）を設定できると解ける

for文を使う時は配るDP、再帰を使う時は貰うDPの方が考えやすい

4月15日(火)

一旦お勉強タイム。

再帰書けそうなパターンだったら再帰→メモ化の流れを使おう、という気分に

4月28日(日)

昨日のABC-D、DPでも解けるらしい

いやどうやったらDPって分かるんだよ…？という気持ちになった

競プロ合宿に向けてDPの練習をしていきます

全探索が（TLEするけど）可能、みたいな時のDPは「まとめて時短」のような考え方をする

5月6日(月)

CPSCO2019が終わった

木DPと対面した。じっくり考察したので、木DPの考え方は分かった。

その頂点を根とする部分木についてのDPとかそういうの。

葉っぱの部分から多分再帰的に更新していく。

でも実装はできない。遷移もできない。

5月30日(木)

既にDPの基本的な考え方というか分類と言うかジャンルは軽く分かった気になっているので、次はDPを何もない所から立てていく練習をしないといけないな〜みたいなことを思ったりしました

7月31日(水)

でも最近「DPやな」とは思えているので進歩してる。

基本的に遷移が上手く生えない時は、一旦制約をぶっ飛ばした状態で考えて、そこから簡単版の制約を足してみて…のように考えるのがやりやすいな、と思いました

11月11日(月)

DPのおきもちみたいなのは分かるようになってきた

状態をまとめる、全探索の必要な部分だけ抜き出す、みたいな

でも、そもそも問題数を解いていない気がしてきた

EDPCもそうだし、問題の数をこなす必要があるなって思い始めた。Codeforcesやるか…？LeetCode？

11月17日（日）

じゅぴろ氏に聞いてみることにした

DPの考え方自体、0から思いつける人は少なくて、過去の解いた問題の中で類題というか「この問題、制約が〇〇だから☓☓DPでは…？」みたいな感じで既にあるテンプレからそれに近いものを選んで実装していく、というのが近いのかもしれない

昨日のABC-Eのやつも、TLで「これまんまARCのおかしじゃん」って言ってる人いたし…。