みなさん、こんにちは。パークガイドのミライです。
先日行われた『DPまとめコンテスト/Educational DP Contest』、通称EDPCの解説を競プロフレンズのみなさんに書いていただきました。
個別の解説に入るまえに、解説の中で登場するコードについて注意をいくつかしておきます。
・解説で使われるコードはC言語で書かれたものです。
・入出力は省略しています。入力で与えられる配列は入力例にならい1-indexedです。
・DP配列は0で初期化されています。
・次の5つのマクロが定義されています。
#define rep(i,l,r)for(int i=(l);i<(r);i++) #define max(p,q)((p)>(q)?(p):(q)) #define min(p,q)((p)<(q)?(p):(q)) #define INF ((1LL<<62)-(1LL<<31)) /*オーバーフローしない程度に大きい数*/ #define MOD 1000000007
repが半開区間になっていること以外は自然なものだと思いますので、混乱はないと思いますが注意してください。
それでは解説をどうぞ。
EDPC解説 A～E (入門編) アライグマさん
EDPC解説 F～L (基本編) サーバルさん
EDPC解説 M～T (応用編) カラカルさん
EDPC解説 U～Z (発展編) フェネックさん
さて、せっかくなので私も「DPとはなにか」について話してみましょうか。
これにはさまざまな宗派がありますが、私は「ある問題を部分問題に分解し、それらの解を用いて元の問題に答える手法」だと考えています。
簡単にいうと「困難は分割せよ」ですね。この考え方は実装するうえではもらうDPやメモ化再帰との相性がよいです。
「何を状態として持つか」が「どのような部分問題に分解するか」と対応し、「状態遷移がどのようになっているか」が「部分問題の解から元の問題の解をどうやって得るか」に対応しています。
この考え方だけで基本的なDPの問題は多くが解けるようになるので是非覚えてくださいね。
