The Great Plain - とどの日記

備忘録として，解法をメモ．

基本方針

前処理+焼きなまし法．前処理では，出来るだけ高速に妥当な解を生成する．焼きなまし法では，妥当な解からベターな解を探索する．

前処理

$a(p)$ ：座標 $p$ での値
とする．

まず，注目しているセルの座標に対し，ユークリッド距離で重み付けをした．つまり， $a(p)=0$ である $p$ に対して，
$a(p)=\frac{\sum_{k=1}^{k=n_f}\frac{a(p_{f_k})}{\|p_{f_k}-p\|}}{\sum_{k=1}^{k=n_f}\frac{1}{\|p_{f_k}-p\|}}$
と定めた． $n_f$ は，値が固定されているセルの数， $f_k$ は，値が固定されているセルの中でk番目のセルのインデックス．この方法でも，ある程度のスコアが得られるが，計算に時間がかかるという欠点があった．Test Case Generationより， $N=100$ ， $M=100$ ， $K=10$ の時に， $n_f=1000$ となるため，最も内側の演算は最大で約 $10^7$ 回実行されることになる．

次に，画像処理のフィルタリングを適用することを考えた．常識的に考えて，最適解は，全体的になめらかになるはずである．このように，値を全体的に滑らかにするフィルタを平滑化フィルタと呼ぶ．最もシンプルな平滑化フィルタに平均化フィルタというものがある．このフィルタは，注目しているセルの値と，その周りにあるセルの値の平均値を計算する．今回は，8近傍（+自身）を平均化の対象とした．1回のフィルタリングは， $N*M*9$ 回の演算ですむ．サンプルデータにフィルタリングを複数回適用した結果から，フィルタリングの適用回数として5を採用した．

焼きなまし法

まず，1回の遷移で，1つのセルの値のみを変更することを考えた．スコアの計算が $O(1)$ で可能だからである．この方法でも0.99pts.程度は得られた．

次に，複数セルの値を同時に変更することを考えた．簡単な場合として，2個のセルに注目する．この時，2つのセルのマンハッタン距離は，1で無ければ意味が無い．何故ならば，マンハッタン距離が2以上の時は，それぞれのセルの値がスコアに関して独立になるからである．つまり，1つのセルの値を変更することを2回繰り返すことと変わらない．そこで，以下のような変更パターンを作った．

これらのパターンから等確率で1つのパターンを選ぶようにした．焼きなましのループ回数を変更せずにローカルで試した所，スコアの向上が見られた．しかし，ループ内の演算が複雑になったため，CodeChefにSubmitした結果はTLEになってしまった．そのためTLEにならないループ回数に設定したが，スコアはむしろ元より下がってしまった．仕方が無いので，変更セル数を1or2のみとして（上図の上3つに対応する）ハードコーディングを行った．

その後は，乱数生成回数の減少（高速化のため），ループ回数・焼きなましパラメータの設定に労力を費やした．

サンプルデータ

$N=100$ ， $M=100$ ，固定値セルの出現頻度を0.01，0.025，0.05，0.075，0.1としてサンプルデータを生成した．

反省点

焼きなましの回数が固定値であったため，無駄にループしていたケースが少なからずあった（例：小さいプレートと大きいプレートが混ざっているケース）．適切にループを抜け出し，大きいプレートにより時間を割くことが出来ればもっとスコアは上昇したと思う．

乱数は最後までjava.util.Randomを使っていた．（使用が許可されている）他の乱数生成ライブラリを探す必要があった．

後半では，パラメータを細かく変更したコードを無差別にSubmitしてしまった．