yukicoder No.314 ケンケンパ - はむ吉（のんびり）の練習ノート

この記事では、私がNo.314 ケンケンパ - yukicoderに取り組んだ際の試行錯誤について詳しく述べるとともに、競技プログラミングにおいてよく用いられる技法である動的計画法の基本について考えます。

はじめに

私は2015年9月に競技プログラミングというものを知り、以後yukicoderやAIZU ONLINE JUDGE: Programming Challengeをはじめとするオンラインジャッジで練習しています。数年前から主に趣味としてプログラミングを行ってはきたものの、アルゴリズムに関する知識はあまりありません。そのため、yukicoderでの★2レベルに相当する問題が解けたり解けなかったりするという状況です。動的計画法については、重要な技法であるとは認識しているものの、いまだに理解が不十分であるように感じます。

動的計画法とは

問題に触れる前に、動的計画法の概要について述べておきます。wikipedia:動的計画法によれば、動的計画法は分割統治法とメモ化を用いたアルゴリズムの総称であり、その実現方法としては次の2種類があるとのことです。

履歴管理を用いるトップダウン方式：再帰を利用する場合にはメモ化再帰とも呼ばれる
ボトムアップ方式

私が競技プログラミング関連の解説をいくつか読んだところでは、特に後者の、ボトムアップ方式の動的計画法を指して動的計画法と呼ぶことが多いように感じました。これは狭義の動的計画法とでも呼べそうです。

注意

以下には、No.314 ケンケンパ - yukicoderに対する解法および解答例が記載されています。

問題文の要約

「ケン」と「パ」を繰り返す、長さ $N\:(N\in\mathbb{N},\,1\le N\le 10^6)$ のケンケンパコースを作る。ただし、「ケン」は3回以上続いてはならず、また「パ」は「ケン」の後にしか置けないものとする。このとき、可能なコースの数 $a_N$ を $M=10^{9}+7$ で割ったあまりを求めよ。

漸化式の作成

最初の小さな $n$ に対する $a_n$ は、以下のように樹形図を描くことで求められます。これから推測すると、 $a_1=1,\,a_2=2,\,a_3=2,\,a_n=a_{n-2}+a_{n-3}\:(n\ge 4)$ という式が成り立ちそうです。サンプルとして示された値はいずれもこの式を満たしています。それゆえ、どうもこの式は正しそうです。
f:id:hamukichi_nbr:20160110162832p:plain

なお、私がこの問題を最初に見たときには、書き出しはしたもののなぜか樹形図の形にはしなかったため、法則性を見つけることができず、安易に解説を読んでしまいました。

動的計画法を用いた答案

メモ化再帰（トップダウン方式の動的計画法）による答案

最初に作成したのが、以下のようなメモ化再帰による答案*1でした。

しかしながら、このコードはテストケースchallenge01.txt ( $N=983039$ )に対してRuntime Errorを発生させてしまいます。これは、スタックの深度が大きくなりすぎ、Recursion Errorが起きるためです。コード中に示したように、sys.setrecursionlimitにより深度の上限を上げることは可能です。とはいえ、あまり上限が高すぎると、クラッシュしてしまいます。いくつかの値を上限として試してみましたが、結局これらの不具合を解消することはできませんでした。

今度は、メモ化の処理を自分で書くのではなく、以下のようにデコレータ@functools.lru_cacheに任せてみました。しかし、やはり上述の理由でRuntime Errorが生じ、これを解決することはできませんでした。

ボトムアップ方式の動的計画法（狭義の動的計画法）による答案

そこで、以下のように、ボトムアップ方式の動的計画法を使ってみました。すると、challenge01.txtが与えるような大きい $N$ に対しても正答でき、Acceptedを得られました。また、コードもいくぶんすっきりとした見た目になりました。

また、C++の練習を兼ねて、同様のプログラムをC++でも作成しました。

疑問点

漸化式の立て方

私は、上図のような樹形図を描き、その結果から帰納的に漸化式を立てましたが、この方法が適当なのかは不明です。ほかの方による解答をいくつか読んだところ、違う漸化式を用いているものが多く見られたのが気になります。

Haskellでの動的計画法

競技プログラミングでHaskellを用いることはあまりないかもしれませんが、（最近の）Haskellでは動的計画法をどのように書くのでしょうか。ただ、これについて考えるのは、動的計画法やHaskellの訓練をもっと積んでからのほうがよいのかもしれません。

おわりに

いくつかの疑問点は残ったものの、とりあえず動的計画法を用いて解答することができました。動的計画法をはじめとするアルゴリズムに関する学習を進め、より多くの問題を解けるようにしたいところです。

*1:実際に提出したものを整理した上で、コメント等を追加したものです。これより後のコードについても同様です。