マラソンマッチ談義

しめじたん（レベルを上げてコミュ力で殴る @simezi_tan

あとマラソンはノウハウと勉強方法が浸透してなさすぎて手をつけにくいと言うのもあった。2週間、時間を費やしてマッチして、成長のノウハウがないから何も実力向上しないとかなったら嫌だと思っていた

しめじたん（レベルを上げてコミュ力で殴る @simezi_tan

マラソン版蟻本みたいのがマジで待たれる。出たら多分、頭の良さじゃなくて長期開発のノウハウだけである程度戦えている社会人MMerとか(もちろん赤は別)はうちの学科のめちゃ頭いい学生たちに一瞬で抜き去られるはずである(過激発言

しめじたん（レベルを上げてコミュ力で殴る @simezi_tan

まあそんな本が出るわけないので、自分で勉強会を開き、定石を共有して整備しようと言う訳である。(結局前回の反省会やらずにR3始まってしまってごめんなさい)

しめじたん（レベルを上げてコミュ力で殴る @simezi_tan

@choku_key_dai ごめんね。特定の誰かに文句言ったわけじゃなくて、幅広いノウハウを網羅的に凄く良くまとめた蟻本みたいなのが出るのを期待する、受け身の態度よりも自分から動きましょうね的な意味です

しめじたん（レベルを上げてコミュ力で殴る @simezi_tan

@choku_key_dai 出したら絶対買うので待ってます

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

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

コルン @colun

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

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

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

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

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

コルン @colun

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

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

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

コルン @colun

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

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

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

コルン @colun

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

コルン @colun

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