DPの話

この記事はDynamicProgrammingAdventCalendarには関係ありますん。

 

最近DPできないという人が多いので、そういう人々に様々な言葉を投げつけたいと思います。

 

DP(ドッピオ)というのは競技プログラミングで頻繁に使われるテクニックです。日本語では動的計画法(ダイナミックプログラミンッ)です。

DPができない人はN(自然数)種類に大別されます。

第1種DPできないマン(ウーマン):初めてDPをみた

初めてDPを見た人というのは、おそらく競技プログラミングを始めたばかりの方だと思います。これ以前に解いた問題は計算量を考えたりする必要のない問題ばかりでしたでしょう。DPに出会った人々は初めて本格的にTLEに悩まされるでしょう。ソートなんかとはものが違う。累乗を擬似多項式まで落としこむという概念自体が初めてなので、人々はDPで「DPつらい、ちかよらんとこ」となるのです。そもそも入力を保存する以外の用途で配列を確保したりするという発想もまだ無いかもしれません。とにかくまだDPが発想に無いのです。

第2種DPできないマン(ウーマン):解説が読めない

さて、初めてDPに出会った人は悩みます。悩んで悩んでわかりません。わかる人ならできないマン(ウーマン)ではありません。わからないのです。そこで、きっとこの問題は私には無い発想が必要なんだと気づきます。それならばうんうん悩むより解説を呼んで学習するほうが効率が良い、そういうわけで解説を読むわけです。今日では多くの競技プログラマーがブログ等で解いた問題の解説を公開してますから、一つくらいわかりやすい解説に出会うでしょう。

しかしどの解説も読めないという人がいます。それが第2種DPできないマン(ウーマン)です。

この人は簡単です。言葉の勉強をしましょう。日本語じゃなくても英語でも大丈夫です。漸化式とか再帰とかの文字が読めないときは、競技プログラミングよりもっと基本的な何かが抜けているのでググるなどして理解しましょう。

第3種DPできないマン(ウーマン):解説が理解できない

晴れて解説を読めるようになったけれど、なぜそのアルゴリズムがうまくいくのかわからないという人がいます。

その人は数学的センスがありません。数学的センスはごく一部のプロのみが生まれながらに持ち合わせていますが、普通は持っていません。普通の人が数学的センスを磨く方法は一つしかありません。ずばり演習することです。まだDPは解けないので高校数学の確率と漸化式の範囲の問題でもすればよいでしょう。互いに排反であることを意識したり、できるだけ簡単に計算できるように場合分けを考えたりするというのはDPに通じる発想力ですので、やれば絶対にDP力がつくでしょう。それでもダメな人はアイエエエエエ

第4種DPできないマン(ウーマン):実装ができない

経験の問題だ!精進しよう。「精進」というのはひたすら問題を解く苦行のことです。たくさん解けば、いわゆるパティーン(パターン)がわかってきます。2,3重のfor文を書く。変数はちゃんと初期化しないとまずい。初期値は0だったりINFだったり。dp[0][0]だけはじめに適切に設定しないといけない。わざと1-indexにして番兵をつくるとわずらわしい条件分岐がなくなって良い。などなどいろいろなノウハウを精進でゲットしましょう。

第5種DPできないマン(ウーマン):解説記事の筆者の気持ちがわからない

解説も理解できるようになったし、理解した解説をコードに落としこむ事もできるようになったけど、解説なしでは解法がさっぱり思いつかない。どうしてその漸化式が思いつくのかわからない。そういうパティーンの人は競プロ的センスがありません

おそらくこのパティーンの人が一番多いでしょう。競プロ的センスというとやばそうに聞こえますが、今の文脈では「頭のなかで似た既知の問題を探してこれるようなセンス」のことを指すと考えてください。競技プログラミングというのは問題を解く問題を解く競技です。あらゆる特殊な問題を頭のなかで一般化して、できるだけ抽象的な形で引き出せるようにして格納することができるかどうかが大事になってきます。例えば私の個人的な見解として、JOI予選4番は2010年のA FIrst Grader以降、ぜんぶ同じ問題です。i番目までで状態がx,y,z...なときの求めたい値をdp[i][x][y][z]..で管理して、すべての変数について小さい順にループを回すだけ、という点で全部同じ問題です。そういう問題を分類する視野をもてるかどうかが一種の競プロ的センスだと思います。競プロ的センスについても数学的センス同様に演習でつくものですが、ただ精進するだけではだめです。しっかり頭で問題を吟味しましょう。

第6種DPできないマン(ウーマン):蟻本を持っていない

蟻本を読もう!

 

以上です