第3回日本橋ハーフマラソン予選

失敗したと思ったが(75位で，恐らくボーダーだが)予選通過したので，少し復習した。

A:ツーリストXの旅行計画

コンテスト中にやったこと

山登り/焼きなましでよさそうだと思ったので， $0,1,\cdots,N-1$ という順から初めて，2点をswapする山登り法を試した。山登り法というのは

現在の状態から「少し変わった状態」のスコアを計算して，それが現在の状態のスコアより良ければ，「少し変わった状態」を現在の状態とする。

ということを繰り返すものである。この「少し変わった状態」を近傍と呼ぶ。2点swapというのは，点を訪問する順番を表した順列において，2点を入れ替えたものを近傍とするという意味である。これをすると28万点くらいになる。
Submission #4232922 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザの結果はこちら。
f:id:sigma1113:20190216174359p:plain
ところで，分散の計算には「 $(2乗の平均値)-(平均値の2乗)$ 」が使える。これを用いれば，実は近傍のスコアの計算を $O(1)$ で済ませることができる。つまり状態として訪問順の他に，距離の総和と距離の2乗和をもっておけば，点を入れ替えたときに減る距離と増える距離をそれぞれ計算することができて，これは高々4箇所であるので， $O(1)$ で更新が済むというわけである。これは差分更新と呼ばれたりする。
しかし，これをやればスコア伸びるでしょーと思って出したのだが，なんと全く伸びない。このあとBを解き，Aに戻ってきてからいろいろと試したが，結局28万点のまま終了した(152位)。悲しいね。

反省会

山登り/焼きなましというのは悪くなかった。問題は近傍の選び方であった。2点swapでは，パスを構成する辺が4つ変わっていることになる。これは全然「少し」変わった状態じゃないという問題があった。ここから，近傍として「パスのうち2辺を変更する」ということを考える。これは2-optと呼ばれる手法(?)らしい。そんなこと簡単にできるのかとちょっと思うが，訪問する順番の順列のある区間をreverseするだけでできる(絵を描くとわかる)。
なんとこれだけでスコアが150万点くらいになる(!?)。およそ5倍になっている。コンテスト終了後，TwitterのTLでは，「スコアが5倍になった」というツイートが散見された。
Submission #4238797 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。大幅に改善している...。
f:id:sigma1113:20190216180528p:plain
この提出は差分更新をしていないのだが，2点swapのときと同様に差分更新にして，焼きなまし法に変更すると，220万点が出る(30位相当)。焼きなまし法はパラメータの調整が面倒なのだが，以下の記事を参考にいろいろ試したらうまくいった。ありがとうございます。
焼きなまし法の適用メモ - Negative/Positive Thinking
提出はこちら。
Submission #4276320 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。
f:id:sigma1113:20190216181033p:plain

上位陣の考察を見ていると，使う辺の長さの範囲を限定したり，ある長さを決め打ってその長さに近い辺を使うということをしていた。この長さを決め打つという手法は有効らしく，「長さを乱数で決め打って，決め打った長さに最も近いものを選びながら，先頭から順番にパスを構成していく」だけで80万点が出るらしい(自分は試していない)。マラソンわかりません。

B:ファーマーXの収穫計画

B - ファーマーXの収穫計画

コンテスト中にやったこと

大きい数字である9や8をたくさん作って収穫したいと思った。ところが，1とか2を9にしても手数がかかるのでよくなさそうだ。そこで，てきとうに閾値を決めて，閾値以上のマスは収穫したい数字にする，ということをした。閾値は収穫したい数字の半分以上とした。収穫したい数字は9から始めて，9を収穫しきったら8を試す....ということを繰り返した。実装上はBFSを何回かすることになる。なんとこれだけで54万点が出る。
さらに，9のマスはいくつかあるわけだが，収穫する順番を乱数で決め，時間いっぱい試すことにより，55万点に乗った。これが最終スコアになった(38位)。やったことは非常にシンプルだが，これでそこそこ上位が取れたのは助かった。
Submission #4236103 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。ほとんど9で収穫している。よく見ると8も少しある。
f:id:sigma1113:20190216183234p:plain

反省会

大きい順にとる，というだけでは，手数の問題をまだ十分に考慮しきれていない。ある区画を収穫するときに，その区画を収穫すると1手あたり何点得られるか？ということを考えるのは，言われてみれば自然なことのように思える(まあ気づけなかったんですが...)。そこで，「ある区画を収穫するときに得られる得点/その区画を収穫するまでにかかる手数」を評価値とする。このとき，「その区画を収穫するまでにかかる手数」は小さくしたいから，収穫するマスの値を $K$ とすると，「隣接する $K$ マスの値 $K$ にするのに必要な手数の最小値」を求める必要があるが，これはbfsの際に優先度付きqueueを用いることで可能になる。
すべてのマスについて評価値を計算した後，それが大きい順に実際に手入れ，収穫をする。評価値が最大でないマスは，すでに本当は使いたかったマスが収穫されていしまっているということがあり得るが，その場合は評価値を再計算する。これを手数の限り繰り返す。
なんとこれをすると60万点に乗り，2位相当となる(!)。何を評価値すればよいかということをしっかり考えることが重要だと思わされた。
Submission #4267434 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。要はコスパの良い順なので，さまざまな数字が収穫されている。また，収穫されているマスが各段に増えている。
f:id:sigma1113:20190216185003p:plain

せっかくなので本戦も頑張りたい。