![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
概要 †
高度合成数 https://gist.github.com/pekempey/9eddf9342f65552a92845e035960e8a3 Chokudai Contest 2 これ劣モじゃない？？ 多項式時間で厳密最適解がでる。 http://ibisforest.org/index.php?%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9 近似解法もある。 http://www.kurims.kyoto-u.ac.jp/~takazawa/coss2010/shioura-1.pdf 非厳密DP面白い（Chokudai Contest 1のchokudai解答） 結局、自分が解ける部分問題に落とすパートが強い マラソン感想 ある前提を入れると最適解がもとまる「パスなら…」「左上から右下なら…」 強化学習は人よりかは強くなっても、アドホックアルゴリズムに比べるとね https://topcoder.g.hatena.ne.jp/CKomaki/20141202 Topcoderではtime関数がいみわからんくらい重い ビームサーチ、焼きなまし、山登りを習得するのが基本。 貪欲や山登りを使っている場合は大抵焼き鈍しやビームサーチ等に変えることにより大幅に得点を伸ばすことができます。 大抵「問題のスコアリング + 良さそうな状態にボーナスポイント」という形になります。 やきなまし 診断人さんのマラソン解説 http://shindannin.hatenadiary.com/entry/20121224/1356364040 焼きなましとビーム、どっちを使うべき？ http://qiita.com/takapt0226/items/b2f6d1d77a034b529e21 焼きなましは初期解答が大雑把にきまるとつよい http://topcoder.g.hatena.ne.jp/agw/20141205 コルンさんのマラソンのはなし。テストかけ、テスト300ケースはかけ。プロファイラを使え。プロトタイピングは4時間以内。開発ループを回せ。枝刈りを観測的に行う方法。 http://www.colun.net/archives/294 まず生の点捨をとる。根性が大事。 例えば、最近流行りのビームサーチを例にしましょう。「ビームサーチで200ターンのゲームをする、幅は10000」とかあったとするじゃないですか。これ、「100ターン時点で、50ターン時点の親となるノードは何種類残ってるか」とか、多分みんな調べてないじゃないですか。 そういうの調べれば、「途中でどれくらい偏ってるか」とか、「どれくらい同じノードの情報で埋め尽くされちゃってるか」とかわかるじゃないですか。それをやれば、例えばchokudaiサーチに切り替えたら良さそうとか、もっと別の変則ビームサーチだったり、微妙に焼きなまし混ぜたりとか、色んなバリエーション試せるじゃないですか。こんなんビジュアライズするまでもなく、ちょっとコード書いてデバッガで見るなりprintfで出力してみるなりすれば、すぐに解ります。でもみんな調べてないわけですよ。こういう、「とりあえず今どう動いているか調べてみよう」みたいな気概が大切なんです。ぶっちゃけ、こういうの１個１個やっていくの、超めんどくさいです。めんどくさいけど、「こうなってるといいな」って予想して、「こうなってない」みたいな状態を見つけることこそが、プログラムの改善に繋がるわけですよ。そこら辺手抜いちゃいけない。手抜いちゃいけないけど超根性いる。でも頑張らないとだめ。ってことは、「これを実装してスコアが上がると思った理由」ってのがそれなりにあるはずです。それであれば、「自分はこう思っていたのに、そうならなかった」って発見がこの時点であるわけですね。もうこの時点で十分な収穫なんですよ。「こう思っていた」自体が嘘だった。それが悪い要素だったり、反対向きだったりした。 「こう思っていた」は正しかったのだけど、それよりもっと大きい「こうなってはいけない」要素が存在した 手法だけ覚えてもしゃーないんです。とにかく自分で生のデータを見る。生のデータが良くわからんなら、どうやって可視化するか考える。別に「可視化」「ビジュアライズ」って、絵として表示しろって意味じゃないんですよ。普段プログラム動かしてて見えてない部分とか、そういうのを何らかの形で見えるようにしろって話なんですよ。すっげー泥臭い部分なわけですよ。 http://chokudai.hatenablog.com/entry/2014/12/04/000132 これが便利らしい 量子アニーリング †
Kaggleの勝ち方 † |
