TCO18 MM R2 - CrystalLighting

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

Obstacleの実装が終わったのが24時間前、Mirrorの実装が終わったのが3時間前だから、まぁこれは無理ですね・・・。

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

Mirrorに関しては未だに１％くらいの確率でバグって異常終了するので、何かしらおかしいしちょっとどうしようもない・・・。

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

今回は実験的に１からC++で書いてみたんだけど、やっぱ初手C#にしないと大惨事が起こるということが分かりました＞＜

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

ちなみにやったのはただの焼きなまし。ちょっとバグりにバグってそれ以上のことをする余裕がなかった。

nico_shindannin（診断人） @nico_shindannin

ちなみに、今回は、自分自身に負けたかんじじゃ…。日曜日、焼きなましの差分実装が今回は億劫だなぁと思ってゴロゴロしているうちに、丸一日棒に振ってしまった…。

nico_shindannin（診断人） @nico_shindannin

どうデータ構造持つのがいいのか、いまいちな方法しか思いつかず、さらに「おっくう度」が高まった気がする。焼きなましの評価関数も、なんの工夫もないベタのやつで終わってしまいました…。

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

滑らかに遷移するように評価関数とか上手く作るとかその水準に達していないので、「スタートラインに立つ前に競技が終わった」って感じだ・・・

Leonardone @neetsdkasu

今回はダメすぎて、ヴィジュアライザぽいやつ作るくらいしかしなかった（これ1stのサブミッ後に作り始めてヴィジュアライザと同時に別方針も組もうとしていたので、この画像は1stは完全に無関係なやつ pic.twitter.com/IeynM2TxBs

拡大

拡大

hoshi524 @hoshi524

順位が良かったので、解法にふれると2段焼きなましをしました。 1つ目の近傍は、7*7のマスク単位で更新 2つ目の近傍は、何かを置く or 何かを動かす でした。動かす近傍が重要だった気がします。

nico_shindannin（診断人） @nico_shindannin

2次元フィールド上にリンクを貼るような形で、各地点各方向からの終点を持つようにしたけど、 - 鏡を置いて鏡ループができるケース - 鏡ループから鏡を消したときのケース - 鏡３つ置く→間に障害物を置く→その後鏡１つ置く→障害物除くで鏡ループができるケース など、混乱要素が予想以上に多かった

1 @komori3_

TCOMMR2 ・ゴミを投げる ・天国への階段を上る ・小説家になろうにアクセスする ・みんなにレートをお裾分け

nico_shindannin（診断人） @nico_shindannin

そういうわけで、昨晩は思い切ってデータ構造を見直して、ダイヤモンドを根とした根つき木にする方法を考えたけど、それだとランタン同士が並んだらダメ判定に不向きだったので、結局２次元グリッド上にリンクをする形を継続。ただ、双方向リンクで明らかにムダそうな計算いっぱいしてたので、だめそう

はまー @yuuki3655

TCOマラソンお疲れ様でした。方針は焼きなましただけです。焼きなまし難しい。

koyumeishi @koyumeishi_

今しがたやっと動かせるようになったけど提出間に合わなかった。 最低限過ぎて mirror / obstacle ガン無視した場合と使った場合の差がない、もしくは使わない方が若干いいレベルの出来。 提出してても多分70位ぐらい

tomerun @tomerun

TCO Marathon Round2おつかれさまでした。ランプ・鏡・壁を置いたり除いたりで焼きなましました。1日延びて助かった…

1 @komori3_

まあ真面目な話をするとアイテム置いた時のスコア変化を置く前の時点で計算する実装に固執しすぎた結果 lantern の place/remove すらバグらせて死んだ

tomerun @tomerun

工夫ポイントは ・「ランプを光に沿って移動させる」の遷移が重要（除く→置くよりも小さい遷移になる） ・2色クリスタルに1色だけ入っている状態の評価を+7→-10へ徐々に下げる ・操作する位置は単にランダムではなく、不要な光の経路上を優先する ・盤面サイズが小さいときは多スタート

はまー @yuuki3655

マラソン暫定32位。苦手な焼きなましで頑張れた方な気がする。github repository: github.com/yuuki3655/TCMM…

tomerun @tomerun

はじめ無駄に実装重い方針とってしまって土日ずっとデバッグで終わってしまったのは大反省（結局よりシンプルな方法で書き直した）

koyumeishi @koyumeishi_

ひぃひぃ言いながらランタン設置 O(1) の構造を書いて時間を消耗してたけど、割と密なことを考えると毎回素直に探索しても多分大差ないし、障害物/鏡設置するとき混乱しなくて済む気がした

はまー @yuuki3655

あと、途中で分割統治を試してみたのだけど、上手くまとまらなくて断念してしまった。

hakomo @hakomof

光の通るパス（実際に通ってなくてもいい）を1つ選ぶ。パス上のモノを高々1つのぞいてパス上に高々1つ足す、を近傍として焼く マスからのrayがどこにぶつかるかを取得O(1)更新O(N)にすると、近傍がO(1)に落とせて試行回数は1.3億 半分完成している2色crystalのスコアを前半は1、終盤は-10にする

nico_shindannin（診断人） @nico_shindannin

１ランタンはあってたら評価高めなのと、光に沿って移動は予定リストにあったけど、最後結局高速化のほうに時間を使ってしまったなぁ…。日曜日にさぼった天罰じゃ…

はまー @yuuki3655

おぉ、そうか。光の行き先はミラー作るまで変わらないから保存しておけば良かったのか。賢い。

はまー @yuuki3655

Javaによる解答も上位に来ていたから何か見落としてる思ってたけど、そこだったか。