paizaオンラインハッカソン・Liteの件－「もしStaticおじさんが反省して動的計画法に挑戦したら」
本当にしつこくも、
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite の件です。
【結果発表】炎上中の20万人月PJを鎮火させた14言語のコード - paiza開発日誌
結果、私のコードが、載せられすぎ。。アカンこれは（汗
9月7日（日）時点、今のところ、Java，Python，Perl，JavaScript，CoffeeScript，VBと鎮火させた14言語のうち6言語が私のものになってしまっています。
前回、Javaが最速の0.01秒にならないと嘆いていましたが、それも掲載されてしまいました。コメントに、「static-OJISAN!!」とか書いたのもそのままです（笑
さて、別に自慢したいわけではなく、逆に嘆いているのです。何を嘆いているのかと申しますと。。リポビタンD×50本があたらなかった。。ではなく、実は私のコードは、データのパターンによっては、最適解でも最速でも無いのです。テストケースのデータのパターンでは、たまたま、正解が出て高速に切り抜けているだけなのです。ということは、解りにくいぶん、これは、二分探索でテストケースのデータを発見する方法より何倍もヒドい（！）のです。（といっても再帰＋枝刈りの考え方自体が間違っているワケでは無く、単純にどこか間違えてて変なことになっている模様。。）
このままでは、無事、テストケースを全部通ってみんな安心しきって、いざ本番稼動となった時点で、はじめて問題発覚して、大炎上するということになってしまいます！
（まぁストーリーに沿うなら、下請け会社を決めるために一度きり使うだけのことなので。。実際のシステムでは無いからいいかーという考えもありかも知れませんが。。）
とにかく、ちょっと、ヒドすぎるな。。と思ったので、もう一度、作り直してみることにしました。本当に本当に本当に私が苦手な。。あの「動的計画法」を使って。（というか、つい最近まで言葉自体知らなかったという。。）
よって、以下、かなり初心者向けです。解っている人は随分イラッとする内容かも知れません。まだ良く解っていない人は一緒に勉強しましょう。
Pythonでしますね。（たぶんPythonを知らない人でも見やすく書けるので。。思い込み？ 私自信もPythonに詳しいわけでもないがなんとなく見やすいと思っている。）
目標は、paiza事務局さんのPython版動的計画法を使った模範解答よりも早くなったらOKということで。（※この模範解答のソース自体は会員にならないと見れません。当然ですが、この解答とは異なった方法で行います。）
http://paiza.jp/poh/kirishima/result/bc6efa98e260eaded5896c3c336dca75
↑ Test Case 7 で、0.53秒。そんなに早く無いですね。。なんとかなるかな？
[1] まずは、最初に再帰の形でシンプルな処理を作成します。
min関数を使って、index番目の下請け会社を入れない場合と入れた場合を再帰的に繰り返して、全パターンを網羅します。人数がm人以上となったときに、0を返したり、一番最後の下請け会社を越えたときに、整数の最大値を返したりしてるのが解りにくいかも知れません。簡単なテストデータを使って、紙に書き出して追えば、解ると思います。（ごめんなさい、こっからが本題なので、これについては細かく説明しません）
KoukiMinoさんの採点結果[71点] まぁだいだいできたかなぁ〜｜paizaオンラインハッカソンLite
Test Case 6 でタイムオーバーです。
[2] [1]のソースにメモを入れて高速化します。
[1]の再帰処理は、全パターン網羅するどころか、深い階層ではすでに以前に処理した同じ計算を何度もしてしまいます。よって、同じ計算を繰り返させないために、計算結果を格納する領域（メモ）を用意します。
関数の引数がindex（現在処理する下請け会社のindex），sumq（それまでに採用した下請け会社の合計人数）となっていますが、これをキーに金額を格納しています。2次元のリスト(配列)でもいいのですが、合計人数側は最初に大きな領域を確保することを嫌って、辞書にしておきました。もし、配列にする場合は、下請け会社の合計最大人数だけの大きさを確保する必要があります。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
一応、Case7まで通ります。Case7は、5秒です。まだ模範解答の10倍くらい遅いですね。
[3] [2]をDPテーブルを使ったループの処理に書き換えます。
[2]では高速化の目的で、memoという格納領域を用意しました。「手段」として導入したものなのですが、動的計画法は、逆で、この「手段」を、「目的」としてしまうのです。つまり、再帰処理の中で作成したメモを、逆から組み立てて、最終的に残った格納領域（DPテーブルと呼びます）の情報より、目的の回答を取得する。ということをします。
と、言ってもそんなに単純では無く、いろいろ苦しむこと数日。。
しかも、ネット上には、すでにあちこちに解答のサンプルがあるため。。
以下の制約を守って、なんとかオリジナルっぽい形にしようと思いました。
・元のメモが辞書を使っているため、DPテーブルも辞書を使う。
・max関数で値を取って最後に引くやりかたのほうが楽そうだけど、
min関数ではじめてしまったため、あくまでもmin関数を使う。
これはヒドい。。（笑
普通、最後の解答がどこか解りやすい場所、配列の一番手前とか後ろとかに寄るはずなのに寄らないし（なので、最後に余分なループで解答を探しに行ってる。。）、とにかく、なんだか見通しが悪い。
min関数も、一応使ってますが、本質的なindex番目の下請け会社を入れるか入れないかの部分は分離してしまっています（笑
いや、でも意味合い的には合っている（と思う。。）。
これで早かったらいいんですが。。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
Case7－6.31 秒 って！！ 再帰＋メモのほうが早いし！
[4] [3]は途中過程です。。まだがんばれます。
幸いにして、本当に幸いにして、実は、この処理においては、dpを1次元にしてもいいのです。[3]のプログラムの流れをじっくり見ると、ループ中のindexの値に依存していないことが解ります。
よって、
dpが1次元（というか単なる辞書のみ）になったことで、それっぽくなりました。元々、index番目の下請け会社を入れない入れるで分離していた箇所も、入れないほうの処理はいらない（dpの状態は現状維持でいい）ので、随分すっきりしました。min関数もこれなら、意味合い的に再帰のときと一致していると言えて、綺麗かと。
たぶん、このような形を、多くの凄いプログラマの皆さんは、すぐ思いつくのだと考えられます。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
Case7－3.30 秒。。まだ道のりは遠いなぁ。
[5] [4]は普通すぎるので工夫していきます。
最初に全社の合計人数を求めておき、下請け会社1社処理するごとに引いておきます。残り人数ということです。nokoriというショボい変数名ですが、解り易さのために、そうしておきました。
このnokoriを、現在処理している人数（key）に足しても、目的の人数mに届かない場合は、問答無用で、そのキーの辞書を消してしまいます。これで、ちょっとは速くなるかと。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
Case7－0.73 秒。。随分マシになってきました。
[6] [5]からさらに工夫します。
人数の多い順にソートして、早くm以上の辞書が出来あがるようにします。
あとは、よく考えたらmin関数にする必要も無いので、それを書き変えました。
まだ、工夫できるかも知れませんが。。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
Case7－0.39秒。とりあえず、模範解答よりも早くなりました。
とりあえず、現時点ではここまで。一応、どれも最適解だと思う。。
[7] これ以上は無理そうなので。。（私の今の実力として無理ということで、たぶんなんか方法はあるっぽい）
とりあえず、元のソースを修正しておきました。
まぁ、横着しちゃダメってことでしょう。。
何故にpaizaさんは私のソースをわざわざ選んだのやら。。
VBはともかくとして、JavaやPython，Perlなど公式の言語だったら、
最速で、かつ、もっとちゃんとしたコードがあったはずなのに。
KoukiMinoさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
とりあえず、同じ0.01秒で。もし、これが最速じゃなかったら、
ショックで倒れるところでしたが、一安心。
