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

コルン @colun

点１を選択→点２を選択→多角形の頂点数Nを選択→（点M∈（点３〜点N）を選択） っていう手順に書き換えることができて、点Mの順番は自由な順番で探索して良いってなる。

コルン @colun

で、これに対してビームサーチなんかを使って探索して良いんですけど……ビームサーチやってる時間もないやって場合には、貪欲法が思いつく。その時に、まぁ空間索引を用いるのはわりと常套手段です。

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

@colun 確かにそうなんですけれども、何で自分は見えなかったのかなー、とか、なんでwataたんは見えたのかー、とかは考えますねー。今同じ問題を解いても、なんかおんなじ嵌り方しそうなんですよねえ、、、。

コルン @colun

後でもう一回、wataさんの解法を読み返そう。。。貪欲で見つける部分はだいたい思考過程も含めて理解したつもりだけど、それ以外の部分がどんな解法だったのかが、そもそも記憶に残ってない。（逆に言うと、そこ以外は感銘を受けなかった。

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

あの問題は、wataたんが貪欲法であっさりと使用する点の候補を決めていたのに対し、自分は枝刈超多めの優先順位付きな深さ優先探索で、点の候補が１つ決まるたびに補正を繰り返して成功率を上げてた。どっちも有効な手段だとは思うのだけれども、どうやったら前者にたどり着けるかなぁ

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

自分はヒューリスティック大量に入れて勝つパターンに慣れちゃってるので、一つ一つの関数が重くなりがちだから、こういうあっさりとした解法って凄く見逃しやすいのだけど、速度を優先したほうが有効な場面ってそこそこ多いので、候補には入れないといけないんだよなぁ

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

２年前のコンテストだし、まぁ反省点は十分上がってるような気がしてきた　コードは読むけど

コルン @colun

たぶん深さ優先探索の時点であんまり良くないって感覚があって、そこをDPやビームサーチに置き換えなきゃいけないって感覚があって。で、ビームサーチの方に置き換えると、あとは貪欲法まで一本道な気がしています。＞TCO11MR2のwataさん解法

コルン @colun

点１→点２→多角形の頂点数→点（N／２）→点（N／４）→点（３N／４）→…… みたいな探索順序も試したのだとすると、角度が分かってなくても枝刈りする指針とかも見えていたはずなので、そうすると全部貪欲で良いや、、、って繋がる様な気もします。＞TCO11MR2のwataさん解法

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

厄介なのが、単にDFSにしていた部分を貪欲に変えるだけだと悪くなって、貪欲にするなら徹底的にそ速度重視にしないとスコアが上がらない点。探索幅を実験して、微妙に戻ることがあるくらいが最適と判断したのだけど、自分のヒューリスティックを殆どそぎ落として高速化するとそこが逆転する。

コルン @colun

ああ、なるほど……メタ探索空間が凸じゃなかったんですね。＞貪欲にすると点数が落ちる

コルン @colun

確かにそう言われると、僕も同じ方針に辿り着けるか怪しくなってきます。

コルン @colun

（怪しくなってくるけど、調査次第な様な気はする。

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

ぶっちゃけこのメンツでこの順位なんだから、自分の解法も十分良いんだろうし、ある種の局地解には達してるんだと思うんだけどなー。　http://t.co/KhMizgWgjV 考察はすれど最後は実験での検証だし、局地解から上手いこと調査して脱出する術を自分はあんまり持ってない気がする

コルン @colun

（最近までマラソンマッチの解法方針候補が点在していると考えて無駄な調査工数を膨大に費やして来たので、このぐらいは列挙可能な気がしてる。＞TCO11MR2のwataさん解 まぁでも、実際に再び直面してみないことには分からないけど。

おたっくす @otaks21

@colun 評価関数内で探索を行うとはどういうことですか？評価関数の中の係数(重み)を変えてみてより良い点数が出るものを探す感じですか。

コルン @colun

@otaks21 いえ。。。たとえばビームサーチとかに対して、＋１手先読みの評価関数を使ったりします。これが劇的なスコア上昇をもたらすパターンがあります。