競技プログラミング初心者の方が動的計画法(DP)を勉強するのにお勧めの問題があります。AtCoderで開かれた「Typical DP Contest(tdpc)」です。2013年8月と結構昔に開催されたのですが、今でもたくさんの方が解いています。
このコンテストは、そもそもが「動的計画法の練習をすることを目的」として開催されて、「出題される問題はすべて(他のコンテストで使用できないほど)典型的なDPの問題です」とあるように、ちゃんと理解してみるとDPに関する典型的なテクニックをたくさん学べるとてもいいコンテストだと思います。ただ、難易度は高くて(TopCoder SRM d2 hard程度のものが多いとのこと)、初心者にとってはハードルが高いです。作者の方が一言ヒントをつぶやかれたり、いろいろな方がブログで解説を書かれていますが、一回読むだけではなかなか理解するのが難しいものが多いです。
そこで、競技プログラミング初心者の人にもわかりやすい解説を目指してこのブログを作成しました。もしわかりにくいところなどがあれば指摘していただけるとありがたいです。
また、自分にとってわかりやすかったと思われる他の方のブログも紹介させていただきます。あくまでも私にとってわかりやすかった記事ですので、そのほかにもいろいろ検索して勉強することをお勧めします。
問題 | 概要 | 解説ブログ |
---|---|---|
A コンテスト | 基本的な2次元のDP | Grenache |
B ゲーム | ゲームの最善手 | Grenache kagamizさん |
C トーナメント | 確率 | Grenache simeji_tanさん |
D サイコロ | 確率、4次元のDP、素因数分解 | Grenache kmjpさん |
E 数 | 組合せの数、桁DP | Grenache kmjpさん tshitaさん |
F 準急 | 組合せの数、累積和 | Grenache mayokoさん |
G 辞書順 | 組合せの数、文字列の部分列 | Grenache simeji_tanさん osakさん |
H ナップザック | ナップサック問題の変形、最大値 | Grenache kagamizさん kmjpさん |
I イウィ | 最大値、文字列 | Grenache osakさん ??? |
J ボール | 期待値、bitDP | Grenache kagamizさん |
K ターゲット | 最大値、LIS、幾何 | Grenache kmjpさん |
L 猫 | 和の最大値、累積和 | Grenache simeji_tanさん kmjpさん |
M 家 | 組合せの数、巡回セールスマン問題(TSP)、 bitDP、行列累乗 | Grenache simeji_tanさん |
N 木 | 組合せの数、逆元、パスカルの三角形 | Grenache kmjpさん simeji_tanさん |
O 文字列 | 組合せの数 | Grenache simeji_tanさん hadroriさん |
P うなぎ | 組合せの数、木構造 | Grenache osakさん shifthさん |
Q 連結 | 組合せの数、文字列、配るDP | Grenache osakさん shifthさん |
R グラフ | ||
S マス目 | ||
T フィボナッチ |
まだすべての問題を解けていないのですが、解けたらブログに書きたいと思います。