問題
お掃除ロボットのルートを決めてね。
1日目
とりあえず正の点を得たい → 得た。長期コンで初めて「今すぐ終われ」って思った。
D_ijが大きいところを複数回通るようなルート構築(ルート構築に重みをつける?)
その上でできるだけ短い時間で帰ってきたほうが全体的に汚れは小さく済む
ならば、条件付きの巡回セールスマン問題に落とし込めるのでは？
=> まずは普通の巡回セールスマン問題として解く
やったこと
正の点を得る
構造体とか用意
全部掃除したら直帰させる -> 1000ケースTotal score: 28331710684
やること
巡回セールスマン問題として解く
2日目
巡回セールスマン問題でやると平均汚れがあんまり下がらなそう → 一旦後回し
左上と右下に拠点みたいなのを設置して、そこを往復させる？
一番高い場所を一箇所用意→そこから行って帰ってきてを繰り返すでも良さそう
流石に入力の生成を確認したほうが良さそう
なんかあんまりまとまらない日だった
やったこと
エリアに分けて、掃除する順番を決めたあとにエリアごとに掃除していく→ Total score: 27590499212
暫定テストだけだと下がったように見えるけど良くなってるらしい
やること
順番の決め方を改善する
右上と左上を行き来するようなのは弱い
エリア間の移動を改善
なにがある？わからん
3日目
通るルートは少ないほうがいいので、一旦雑に汚れの増加量を減らしてみる
→ Total score: 23666745045 結構改善してワロタ
エリア分けを山登りっぽい感じでDの平均が近い方に移動させようとしてるんだけど、連結性のやつでWAになってて、3 * 3のマスで簡易的な判定するやつやろうとしてるんだけどそのツイートが見つからない。助けて！
地図を小さくする回で見たような？と思ってハッシュタグで調べたら出てきた。
chokudaiさんありがとうございます！！！！！！！！！
実装うまく行かないから普通にDFSした。
Dをできるだけ同じところに集める方針はうまくいかず
→ Total score: 26746043097
結局いろいろ試したけど、今日のはじめに引いた方針より改善はできなかった。ぜんぜん違う方針を探る必要がありそう。
やったこと
いろいろためした
4日目
違う方針を探るために、汚れとルートを完全に追跡するように。
気づき：Dが小さいところを先に掃除しておくと長期的に有利な場合がある？ → 多分正しくて、しかもコレは"早く帰ってきたほうが強い"にもつながる
山登り・焼きなましのために差分での得点がどうなるかを考える。
変更前:(L + M)ターン、汚れの総和: (S + T)
変更後:(L + N)ターン、汚れの総和: (S + U)
であるとき、
S(N - M) + L(T - U) + (NT - MU)
が負になれば改善。ただ、特定タイミングの汚れの総和T, Uを求めるのは(持っておくのも、更新時の差し替えも)重そうなので、いい感じにサボりたい
そういえばローカルでテストする用のツールはRust製なので、ちょいと評価関数を拝借してきた。visualizerの値とちょっとズレてるのは、まぁ誤差程度だし大目に見といてあげましょう。さっきまで真面目に考えてたのは何だったんだ...
やったこと
山登りを書いた
やること
高速化
新規ルートの作り方を工夫
焼きなまし
5日目
実はずっと放置してたけど、プレテストで1ケースだけずっとTLEしてるやつがいる。まぁなんとなく予想はついていて、ルートの全長をLとするとルートの更新と点数取得にそれぞれO(L)かかってきていて、コレが重そう。でもLの最大値が10^5なので、いくら定数倍が重くても100msもかかるか...?みたいなところはある。どうなっとんねんこれ。
配列の交換をswapにしたら早くなった。大体2万回転ぐらいしてるらしい。そういえば1000ケース回してなかったのでまわす。Total score: 19857798014
回転数ってどれぐらいあるといいんだろうと思って調べてたら↓を見つけた。
https://github.com/terry-u16/ahc014/blob/master/diary.md
山登りができるということは焼きなましもできるということなので焼く。
焼きなマterryさんが言うなら間違えなさそう。コンテスト期間中だと初焼きなましに挑戦。うーん、悪くなった。ということは、初期解があまり良くないのと、近傍がよくない(BFSで決めてるのがだめ？)っぽいな。
とりあえず高速化。今はseed=97でだいたい17Kイテレーション。各頂点からの距離を事前に計算するようにしたら早くなった。31Kイテレーションぐらい。汚れを完全に追跡するのをやめたりして、42Kイテレーション。これ以上高速化しようと思うとスコア関数を高速化するのがいいんだけど、筋のいい方法があんまり見つけられない。ので、一旦後回しにして近傍を探っていきたい。1000ケースはというとTotal score: 16860798540。めっちゃ上がっててワロタ。頑張れば1桁落とすところまで行けそう？
ルートの近傍については、初めの最後の2地点の平均を取って重み付けした状態である1点乱択、その後その一点を通るBFSルートでやるといい感じになるかも？まぁこれはやってみないとわからない。あとはあれか、プロファイリングとかいうやつをやってあげてちゃんと重いところを見つけてあげるべきなのか...?
その後ちょっとした高速化とかもしてみて焼きなましに戻したりもしたけど、点数は上がらず。時間をかけても対して変わらなかったので、コレは近傍がダメそう。
やったこと
高速化
よわよわやきなまし
やること
高速化
近傍の作り直し
6日目
ここまで来てもまだ改善点があるのはありがたい。まずは近傍を一点乱択+そこを通るようにに変えた。ただ初期解の動きそのままで非効率な箇所が散見されるので、やっぱり速度が足りてない+初期解の見直しが必要っぽい。10秒じっくり焼いてあげると点数が上がっているので、まだイテレーションが足りてない。評価関数直さないとか...
Total score: 17374650081。やっぱりちょっと落ちてるが順位は上がったので、他の人が苦手なケースが強い可能性がある？
同じ箇所を複数回通る可能性がある以上、あるターンで平均汚れが小さくなっても、あとから覆る可能性があるんだよなぁ。そう考えると毎回計算せざるを得ないのか？というか、初期解が小さい問題だと100Kぐらい回ってるので最初から初期解を小さくする方向でやったほうがいいかもしれんな。というかそもそも初期解を作り直すべきかもしれん...
となると、強い解がどうなるかを想像すれる必要がありそう。
見ていると、エリア間の移動で明らかに汚れている場所を無視して次のエリアに移動しようとしている時があって、それがボトルネックになってる感じがある。そのエリアの汚れが小さいときはあとの焼きなましで消し飛ばせるはずなので、隣接エリア(壁が多いときは隣接しない場合があるがあまり気にしない)のみに移動していくように初期解を変えるとか？うーん...
今の分割統治の初期解+焼きなましだとseed=97みたいな盤面大きめ+複雑だと強いけど、seed=0みたいなのだとかなり微妙。高速化よりは初期解の弱さが最上位との差だと思うんだよな。近傍はまだ工夫できるけど、銀の弾丸にはなり得なそうな感じがあるので。
現実の自動掃除機を見てると、ある場所からぐるぐる回る動きをすることが多い。これって実は合理的な動きなのでは？いい感じに取り入れれないかな。
うーん、改善を求めていろいろ試したけどやればやるほど悪くなるな。根本的に色々見直していく必要があるかも。
これで下の方が相対得点いいのマジわけわからん(たぶん点数がデカくなるケースで他の人に勝ってる)。
2地点の近傍、どっちにしろ同じルートならDがでかいところを通ってたほうがいいだろってことで、DPでやってもいいかもしれん((値、どっちからきたか)を持ってルート復元するDP。ボールソートするときにやったやつ)。
7日目
とりあえず昨日の最後に書いたやつを実装した。Total score: 16673727704。よしよし過去最高点は更新できた。
ほかは特に何もできてない。うーん、そろそろスコア比較をどうにかしないとなぁ...
8日目
いい加減スコア更新をなんとかする。
9日目
通ったタイミングを持って、遅延更新でいい感じに効率化とかしようとしたけどバグらせた。リバート。
ただ更新時に配列コピーが発生しないようになって、平均して8k回転ぐらいは上がった？いやそんだけかよ。
今日は用事で出かけるので、その間にパラメータチューニングやりたい。
あと、ふと思ったけど100とかのレベルで更新がかかるからバグらせるのであって、2,3程度に収めれば何とかなるのでは？実際、任意の連続3マスだけ抜き出すとありうるのはL字か直線かの2択で、その範囲で再構築するほうが現実的かもしれない。ただ一方で長さの圧縮が全体の効率化に寄与するという面もあるにはあるので、全長が短縮される近傍も入れたいんだよな。