Marathon Matchの問題の概説とノウハウについてのまとめ

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

マラソン本、需要があるのは解っているのだけれども、「マラソンマッチの問題を１００問解いた人はいない」って実情を考えると、網羅的にー、ってのは無茶苦茶難しいんじゃないかなぁ、と思ってる。「統計一通りやれ」は間違いなく言えるけど、欲しがってる人はマスターしてるだろうし

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

そもそも自分が感覚派過ぎるからなぁ。むずい。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

蟻本みたいに、１問に付きこれはこうやるーこれはこうやるー、ってやろうとした時に、マラソンマッチだと１問に付き何時間使えばいいのか・・・。Algo系の問題が１問平均１時間程度費やすのに対し、Marathon系の問題は100時間以上だから、割合的に難しいんだよなぁ・・・。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

単に「今までに使ったツール集紹介します！」ならまぁ出来なくはないのだろうけれども、それじゃ多分不十分なんだよなぁ。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

未知の問題と当たっても強い人は安定して強いわけで、ってことはもっとメタな部分を共有するべき。　と思って思考過程と調査履歴、思考ログとかは公開してるけど、そこから何か読み取ってー、というのは不親切過ぎる。んじゃいつもやってる共通部分抜き出せばいいのかー、となると今度は少なすぎる

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

ということで、マラソン本は多分自分は書けないのだけど、ノウハウ共有したい、という意思はあるので、なんか解らんこととか、こういうとこどうやったのとか、そういうのがあればどんどん聞いてくださいな。暫くはそういう形式しか取れないかなー

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

まぁそういう意味で、@simezi_tanとかがやってるMM勉強会は、どういう感じでノウハウ共有していくのがむっちゃ興味あるので、ぜひとも頑張ってほしい。

コルン @colun

まずマラソンの問題分類が、 ・確定完全情報の計算量爆発 ・・手順の探索（指定された探索文脈） ・・組合の探索（自由な探索文脈） ・反復 ・・不確定 ・・不完全情報 ・認識または機械学習 ぐらいしかなくて、認識及び機械学習はTCOマラソンでは出題されたのを見たことがない。

コルン @colun

となると必然的に計算量爆発（探索）または反復の問題の対策だけ行えば、だいたいの問題の対策が行える。 反復の問題は、探索の問題の貪欲版と言える場合が多い様な気がしていて、ある意味で固有の問題は抱えているけれども、基本的には評価関数勝負。 探索の場合も評価関数は含まれる。

コルン @colun

よって、評価関数こそが全てのマラソンマッチ問題の基本と成りうる。 評価関数は、どう合成するか？　みたいな問題もあるけれども、基本的には、どういう部分評価関数を揃える必要があるのか、が重要。 部分評価関数同士が補い合って、潜在し過ぎて全く検知しようがない状態変化を潰すのが重要。

コルン @colun

評価関数をマスターした上で、ようやく探索の問題に入って行く様な気がしている。 探索って何かっていうと、結局シラミつぶしに全パターン探すのが最強なんだけど、そんな時間ないですよ、と。 で、良い組合せの近くには良い組合せがありそう。 良い部分手順の先に良い完成手順がありそう。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

TCOで言うと、TCO2009R1のReliefMapとか、不確定要素の反復といえばそうだけど、あんまりそれっぽくない気がする。等高線の白黒画像が与えられ、各地点の測量が何回か行えるので、等高線画像の各ドットごとの高さを出来るだけ出力してね、みたいな問題。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

問題文はこちらから　http://t.co/qOVx34pyhE

コルン @colun

そういう、良い解の偏りを利用して探索を行って行くことになる。 良い解の偏りが全くない場合には、必然的にモンテカルロ法で時間の許す限り、しらみつぶし探索することになる。 でもそんな問題は出題されない。 そして、偏りを見分けるのが評価関数。

コルン @colun

@chokudai それ不完全情報の反復問題だと思います。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

不確定要素のー、とか適当なこといったけど不完全情報ね。眠くなると日本語適当になるのよくないｗ

コルン @colun

不確定は、情報が入ってくる前段階ではサイコロが振られているのと振られていないことの区別がつかない状態。 不完全情報は、情報が入ってくる前段階でサイコロが既に振られていることの区別がつく状態。

chokudai(高橋 直大)🍆@AtCoder社長 @chokudai

@colun 反復っちゃ反復なんですけど、測量があんまり本質的でなくって（特徴点を調べるだけ）、画像からの復元がメインなんですよねー

コルン @colun

うーん。反復の問題の中には、途中または最後、あるいはその両方で、別途探索を行わなきゃいけない問題も確かにあります。ちなみにTCO11MR1なんかは「呼び出す」形になっていますが、「呼び出す」と「呼び出される」は切り換え方法の違いだけで等価変換可能だったりするので、あれも反復問題。

コルン @colun

TCO11MR1では探索を確かに行うのですが、その探索結果の情報を評価関数に使っていたので、探索行ってるけど評価関数だよなーという認識になってしまっていました。 ただ、TCO11MR1では最終的に探索結果を返さなきゃいけないので、なので反復問題で探索が要らないってのは嘘ですね。

コルン @colun

ただ、反復問題の中には、探索が不要な問題もいくらかあります。 それから、評価関数内で探索を行うパターンもあったりします。

コルン @colun

んで、、、話が本題に戻ります。 探索を行う際に、自由な文脈での探索を行う問題であっても、そこに確定手順みたいなのを見つけ出した方が効率的に探索できるパターンが非常に多い。

コルン @colun

手順探索では、最終的に全てを選択したものが解候補となる。 じゃあ、どういう順番で選択していくのか？　っていうのが、どう探索するのか？　という問題と等価。

コルン @colun

つまり、最終的に選択すべきものを、どれだけ細分化して選択を分離できるか？　を行った後に、どういう順番で選択するのか？　っていうのが、探索で扱うべき１つ目の問題。 ２つ目の問題は、それに合った適切なメタヒューリスティクスを探すこと。

コルン @colun

選択の分離は、コツを掴めば何と何が分離できるかはある程度列挙可能なので、分離を列挙した後で、どういう順番で選択していけば良さげなのかを手作業探索してけば、自ずと適切な探索手順は見えてくる場合が多いんじゃないかと期待できる。