第3回 RCO日本橋ハーフマラソン 予選 B 問題 652K 解法解説
ainem さん (ainem (@ainemixion) / Twitter) 主催の 第三回AHCをみんなで解く会コンテスト
に参加しました。この会は AHC のコンテストをチームを組んで解くというもので、今回は 第3回 RCO日本橋ハーフマラソン 予選 B 問題が題材となりました。
この会で 652K まで得点をのばし参加者中トップの得点を取れました。この記事ではこの解答について解説を行います。
考察
まずこの問題の状態として何をとればよいかというのを考えてみると以下となります。
- 手入れが終わってから収穫してよい
- 一度収穫すると 2 度と再収穫できないため、収穫 -> 手入れ -> 収穫 という操作は無意味
- 手入れが終わった状態での最高得点は一意に決まる
- 手入れが終わった状態であれば盤面のどの連結区画が収穫可能かと各連結区画の収穫時の得点が固定される
- 各収穫に平等に 1 手必要なので得点の高い連結区画から収穫していけばよい
以上から各区画を何回手入れしたかというのを状態と定義してやれば、本問題のすべての解答をもれなくだぶりなく表現できそうです。
ここで問題の性質を考えるとこの問題には以下のような性質がありそうというのがわかります。
- 10 以上の品質は無意味
- 品質をあげるのは 1 操作 1 点にしかならない
- そのうえ収穫困難になる
- また 1 操作で 1 点をあげる方法はいくらでもある
- 収穫対象にならない区画を適当に手入れして他の連結区画と連結させればよい
- 品質をあげるのは 1 操作 1 点にしかならない
- 局所的な変更は大域的な影響をもららさない
- 最大の品質が 9 なので、ある区画の操作は 9 マス離れれば得点に影響しない
- 逆に局所的な変更はまわりの状況に非常に影響される
- ランダムに 1 区画選んで変更してもまず得点があがらない
- 組み合わせ最適化のうち、評価値があがる組み合わせが極端に疎となる問題というイメージ
方針
ランダムで盤面を変更する場合、複数の区画を同時に変更したほうがよさそうです。したがって以下のような山登りの方針なら (トップと戦えるかはともかく) 得点は伸ばせそうに見えました。
- 初期状態としてすべての区画の手入れ回数を 0 に
- 時間が尽きるまで (1950 msec の間) 以下を繰り返す
- 区画をランダムに選択する
- そこからランダムな数の区画をランダムに接続する
- 接続する区画数は
からランダムに選ぶ
- 接続する区画数はパラメータ調整対象。当初は
からランダムに選んでいた。
- 接続する区画数は
- 接続した区画の品質が同じになるように手入れの回数を更新
- 更新した手入れ回数の得点が元よりも高ければ保存、高くなければもとに戻す
これを実装したところ 500K 点ぐらいの得点でした。
差分評価
手元でタイムリミットをのばしてみると得点があがるので山登りしきれていなさそうです。上記の操作の処理時間を見てみると 0.4 msec 程度 (操作回数 5 千回) かかっていました。
いろいろな処理をコメントアウトして *1 みたところ、盤面の得点評価が圧倒的に時間がかかっていたので得点評価を高速化することを考えました。
考え方
考察の通り局所的な変更は大域的な影響をもたらさないので、局所的に変更した後に盤面全部を評価しなおすのは無駄となります。局所的な得点、つまり今の盤面で収穫可能な連結区画とその得点を管理すれば、変更した周辺だけを評価しなおして変更後の得点が計算できるはず、だと考えました。
手法
以下を管理して差分評価を実現しました。(map は実際には unordered_map を使っています)
- 各収穫可能な連結区画に番号をつける
- 得点の管理として何点の連結区画があるかの multiset (C++ でいうところの) をもつ
- 総手入れ回数から収穫可能回数がわかるので、multiset の大きいほうから収穫可能回数個足しあわせれば得点が簡単に計算できる
- 注: ここは得点を key としてその得点を達成する連結区画数を value とする map をもってもよかったかもしれないです
- 連結区画の得点を管理するために連結区画番号を key として得点の map をもつ
- 連結区画を壊したときに何点下がるかを簡単に計算するため
- 注: これは不要でした (得点は連結区画の区画リストの区画数から容易に計算可能)
更新手順
更新するときは影響の受ける連結区画を慎重に見定める必要がありました *2。以下の手順で操作を行えば更新による収穫できる連結区画の増減を漏れなく検知できます。
- 更新対象の区画が所属する連結区画を列挙する
- 列挙した連結区画を破棄する
- 連結区画の得点も破棄しておく
- 更新対象の区画 + 破棄した連結区画に所属する更新対象外の区画に対して収穫できる連結区画ができるかチェックする
- チェックの結果収穫できると判明した連結区画に新たな番号を振る
- 新たな連結区画の得点を記録する
高速化効果
差分評価を実装したところ、操作にかかる時間は 8 microsec ほど (操作回数 25 万回) となりました。およそこれで 600K 点ほどです。
山登り解の改善
この解答は乱択なため、できあがりの盤面は無駄が含まれていていくらかの改善ができます*3。
- 収穫できない区画への手入れを解除
- 無駄な手入れ回数を収穫にまわす
- ある区画が連結区画に属していて、品質の低い別の連結区画に隣接している場合、手入れ回数を減らすして所属する連結区画を変更する
- 手入れ回数が 0 未満にならない場合に限る
- 減らした手入れ回数分を収穫にまわせる
- ある区画が連結区画に属していないが何回か手入れを行えば連結区画に連結できる場合、得点の状況を考慮しながら手入れを行う
- 手入れを行うと別の連結区画が収穫できなくなるため
と収穫対象の連結区画の最低得点を比較しながら手入れを行うかどうかを決める
- 手入れを行うと別の連結区画が収穫できなくなるため
- 最後に連結区画に対して
順にならべて得点効率の悪い連結区画の手入れを解除する
以上の貪欲改善を行うと 1 テストケースにつき 100 点弱プラスでき、総計で 650K 点となりました。
得点状況
seed=1 に対する得点状況は以下のようになりました。2 点の区画まで収穫しているようです。
初期状態
操作後
好スコア要因
連結区画が十分作れてすべての連結区画を収穫できなくなった状態において、得点が上がる方向への遷移を考えると以下のようになっており、自然と得点効率があがる方向に遷移していったので好スコアが出たのだと考えています。
- 無駄に手入れするのをやめる
- 例えば初期品質 1 の区画を手入れして他の連結区画に連結していたのを手入れ回数を 0 にする
- もとの連結区画が収穫できる状態を保つこと
- 手入れ回数が減る分収穫回数があがって得点アップ
- 例えば初期品質 1 の区画を手入れして他の連結区画に連結していたのを手入れ回数を 0 にする
- 大きな初期品質の区画を他の連結区画に連結する
- 得点増加分と手入れ回数増加による収穫回数減少分を考慮しても得点アップする場合のみ
焼きなましが上手くいかなかった原因
山登り関数の名前が annealing になっている通り当初は焼きなましをしようとしていました。ただしやってみたところ得点がのびずまったく焼けませんでした。本解答の更新手法は近傍状態への遷移と考えてよいですが、近傍状態のうち得点が増えるものが極めてすくないため、焼きなましを行うとどんどん得点が失われていくようです。
おわりに
ainem さん、楽しい会を開催していただいてありがとうございます。
