GCJ2012 Round 1C Problem C. 解き方

Google Code Jam 2012 Round 1C
Problem C. Box Factory 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

箱のラインとおもちゃのラインがそれぞれどこまで進んでいるかのインデックスを持ち、再帰で全パターン検証するベタな方法で解きました。（ベタだと思います。これ以外思いつかなかった…）

箱とおもちゃが同じ種類の場合は作れるだけ作ります（箱の残り数とおもちゃの残り数の少ない方に合わせる）。使いきったラインはインデックスを進めます。使いきらなかったラインは「いくつ使ったか」を記録しておきます。（流れてくる数 - 使った数 = 残り数）

次に「箱のラインを進めた場合」と「おもちゃのラインを進めた場合」を再帰して、より多く作れた方 + 自分が作った数 を返します。この先最大いくつ作れるか、を示しています。（インデックスを進めたときは 使った数 を0に戻さないといけないので注意）

これだけでは特に Large のとき時間がかかりすぎてしまうので、再帰関数の結果（この先最大いくつ作れるか）をキャッシュしておきます。
「箱のラインのインデックス」「今の箱をいくつ使ったか」「おもちゃのラインのインデックス」「今のおもちゃをいくつ使ったか」の4つの数字の組み合せ次第で結果が変わるので、この4つの数字をキーとして関数の結果をキャッシュします。関数の先頭でキャッシュを調べて既に結果があればそれを返すのでもう一度再帰する必要がありません。キャッシュがとても効果的に機能します。