TopcoderのMarathonMatch138に参加しました。
問題はDiceRoller。変則最長路問題でした。
結果は提出74人中、暫定23位でした。（システスはまだ）
問題
グリッドの各セルに数字が書いてるよ。たまに負数もあるよ。
サイコロを転がして（接地したまま４方向に回転させて）移動して、
底面とセルの値の絶対値が等しければセルの値の得点を得るよ。
始点と終点が隣接してたらループボーナスが出るよ。
あ、ダイス目も自分で決めてね。
考察
とりあえず、これは変則最長路問題。
比例までは行かずとも、まずは経路の長さがスコアに直結しそう。
とはいえ、負数は踏む必要は無いし、1のセルとかも多分そんなに要らない。
最長路を引きつつ、同じ値を同じ面で踏めるようにコントロール…きつくない？
経路を決める時点でダイス目が決まっていないと、評価が難しい。
ダイス目を決める時点で経路が決まっていないと、ダイス目を決めようがない。
ダイス候補を複数持って探索するという方法もあるけれど…。
とにかく探索はめちゃ難。
ループボーナスのために元の場所に戻ってくるのも大変そうだし。
じゃあ焼けばいいのか？というと、
輪を保つことは出来そうなものの、目の管理をどうするのかという問題が。
サイコロの向きってどう管理すれば…あ、24パターンしか無いんですか。
でも差分計算はきつそうだなあ。
近傍は破壊して再構築といういつものAHCメソッドが通用しそう。
うーん、基本焼きなましで、探索もちょっと挑戦してみる感じかな。
探索は明らかに難易度高そうなんだけど、
実は出来ますというパターンが最近多くて微妙な気持ちになっているし…。
実装
サンプルは渦巻らしい。ループしないものの、経路としては最長。
ダイスのシミュレーションはいずれ必要になるし、まずこの渦巻に対して最善のダイス目を求めてみる。42点。*1サンプルが16点で3倍くらい。やっぱり得点の上限は低いっぽい。
これ以上は、面ごとに踏む値を偏らせるか、ループでしか点を上げられない。
ループと言ってもどういう形にすればいいのか。渦巻を二重にしてとりあえず完成。が、これ駄目じゃん。真ん中以外は経路の一部を破壊しても一本道しか空かないから、ほぼ再構築結果が元と同じになる。再構築で変化しやすいよう、長さ20前後？の経路を壊したときのスペースが4x5とか、そんな感じで再構築の余地があると良いかな。でもメアンドロス模様みたいにしちゃうと隣のブロックとの境界が強固…。ん－、大きいジグザグ移動の中で更に小さくジグザグ移動する感じ？
それはそれとして、chokudaiサーチも試してみる。
駄目でした。（2日間ロス）
焼き鈍しに戻る。2日前に考えたパターンを作って64点。更にパターンを見直したり高速化したりで82点。とりあえず爆死回避。
Nの幅が広くて、Excelテンプレ職人になれなくて辛い…。
見た感じ、再構築しようにも空きマスが無くて変化できないというケースが多そう。
kick的なものが無いから局所解にはまってそう。良い近傍に移れる確率がそもそも低いし。
隣り合ったセル間の経路を破壊して空き地にするという近傍を作ってみる。空き地にした後に有効な遷移が続くことがほぼ無く、邪魔をしているだけっぽい。どうすれば…。
では下図のように、初期解の時点で隙間を空けるのはどう？
N=16だけお試しすると、5～10%の改善が出てテンションが上がる。
他のNにも展開すると、何故かスコアが下がる。なんで？
どうやら、ルート再構築のDFSがなかなか終わらずに焼き回数が極端に落ちてしまったらしい。そっちと絡んでくるのか。難しい…。
それはそれとして、高速化に着手してみる。差分計算すれば毎回ルート構築する必要も無いはず！
→差分計算するための膨大なメモリをどうやって高速に初期化するんだい？（1日間ロス）
普段1000msで試しているんだけど、たまに9000msでも試す。すると、どちらでもスコアが変わらないケースが結構ある。局所解で8秒停止は不味い。4秒更新無しでリトライするようにする。ついでに、そのときは初期解を90度回転させておく。
空きマスが無い問題、kick的な空間空けとして、一部破壊して最短経路で結ぶというものを試してみる。僅差だけど改善はした、かな。お守りとして入れておく。
あとは高速化や調整をちまちま。
84点でフィニッシュ。
他の人の解法を見て
・DP
なるほどね（評価出来るかが怪しい）
・再構築時、ダイスの向きが同じになる経路に限定する
それは確かにそう。
以降のルートで目が変わってしまうと直前までの解はほとんど役に立たないし…。
ただ、最初期はそこを気にしないほうがいい可能性もあり、微妙に厄介そう。
・空きマス数を評価
確かにそう。変更の余地が無くて苦しんでいたので、空きマスの必要性は分かっていたはず…。（でも多すぎるとDFSが爆発して死ぬ）
感想
方針空振りを恐れすぎて、自分の走りが出来なくなっているかも。
（競プロ基準で）実装が速い方ではないので、他の方針のお試しに時間を削って、言語も最高速ではないC#、アルゴ力もそこそこレベルとなれば、まあ勝てる道理も無く…。
今は修行期間として色々試してみるにしても、いずれは芯のある走りに戻したいですね…。
*1:得点は終了時のもの。
