- 追加された行はこの色です。
- 削除された行はこの色です。
[[プロコン]]
*概要 [#a37a76e9]
-wataさん「マラソンのコツはコードを書かないこと」
高度合成数
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
これが便利らしい
*量子アニーリング [#g59e4123]
-組み合わせ最適化問題の一般的な近似解法
-[[巡回セールスマンを量子アニーリングでpythonで解く>http://qiita.com/ab_t/items/8d52096ad0f578aa2224]]
-量子アニーリングの専用マシン（D-Wave）が存在する。
--量子アニーリングはD-Waveという専用マシンで有名になったわけですが、このマシンは約10億円（推定）はする高価な装置です。
--装置の内部には減磁や冷却のための装置が詰まっていて、絶対零度に近い極低温で動作する超伝導デバイスを守っています。
--超高級な物理実験装置を、組み合わせ最適化問題を解く仕組みとして使う
-量子アニーリングを、パソコンでシミュレーションする方法を量子モンテカルロ法と呼ぶ。
-[[量子アニーリングを機械学習に応用>http://knowledge.sakura.ad.jp/tech/4273/]]
*Kaggleの勝ち方 [#xb35cb15]
-https://codezine.jp/article/detail/9330
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
