AHC044の反省

はじめに

今年からHeuristicのコンテストが多くて嬉しいが、AtCoder Heuristic Contest 044は、手も足も出なかったので、ほぼ反省の振り返りになる。

問題

問題は掃除当番を順番に決める問題...というか、1回目は右に行くけど、2回目は左に行くという線路のおもちゃを想像した。各線路を通過する回数に目標値があるので、それにできるだけ近づける問題。

方針

よくわからないので、焼きなましで考えてみる。

スコアの計算

最初、スタート地点に2回戻ってきた段階でループに入る...と思ってしまったが、よく考えると他の社員が奇数回目か偶数回目かも一致しないとループにならない。仕方ないので、愚直にシミュレーションしてみるが、ターン数である$L$が$500,000$なので、それなりに時間がかかってしまう。そこで、$L/100$回シミュレーションして、目標値の$1/100$との誤差を足し合わせるでスコアを算出することにした。目標値の値域が$0$から$10,000$なので、$1/100$すると$0$〜$100$に圧縮される。粒度としてはそんなに悪くないのでは？と考えた。

木を作る

2つに分かれる線路のイメージだったので、二分木を作ってみた。ある程度進むと根に帰るようにすると、根のノードの方が巡回される回数が多いので、根に近い方に目標値が大きい社員を置くと良いと考えた。
そこで、目標値を降順にソートし根から順番に二分木を作ってみた。葉に相当する社員は根の社員に戻るようにしたが、これだとみんな同じ回数だけ掃除することになるので、ある高さ以上の社員の$a_i, b_i$のどちらかは根の社員に戻るようにした。隣接解としては、次の掃除当番社員の交換と根の社員に戻る順序をランダムな社員に変更するの2種類で、導出した。

ただ、この方式だと最初の解のスコアも低い上に、焼きなましで回してもまったく更新されない。これで結構時間を取られてしまったが、再度考え直すことにした。

単純にならべてみる

木だと複雑すぎるので、社員を目標値順に1直線上にならべてみた。この時、奇数回目での次の掃除当番を根の社員にすると、根の社員からその社員までを2回通過してから、その後ろの社員に掃除当番が移る当番表が作れる。つまり、目標値が根の社員の$1/2$, $1/4$, $1/8$のところで根に戻るようにすると、良い感じになるのではないか？ということでそれを初期値として焼きなましをおこなうこととした。隣接解は、奇数回目の宛先を適当な社員に変更する。で行ってみた。これでも、ほぼ更新は発生しないが、木の時よりもスコアはいいので提出。これで終了となった。

振り返る

最後に提出したもので、公開されている100のテストケースを解いたスコアは74,755,066点。ここから他の人の実装などを見て考え直してみた。

隣接解のバリエーション

近接解を以下の4パターンで作成することにした。
任意の社員$i, j \, (i \neq j)$を導出して、

• 社員$i$の次の掃除当番を$j$にする（奇数回目/偶数回目）
• 社員$i$の次の掃除当番と、ノード$j$の次の掃除当番を入れ替える（奇数回目/偶数回目）

これでスコアが 95,004,870点（+20,249,804）。大きく変わった

重みをつける

$i,j$の導出をランダムで行っているが、誤差が大きい社員ほど変更した方が良いので、誤差をそのまま「重み」として選択するようにした。スコアは95,551,232点　(+546,362)

シミュレーションの回数変更

シミュレーション回数を$1/100$に固定するのではなく、$1/100$, $1/50$, $1/25$,.. とだんだん増やしていってみる。スコアは86,152,584点 (-9,398,648) で下がってしまったので、とりあえずこれは保留

スコア算出方法の変更

スコアをシミュレーションではなく、トポロジから導出する方法を使っている人が多かった。目標値$T_i$の社員$i$の次の掃除当番が$(a_i, b_i)$であったとき、社員$a_i$, $b_i$には、それぞれ社員$i$から$T_i/2$だけ掃除当番が回ってくる。これより求められる掃除当番の回数と目標値の誤差からスコアを近似する方法である。この時$N$回のループで終わるので、シミュレーションより早くなることが期待される。スコアは 90,045,262点（-4,959,608）。トポロジから求めたスコアと本当のスコアとの乖離が大きい。トポロジから求めたスコアだと99百万点になっていたので、最適化はされている。

試してみる

とりあえず一番スコアが高かった重みつけまでやったパターンを提出してみると、200番台ぐらいのスコアがでた。ここまでなら時間内にだせたのでは？と思うのとともに、もっと上位の狙うにはどうすれば良いかはしっかり考える必要がある。