TCO19 Marathon Match Round 1 参加記
TCO19 Marathon Match Round 1に参加しました。
問題設定
概要
N人の人がいる。人は0からN-1までの整数で番号付けられ、i番目の人の高さはH[i]である。最初、左からi番目にはi番目の人が立っている。この状態から並び順を変える操作をX回行う。このとき、できるだけ移動距離の総和を小さくしつつ、i回目の並び替えの直後に左からj番目に並ぶ人の高さをarrangement[i][j]に近づけたい。
スコアリング
i回目並び替えの直後に左からj番目に並ぶ人の番号をord[i][j]とし、i回目並び替えの直後のj番目の人の位置をpos[i][j]とする(pos[i][ord[i][j]] = j)。distをabs(pos[i][j] - pos[i-1][j])の総和とし、errを(H[ord[i][j]] - arrangement[i][j])^2の総和とするとき、スコアはdist+sqrt(err)と計算される。
テストケース生成
以下の範囲から一様ランダムに選ばれる。
は高さの上限を表す変数。
が選ばれた後に
が選ばれる。
解法
焼きなましました。
近傍設定
近傍は、「i番目の人とj番目の人の、a回目からb回目までの並び替えでの位置をそれぞれ入れ替える」と設定しました。i回目の並び替えでj番目にいる人が、i回目の並び替え以降でとおる場所のarrangementの合計値をsum[i][j]と書くと、errの更新は、
err += 2 * (H[i] - H[j]) * (sum[a][pos[a][i]] - sum[b + 1][pos[b+1][i]]);
err += 2 * (H[j] - H[i]) * (sum[a][pos[a][j]] - sum[b + 1][pos[b+1][j]]);
とO(1)で計算できます。実際に遷移が起きるとき、O(X)かけてsumの値を更新すれば、O(1)でスコア差分が求まり、O(1)で遷移判定を行うことができます。
distに関して、i番目とj番目の人の、「(a-1)回目からa回目」及び「b回目から(b+1)回目」の移動が変化しています。ただし、b=Xの時は「b回目から(b+1)回目」の移動が存在せず、この場合は変化する箇所が少なくなり、特別扱いします。
遷移提案
５０％の確率でb=Xとする。b=Xは状態の変化量が小さく、焼きなましの遷移としてよい性質を持っているといえるので、確率を大きくしておく。
a,iをランダムに選ぶ。a番目の順列の前後でi番目の人の近くにいる人をjの候補とする。候補の中でiから遠い位置にいる人から順に見ていき、遷移が受理される時点でイテレーションを終了する。
温度管理
温度そのものをスケジューリングするのではなく、最良スコアと現在の状態におけるスコアとの比が線形に減衰するように温度を調整するようにした。具体的には、線形に1から0に減る量をrとし、W=1+0.03rとしたときに、(それまでに見つかった最良スコア)×W>(現在のスコア)なら温度を上げ、そうでなければ温度を下げる、とした。
再スタート
時間を４分割してそれぞれで焼きなましを行った。Wの初期値は減衰させるようにした。
感想
久しぶりにまともに参加（といっても３日だけ）できて楽しかった。
