参加記
問題
人の社員がいて週替わりで掃除当番となる
各社員について掃除回数の目標値が設定されている
週経過した時の、目標値との差を最小化する問題
掃除当番の社員の次の当番を
の2人設定し、交互に当番を渡していく
問題理解
ざっと読んで、掃除当番の頻度を最適化(目標値に近付ける)するのだなとは理解できた
ただ、tが奇数の場合、偶数の場合と書いてありましたが、文章だけではよく分かりませんでした
ビジュアライザの例(例を見る)があったので、見てみるとようやく理解できました
週数の偶奇だと思っていましたが、その人にとっての偶奇だったようで、最初に把握できてよかったです
あと、ビジュアライザが201ターンから急に最後まで飛んでいたため、ループ検出をしてスコア計算の高速化をしているのでは？と考えて、コードを読みましたがそんなことは無かったです
~0:40
とりあえず手を動かして解を作ってみることにします
hqに突っ込んで、残っている目標値の大きい人から順に掃除するようにしてみる
すると、全員が同じ回数掃除する解が得られました（ただ全体を1周するだけなのでそれはそう）
いい感じに２分させて、到達回数をバラけさせていくのだなと思いましたが、数分考えても良い貪欲が出てこなかったため、とりあえず焼いてみることにしました
高速化は後で考えるのが短期の立ち回りだと思っているので、L=500,000回のシミュレーションを素直に回してスコア計算をしました
近傍は1点変更と2辺のswapを実装してみると、seed=0でscore=909,650が出ました
一旦提出してみると絶対スコア136,891,480で、確か50位あたりだったと思います
~1:00
小さなケースでいい感じのグラフが作れないか実験してみると、2人であればきれいに1:2の頻度を作れることに気付きました
「0 1, 0 0」のようにすると、001001...のような遷移をすることに気付いて、これを拡張すれば1:2:4:8のように出来ると考えました
良いグラフの作り方をCharGPTに相談してみましたが、的を得た回答が得られず残念でした
グラフの作り方を提示しても間違った比率を解答してきました。難しい
~1:30
子供が眠そうにしていたので、寝かしつけをしていました
考察を頑張ることで、寝落ちせずに戻ることが出来ました
~1:50
掃除回数の目標リストを[9600, 4800, 2400, 1200, 600, 300, 150, 75]のようにして、各値に近い人をグループ化して１人として扱うことにします
「0 1, 0, 2, 0 3 ...」のように、1/2で最初に戻るループを作れば上記の頻度を達成できます
これを実装して提出すると、絶対スコア138,360,124で少し良くなりました
若干想定の回数とはズレていますが、2倍違いの掃除回数が並んでいるのでやりたいことは出来ていそうです
また、この初期解をベースに焼くと絶対スコア140,407,270が出ました
この辺りで初めて順位表を見ましたが、149Mが出ており「強すぎ...」となっていました
~3:30
他にやることも無いので、今の解をレベルアップさせようと色々試しました
まず、焼きなましのループ回数が明らかに少ないので評価関数のループ数を減らしました
L/100回シミュレーションした結果を100倍してスコア計算を行うことで、純粋に100倍高速化しました
コンテスト後のTLを見ると、この改善をした人は結構いたようでした
各頂点について、参照されている数を数えておいてこれが0になるような遷移は不許可とする処理を追加しました
焼きなましの結果で、たまに0回の人が出現したため誰かしらから当番が回ってくるようにはしておきたい気持ちがありました
→終了後に検証すると、無くてもスコアに影響は無さそうでした
１位の点数からケースごとの誤差量を計算してみると、ケースあたり約2000程度しか誤差がないことが分かりました
ここから、最終的に目標値と同じくらいになるのなら目標値を使ってスコア計算をしても良いのでは？と思いつきました
実装してみると、計算上のスコアは上がるもののビジュアライザに投げてみると全然良くない。という結果になってしまい、実装はしたものの一旦使わないことにしました
→終了後にこの辺りの提出コードの評価関数だけこれに置き換えるとかなり良いスコアが出ていた。。。
~4:00
ラスト30分で、目標値を使ってのスコア計算に戻って来ました
というより、これに頼るしかないような状況でした
焼きなましの近傍を増やしてみたり、スコア計算を見直してみたりしつつ、５分おきに提出だけしてみますが250位辺りから動きません
あと10分というところで、自己ループになるような遷移を許可しない処理を追加すると、とんでもなくスコアが伸びました！
→終了後に考えてみると、目標値の半分を行先に振り分けるというスコア計算をしていて、行先に自身が含まれていると過大評価になってしまうようです
最終提出で絶対スコア149,407,730を得て、43位でフィニッシュしました
終わりに
問題を読んだ時点での印象は、かなり取っつきにくい感じでしたが取り組んでいくうちに、本質理解が進んでかなり面白い問題でした
writer解のビームサーチが何をしているのかまだ見ていないので、考え方だけでも吸収しておきたいなと思っています
再来週には長期AHCが始まるので楽しみにしつつ、復習しておきます
この頻度だとアルゴをやる時間が取れないですね。。。
