130. AtCoder参加記録（AtCoder Heuristic Contest 013）
暫定テスト142位、215,674点です。システムテストでは143位、1744 perf でした。
AtCoder Heuristic Contest に初参加しました。
マラソンは初めてでしたが、コンテスト中にブレイクスルーがいくつかあってとても楽しかったです。また、自分の解法だと22万点くらいが限界だと思うので、30万点超えている人がどういう方針で解いているのかとても興味深かったです。
解法
大まかな方針は以下の通りです。
- 1種類（ターゲットと呼びます）だけ、なるべく完璧に繋げることを目指す
この方針でより良い解を得るため、（細かいことは色々ありますが）大まかに以下のような実装としました。特に重要な工夫と考えている部分は太文字にしました。
- 移動フェーズ・接続フェーズに完全分離し、移動回数を少しずつ増やしながら、その時の最良接続で得られるスコアを計算し、時間内に得られた最適解を出力する
- 移動フェーズでは、以下の条件を満たす盤面を「良い盤面」とみなし、評価関数で最良盤面を探索する（貪欲法）
- ターゲットが同じ行列に多く存在する
- ターゲットが多く存在している行列ほど、非ターゲットが少量存在している
- 接続フェーズでは、手数が余っている限り以下の手順で操作を決める
- 隣接しているターゲット同士を（同一クラスタに属さないなら）繋ぐ
- ターゲットから伸ばせる接続で二手先まで見て、最もスコアが増加する接続を行う
- 2. でスコアの増加する手が無い場合、ターゲットから上下左右にできるだけ接続し続けて最もスコアが増加する接続を行う
- 3. でスコアの増加する手が無い場合、ターゲットを他の種類に切り替えて 2. の処理から開始する
この実装で得られた解の例を並べておきます。
日記
期間中の日記です。
8/9
この時は参加を考えていなかったので、何もしなかった。
8/10
お盆休みで数日だけ実家に帰る予定があるので、どうせ暇だし参加してみることに。
問題文を読み、とりあえず「隣り合った同じコンピュータだけ接続する」ような単純なアルゴリズムで提出してみる。7555点。
他の人の提出を見ていると、サンプルコードそのままで26047点になるっぽい。流石に今の点数は恥ずかしいので、「隣接してなくてもケーブルを伸ばして繋がるなら繋げる」ように修正。20325点。結局デフォルト点に届かなかった。
8/11
計算式や操作回数の制約を考慮すると、バランス良くクラスタを作るより、無理矢理でも1つの大きなクラスタを作る方が有利。そういう視点で考えてみる。
Visualizer を眺めていると、コンピュータの種類数や空きマスの割合に応じて良い戦略は変わってきそう。とりあえず、種類数が少なかったり空きマスがあまり無かったりする場合は、昨日と同じ「ケーブルを伸ばして繋がる同じコンピュータをできる限り繋げる」のままに。移動フェーズを色々考えたが、所用で家を出る必要があったので、「繋げるコンピュータの種類・縦横どちらから繋げるか、を全探索して、選んだ種類のコンピュータ "のみ" 繋げた時の最大スコアになる解を出す」という雑な処理で提出してみる。28054点。こんな不完全なアルゴリズムでも正の点数を取れたことに驚き。
帰宅後、貪欲法的なアルゴリズムを考えてみるが複雑すぎて実装を断念。ただ、「なんとなくこうすれば良くなりそう」という戦略は見えるので、「盤面に適当な評価関数を与えてビームサーチすれば良いのでは？」と考えた。見積もりのためにかなり雑な実装にしたものの、それにしても動作速度が遅い・しかも思ったほどスコアが改善しない…。この方針は捨てることに。
8/12
サンプルコードのアルゴリズムが問題文に書かれていることに気づく。適当な移動を入れるだけで多少点が伸びる、ということは移動フェーズが重要っぽい。
昨日は移動と接続をごちゃ混ぜに考えていたが、移動フェーズ・接続フェーズと、はっきり分けた方が見通しが良くなることに気づく。「移動を何回やるか？」で探索できるし、盤面の保存（計算の高速化）もやりやすい。
ここで、「良い盤面＝なるべく同じ数字が密集している盤面」という気持ちになる。そこで、同じ数字同士のマンハッタン距離の和を評価関数として、これがより小さいものを探索してみることに。この評価関数だとビームサーチも必要なくて、貪欲に良いものを残していく感じになる。
次に接続フェーズだが、Visualizerを見た感じ、「違う種類のコンピュータだけど、そこをハブとすれば別の大きなクラスタに繋がって高得点になる」というパターンが多い。そこで、一手先読みを入れて、「違う種類であっても接続を許可し、そこからもう一回接続を伸ばして得られる点数も考慮した最大値はどうなるか？」を計算することに。これも最良のものを残していく貪欲法的なやつ。大きなクラスタを作るため、「どの種類を大クラスタにするか」を決め打ちして隣接したものを繋げた後、一手先読みで最も獲得スコアが大きいものを選択し続けるような処理にした。色々バグらせつつ何とか実装しきり、seed=0 でやると思った通りいい感じの答えを出している。
そこから、「移動フェーズの最低回数を適当に決める」「2700ms で処理を打ち切る」といったものを入れて、見つかった最良の操作を出力するようにした。これで83222点。思ったほど伸びなかったけど、まずまずの点数に。
8/13
昨日の結果を眺めていると、一手先読みはかなり効いてる感があるが、移動フェーズの処理がどうもそこまで意味を為していない気がする。seed=1 を見ていると、もう少し「繋ぎ」に使うマイナスのコンピュータを減らせそう。動きを見た感じ、余計なコンピュータに邪魔されて正しいコンピュータが位置取りできていない雰囲気がある。
移動フェーズでは全部のコンピュータを等しく評価して動かしていたが、「大クラスタを作る種類だけ "良い位置" になるように調整する」という方針を取ることを考えた。すると、若干点数が伸びるパターンが多かったので、提出してみることに。
これで99229点。思ったより伸びた。
でも、正直この方針ではこれ以上厳しそう。現状打破にはまた一つ発想を変える必要がある気がした。
ここまでの結果を振り返って、もう一度「バランス良くクラスタを作るより、無理矢理でも1つの大きなクラスタを作る方が有利」という最初の気づきを思い出す。コンピュータは100個ずつあるので、仮にこれを完璧に繋げられたなら 点になる。仮に50ケースこの点数が取れたなら
点となり、十分上位である。これを第一目標にやってみると良いのではないか？と考えた。
完璧に繋げることを目指すなら、「なるべく同じ行列に大クラスタ用のコンピュータを配置する、それ以外のコンピュータは大クラスタ用コンピュータが少ない行列ほど優先して配置する」という評価関数が良さそう。クラスタ用コンピュータが密集している行列はそこから接続を維持できる可能性が高く、逆に薄い部分は「繋ぎ」が欲しくなるケースが多そうだからだ。
よって、マンハッタン距離の和という評価関数から以下のような評価関数に変更した。
ただし、 は同一行（または列）に存在する大クラスタ構成用コンピュータの集合、
は同一行（または列）に存在する全てのコンピュータの集合。また、評価関数は先ほどと異なり大きいほど良いことを表す。10という係数は適当につけた。
午前の処理からこの評価関数だけ変えて（つまり移動フェーズだけ改善して）、様々なseed値で試すと、驚くべきことにほとんどのテストケースで4000点台後半の点数を出していた。
ここまで効くとは思っていなかったので普段より多くのseed値を試したが、概ね4000点台後半が出る。じゃあ大丈夫そう？と提出すると…なんと203406点という結果に。2倍以上伸びて流石に驚いた。
大方針としてはこの実装で間違いなさそう。後は、このアルゴリズムの弱点を潰して底上げをしていくことに決める。
8/14
今のアルゴリズムが弱いのは「コンピュータが多種類・高密度に存在する盤面」である。移動フェーズでの改善が困難なので、一手先読みでクラスタ同士が接続できないパターンが多く発生する。
基本的には、大きなクラスタ同士なら無理矢理でも結合した方がいい点数になるはず。そこで、「一手先読みにおいて改善できなくなったら、とにかく上下左右に接続を伸ばし続けて、点が増えるパターンがあるならその中のベストを採用する」という処理を追加した*1。
これで高密度パターンにある程度対処ができた。ただ、昨日までの処理で20万点（平均4000点）出たということは、おそらくテストケースに高密度・多種類のケースはあまり含まれていない。暫定テストではそこまで改善しないだろうと思いつつ提出すると207998点と、4500点ほどの増加になった。
最後に考慮しなければならないのは、「どの種類のコンピュータを優先して繋げるか」である。今は何も考えず 2 のコンピュータを優先している*2が、全パターン試して最も良いものを採用するのが筋ではある。しかし、今の処理では速度的にかなり厳しくなっており、「高密度（空きマスが100個以下の）ケースのみ全パターンの優先接続を試す」とした。
これで seed=0 では5033点取れるようになった。
提出してみると、210913点。これ以上アイデアは出ないので、細かいチューニングをしていくことに。
8/15
評価関数を少し調整して、「優先接続する種類以外も同様の計算式で評価値に加算する（ただし、優先接続 : その他 = 11: 1 の重み）」とした。そこまで意味は無いと思いつつ提出すると、213461点。2500点ほど増えたが、正直誤差な気がする。
他には移動フェーズの打ち切りを早めたり、評価関数の重み付けを凝ったものにしたりと色々試したが、スコアの上昇には繋がらなかった。これ以上のパラメータチューニングは無意味と考えて、最後の詰めとして処理の最適化を狙うことにした。この探索では2700ms以内に見つかった手の中で最善のものを出しているので、探索範囲が広がるほどより良い答えが得られる可能性が高まる。よって、最適化がスコア上昇に寄与するはず。
最適化や、微妙に残っていたバグの修正によってスコアは215674点になった。これでもう限界。
8/16
もう実装は間に合わないけど、30万点…つまり、平均6000点取るにはどうすれば良いのだろうと考えていた。「1つは完璧に繋げて、もう1つほぼ完璧に繋げる」くらいのことが出来ないとこの点数は届かなさそう。単純に考えると1つはなるべく外側に追いやって「囲い」のような形で接続し、もう1つは内側で団子にすれば良さそうだけど、これで完璧に繋げるにはどうすれば良いのかが分からない。
午後になって、ものすごい勢いで順位を抜かされ始める。最終日の追い込みヤバい。
少し評価関数を弄ったりしたが良い結果にはならなかったのでボツ。昨日の最終提出をファイナルアンサーとする。
やっておけばよかったこと
初参加で勝手が分かっていなかったところもありますが、こういうことをやっておけばよかったな、と思いました。
自動テスト
毎回Visualizerでコピペしていましたが、自動テストを行えるツールを作ればよかったな、と思いました。暫定テストに過学習してしまっているかのチェックもできるので…。今回は若干過学習気味だった気がします。
リファクタリング
特に、一手先読みあたりがとても汚いコードになりました。コードの汚さから来るバグもありました。落ち着いたタイミングで一度綺麗にしても良かったかもしれません。
