- 追加された行はこの色です。
- 削除された行はこの色です。
[[プロコン]]
*概要 [#a37a76e9]
-wataさん「マラソンのコツはコードを書かないこと」
*詰まったら [#b20c7172]
-考察を丁寧に。得点が増える・増えない理由を、丁寧に考える。
-思考過程をまとめれば、変なのに気付くの自明なので、メモを必ずとる。
-点が平均以下のときは、絶対に簡単な解法を見逃している
*意識すべきこと [#iffc23aa]
-問題をしっかり把握する
-問題をしっかり分析する
--もし特定の条件がなくして問題をシンプルにしたら、厳密最適解はどうなるか、得点が何点になるかを具体的に考える。「自分の解法を真に突き詰めた場合にどこまでスコアが伸び得るか」例えば、
---迷路の壁がなかったらどうするかなど。
---二次元ではなく一次元だったらどうなるか
---上下左右ではなく、2方向しか移動しないことにしたらどうなるか
---盤面を網羅するルートを決め打ちしたらどうなるか
-判断基準を明確にする
--この方針だと何点取れる、という分析を数学的な根拠をもって行う
--この工数の作業をすれば、どのぐらいの順位になるのかの予測をなるべく正確に答えられるように。
--「この方針の長所と短所は何か？」、「この方針が失敗する可能性としては、どんなものが考えられるか？」
--もしダメなら根本的に見直す必要性
-反復期間を短くする
--反復は4時間以内に（実装が難しいなら、100倍ローカルで時間がかかってもよいし、並列化してもよいし、GPGPUしても良い）
-大きいケースと小さいケースで戦略を変える選択肢を持つ
*ビジュアライザ [#w391a545]
-コマンド数計算量を意識する
--入出力が大きいと、原理的にすべての情報を載せられない（2024-masters-qual では出力コマンド数 q=40000、盤面 n=100 に対し、O(qn^2) コマンドが必要になった）。そのため、間引いたり、最後の盤面だけ表示したりする必要がある。
--サイズ数によって出力するものを変えないといけない
-入出力だけでビジュアライザが完成するとは限らない
--途中ビムサが持っている状態のリストだったり、こういう途中状態を可視化することで多様性の確保に繋がる
*貪欲 [#o47d6295]
-大きいケースでは探索が回らないので、丁寧に 1 回だけ貪欲するという選択肢が濃厚になる
--MM94 ConnectedComponents など
--もし時間が余ったら焼くなどする
*焼きなまし [#ldbac605]
-初期解が超重要
--p%の時間を使って生成して、(1-p)%の時間を使って焼く
-操作列の操作がスコアに対してなめらかに影響する場合に有効（途中の操作をほんのちょっと変えるだけでスコアが 0 点になってしまうようなものには向かない傾向）
-重要
--変化させる量が小さすぎるとすぐに行き止まり (局所最適解) に陥ってしまい、逆に、変化させる量が大きすぎると闇雲に探す状態に近くなって、改善できる確率が低くなってしまう。
--反復回数を増やすために、変形後のスコアが高速に計算出来ることが望ましい。
--探索空間は網羅できるようにしなければならない。
**初期解生成 [#yfd6fadc]
-生成の例
--[[AHC009>https://atcoder.jp/contests/ahc009/tasks/ahc009_a]]では、普通に最適経路問題を解けば
-初期解の候補には多様性を持たせる必要がある
--[[AHC009>https://atcoder.jp/contests/ahc009/tasks/ahc009_a]]では、ダイクストラではなく重みを[10,30]でランダムにしたダイクストラを使うことで、多様な解を得ることができる。
**遷移 [#b54650cc]
-操作列の操作
--挿入、交換、rotate、削除など
-効果的な遷移をきちんと考える。
--[[AHC009>https://atcoder.jp/contests/ahc009/tasks/ahc009_a]]なら、確率で止まるのでダブらせるのが強いに決まってる
-
**スコア計算 [#z84192ef]
-スコア計算を軽くすると回る回数が変わるが、それ以前の問題として以下に留意する必要がある
--スコア計算を早くする必要はあるのか？つまり、そもそも回す回数を増やしたら点数を伸ばせるのか？（ローカルで TL を 10 倍に伸ばしたときにどれくらいスコアの上がり具合がどうなるかを検証すればよい）
--スコア計算が重い場合、厳密なスコアではなく近似スコアの計算で事足りたりしないか？
--問題のスコア関数の最大値と、焼きなまし法で使うスコア関数の最大値が一致する必要はありません。最大値をとりうるような状態（argmax）を一致させることが重要です。
---「満足度の最小値 min s(i) 」を、最大化しなさい。だとしたら、愚直にそれを実装するより「スコア＝1番小さいs(i) + 0.0001 * 2番目に小さいs(i)」のほうが探索に向いている可能性が高い
---スコア関数が離散的ならば、そうではなく連続的になるようなものを選ぶと山登りしやすい
-スコア計算の重要なアイディア
--制約がある場合は、制約を満たすようなものだけに遷移するだけではなく、ペナルティを付けることもできる。
---ペナルティをつけた結果、あまりにどの状態もペナルティだらけになるようなら、制約を満たすものだけに遷移したほうがマシかもしれない。
--1変数ずつ焼きなますと早い場合がある
--状態空間が広すぎて収束が見込めない問題では、粒度を荒くして探索空間を狭める（MM92）
--出力順序の前後の差分による、スコアへの影響が異なる場合 (Chokudai Contest 003)
---例1：開始直後は順序関係における頭の部分のみ対象とし、時間経過と共にお尻の方まで対象範囲を広げる。
---例2：順序関係における頭の部分の確率を高くし、お尻の方ほど確率を低くする。
--「スコア変化の無い状態遷移はしない」統計的にスコアへの寄与をプロファイリングして、遷移ごとのスコアの寄与をきちんと考える（注意: 遷移が全状態を網羅していないと局所最適解に陥るので、本当に削っていいのかは考えないといけない）
-温度
--スコア計算が高速になってくると経過時間の取得にかかるオーバーヘッドが無視できなくなってくるため、経過時間の取得と温度の更新は 100 反復に 1 回だけ行う
--温度調整には経過時間 t を開始時刻が 0、終時刻が 1 となるように [0, 1] に正規化して、時刻 t における温度を Tt := T0^(1−t) * T1^t とする指数スケジューリングがよく用いられます。温度 T が高いほど p(∆, T) は大きくなるため、悪化する変形も採用されやすくなり、T が 0 に近づくにつれて指数的に採用確率が低下して山登り法の挙動に近づいていきます。
-多点スタートはあまり良くない
--多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。
--初期解が良くない
*あいまいな問題文 [#o9f7ff42]
-テスタのソースコードに書かれている問題生成手順が、多くの場合、本番でも使われます。
*ビームサーチ [#v64a8933]
-貪欲法っぽく書けば勝手にビームサーチになってくれるライブラリ
*問題解法について [#x18ab6ba]
-大きいサイズと小さいサイズで同じ解法を使うべきかを考える
-評価関数が低い理由を大別して、カウントアップする
高度合成数
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
これが便利らしい
*問題のタイプ [#w94a657c]
-ビームサーチ系
--ゲームの遷移みたいなものがある場合はこういう遷移（DAGっぽいやつ）
-焼きなまし系
--貪欲でいいのなら、焼きなましもやっぱり行けるでしょう
--
*量子アニーリング [#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
*まとめる [#vc16bf81]
これが有効になるのは、「連結性」だったりとか「連鎖」だったりとか、隣り合うものとの繋がりが重要になるケースが多いかな。逆にそういう要素がなければ、手順が限定される必要がないのに順番に埋めてる分、焼きなましにほぼ確実に負ける。
逆にビームサーチ系列は、ターン制ゲームじゃない限り使わない！って人がいて勿体ないなあ、とちょっと思ってる。どうせ最適解が出せない問題だったら、「こういう順番で埋めていく！」って決めてビームサーチ、ってのは、普通に有力な選択肢だよ。埋めた後に補正かけるとなお良い。
Chokudai先生も連結性を問う問題はビームサーチが有効と明言してるのに人々はなぜ焼きなましてしまうのか
gnuplotでhistogramを書くためのいいまとめ
http://www.ss.scphys.kyoto-u.ac.jp/person/yonezawa/contents/program/gnuplot/bar-graph.html
Matplotlibのいいまとめ
http://myenigma.hatenablog.com/entry/2015/08/30/223559
動画的にプロットする方法 matplotlib
http://qiita.com/hausen6/items/b1b54f7325745ae43e47
http://hakomof.hatenablog.com/entry/2017/08/24/195537
評価関数はO(S2)だがy_kawanoさんがchokudai contest（本問題と似ていて連結数を大きくする問題）で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝
かぐるのslack
https://twitter.com/tkm2261/status/899987496443887617
GNU parallelの良いまとめ。
https://www.slideshare.net/koji_matsuda/gnu-parallel
hakomoさん、MMで最小費用流を使ってる…
http://hakomof.hatenablog.com/entry/2017/05/25/232039
部分問題として厳密解が（何らかの理由によって）求められないとき特に悩む。厳密解が求まらない以上どんな実装をするかで何(が/を)犠牲になるのかが変わるので、その選択に自信が持てないことが多い。全体方針とのバランス結構難しくてわからない
hakomoさん、MMでセグ木も使ってる…
http://kurenai3110.hatenablog.jp/entry/2017/05/05/124133
hakomoさん、今回のMMでも永続UnionFindを使ってる…
http://chokudai.hatenablog.com/entry/2017/05/01/231825
https://www.slideshare.net/yowaken/topcoder-marathon-match-92-lighting-yowa
自分はスコアに対して温度管理をするのではなく、温度と連携させるのは速度という形で焼きなましを実現した
例えばchokudaiサーチに切り替えたら良さそうとか、もっと別の変則ビームサーチだったり、微妙に焼きなまし混ぜたりとか、色んなバリエーション試せるじゃないですか。
めんどくさいけど、「こうなってるといいな」って予想して、「こうなってない」みたいな状態を見つけることこそが、プログラムの改善に繋がる
「スコアが上がらなかったら捨てる」と言いました。まぁこれだと勝てません。「こう思っていた」自体が嘘だった。それが悪い要素だったり、反対向きだったりした。
「こう思っていた」は正しかったのだけど、それよりもっと大きい「こうなってはいけない」要素が存在した。
前者の時は、「これは嘘だったから、意識しないで良い」って思えるし、運が良ければパラメータ反転させるだけでスコア上がったりします。こっちはそんなに嬉しくない。逆張り…
https://www.slideshare.net/kazumamikami1/88-54397136
前の行動が影響する無茶振りにはビームサーチが便利
Beam searchは
貪欲法である程度良い解が出せるが、最適な解が出せない、というような問題に対し、手軽により良い解を見つけることが出来ます。
ビームサーチでは、評価値の上の方のものから採用していきます。すると、似たような状態だけどちょっとだけ違う、というのが大量に発生してしまいます。これだと、ビーム幅が広くても、様々な局面を探索することが出来ません。
ここで、chokudaiサーチを使うと、「先行してあんまりよくなかった結果」と「後から見つけてとりあえず良さそうな結果」の両方が探索されます。ざっくり見積もって、ビーム幅Kだと、logK種類くらいの結果がそこそこ探索される感じになります。ビームサーチだとこれが1種類になりがちなので、悪いパターンにハマってしまうことが多いです。
chokudaiサーチでは、多様性が生きない場面だと、単純に悪くなることが多いです。多様性が要らない場合は、chokudaiサーチの最初の方の探索は純粋に無駄になります。隠しパラメータ、評価のラグの時定数が大きかったり多かったりするばあいは、chokudaiサーチのほうが良さそう
上位陣はビームサーチだそうです。「2つの操作の間で依存関係が強いから」だそうです。納得
その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。
近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている
2年前に想像していたよりずっとずっと高温からスタートし、そして局所解になってすらいない様な中途半端なところを行ったり来たりしながら、温度が下がっていくことで移動可能な範囲が狭まっていくが、その間、より大局解に近い領域を高確率で選び続ける。
焼きなましは正直あんまり使ったことがなかったのだけれども、この間、大学院の後輩の焼きなましに関する説明を聞いてからは、根本的に焼きなまし法は凸凹している広域の探索には向かないんだなと思った。
焼きなまし法は、大局的な凸、中曲的な凸、消極的な凸が、フラクタルっぽく重ねあっている時に使えるらしい
これは、「温度変化でしっかり冷ましていけば、ランダムな動きでもある程度良い方向行けるでしょー」みたいな甘えが生み出すもので、最後の方はある程度やっぱり貪欲とか混ぜて、しっかり深いところまで見に行く動きを入れないとうまくいかないこともしばしば。とりあえず、よほど探索空間が焼きなまし法に向いていない限りは、致命的な欠陥がある探索法、という理解を僕はしている。
あまりにトゲトゲしている場合は、ちゃんと一旦底まで降りてあげるような動きを積極的に入れてあげないと上手くいかないことが多い。
そもそも「全体を包むおっきいお椀」というのが存在しなくって、色んなところにそこそこの解があるやつ！ こういうのは焼きなましでやること自体が悪い。多点スタートでどうにかしよう。短い時間である程度の解を出して、一番良いところを見つけたら潜ってく、みたいな感じ
。「距離が近いことと、スコアの期待値にどう相関があるのか？」が、まぁ、探索空間の形
自分の場合はまず「近傍」というものを作りやすいかどうか（2点スワップすればいいじゃんとかそういうの）を見てる
あとはまぁ根本的な話として、「評価を差分で高速に取ることが可能か？」って焼きなましにおいて超重要なところ
やきなまし
http://shindannin.hatenadiary.com/entry/20121224/1356364040
http://www.colun.net/archives/774
ちょくだいさんの具体例を含んだ焼きなましの「解空間」の話
https://togetter.com/li/607979?page=2
valid pathを全部表示するくらいのビジュアライザは作るべきでした (上位陣はほとんど作ってた)
https://topcoder.g.hatena.ne.jp/CKomaki/20141202/1418158488
質のよい乱数大事
C言語のrand()は遅いので、高速なxor128を使いましょう。
前回サブミット時の結果と比較する
マラソンの感想
http://d.hatena.ne.jp/wata_orz/20100805/1281000288
http://topcoder.g.hatena.ne.jp/shindannin/20110601/1306944431
ただ、多点スタートで結果がよくなるケースは、そもそもスコア関数や近傍が良くないので、そこを見直したほうがよいかもしれません。
短時間系コンテストとの関連
MarathonがSRMなどの短時間系のコンテストと全く違うのが、「最適解じゃ無くてもよい、というか最適解とか無理」という部分だと思います。
「ちゃんと良い解を得るにはどうすれば」とあまり深く考えていると、手が止まってしまって先に進まなくなりがちです。
SRMのレーティングは高いけれどもMarathonは苦手、という人は、このあたりで引っかかってるんじゃないでしょうか。
逆に、短時間系のコンテストで使うようなアルゴリズムは知らないでいいかというとそんなことはありません。
解答の一部にDPが登場することはよくありますし、探索や最短経路も頻出です。
事実、日本からの参加者をMarathonレーティング順で見ていくと、上位18人までがSRMのレーティング黄色以上、うち11人が赤経験者です。（2012-05-02現在）
https://www.otinn.com/groups/view_group.php?gid=1376&sort=14
Greedyは強い
「Marathon何やったら良いかわからない」という人には「とりあえずGreedyで」と言っています。
もちろんそれだけで上位は取れませんが「この方針でこんなにスコア取れるのか」とびっくりすることは多いです。
ランダムは強い
上に同じ。
せっかく制限時間が10秒・20秒とあるのだから、計算パワーをめいっぱい使ってあげましょう。
逐次的に改善できるか
要は焼きなまし・山登り。この形にできるかどうかが大きな分かれ目になります。
焼きなましが有効であることが明らかな問題はみんなそれをやってくるので、そこまでたどり着いていなかったら勝負から蚊帳の外な感じになってしまいます。
焼きなませることが自明ではない場合にも、うまく状態の近傍を設計して逐次的改善が可能な形にできると強いです。
探索空間の削減
単純化して言ってしまうと、Marathonの問題というのは「ものすごく大きな探索空間から、いかに良さげな解を持っていそうなところだけを探れるか」です。
そこで、探索空間を減らすため、一部のパラメタを決めうってしまったり、嘘枝刈りを入れたりします。
この"嘘"の加減が重要なのですが、そのあたりが職人芸になる部分でしょうか。
巡回セールスマンはLKHが早い。1700頂点20秒0.5%誤差。
https://www.google.co.jp/search?q=Lin-Kernighan+heuristic%E3%80%80%E5%AE%9F%E8%A3%85&oq=Lin-Kernighan+heuristic%E3%80%80%E5%AE%9F%E8%A3%85&gs_l=psy-ab.3...3216.6079.0.6310.8.8.0.0.0.0.153.858.3j5.8.0....0...1.1j4.64.psy-ab..3.1.105...0i30i19k1.RMxlmavYZ4c
Zobrist hashというのがかなり強いらしい
今までに見た盤面を入れないというだけなのにめっちゃ探索の幅が広くなったらしい
*Zobrist hash [#ae130e3c]
-今までに見た盤面を入れないというだけなのにめっちゃ探索の幅が広くなる
-盤面(i, j)にxがあることに対してh_{i, j, x}というrandomな値を割り当てる。すると、全部の盤面の状態をそのxorで表せる
--これによって、盤面のhashの差分を取ることが出来る
--とりあえず重複探索は簡単に避けることが出来る
*PTAS [#z272bfa2]
-少しのエラーを許すことで動的計画法をとてもパラレルにするという論文です。おそらく明日のいつかの時点からダウンロードできるようになると思います。この論文はどの程度面白いのか(重要なのか)自分は判断しかねます。他の論文は
--http://acm-stoc.org/stoc2017/toc.html
*PTAS [#z272bfa2]
-少しのエラーを許すことで動的計画法をとてもパラレルにするという論文です。おそらく明日のいつかの時点からダウンロードできるようになると思います。この論文はどの程度面白いのか(重要なのか)自分は判断しかねます。他の論文は
--http://acm-stoc.org/stoc2017/toc.html
*機械学習の利用 [#x61e1653]
-マラソンのハイパーパラメータチューニングをベイズ推定でやったり、SVMでケースの特徴量を得て優勝
--https://www.slideshare.net/YukiYoshida11/atcoder-2nd-yosss-84017362
*遺伝的アルゴリズム [#g9d6c96d]
-『今日は脳みそがついていないなあ』という気持ちの時にパパっと作るパフォ低い脳死アルゴリズム
-ちょっと脳みそがついているハムスターは、遺伝的アルゴリズムが本当に最適設計解になるケースは、入力構造の多様性が尋常ではなく設計者すら把握できないような場合だと思っている
*MIP [#c66d074f]
-koyumeishiさんはpythonのfrom ortools.linear_solver import pywraplpなるものを使ってマラソンに対して最適解を出していたらしい。
--https://gist.github.com/koyumeishi/1dc332012cf875f7892844ddf17a5274
*FPT [#efec4835]
-最大独立集合、誤差指定してo k^4
--IBM Cplexクソ早いらしい
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
