takumi152の競プロ日記

競プロとかその他諸々とかの記録

ALGO ARTISプログラミングコンテスト(AHC010) 参加記

ALGO ARTISプログラミングコンテスト(AHC010)に参加しました。

結果は1位/1400人*1で、優勝でした。初優勝なのでとてもうれしいです。

ということで、以下に今回の解法や感想について書いていきます。

問題

グリッド上に曲線状・直線状の線路が乗った正方形タイルが置いてあるので、タイルを回転させてできるだけ長いループ*2を2つ作ってね。
2つのループの長さの掛け算がそのまま点数になるよ*3。

atcoder.jp

解法（簡易版）

以下のツイート(とリプ欄)を参照してください。

最終提出時のコードはこちらです。

atcoder.jp

解法（もっと詳しく）

主に以下の2つを使って解を求めました。

最終的な解法では、焼きなまし法を中心として、それに使う状態遷移の方法として乱択DFSによるループ経路の変更を使っています。

本記事ではこの2つについて順に説明を記載していきます。

なお、本記事では、各線路タイルの名称について、1本の曲線状レールが乗ったもの*4を曲線(1)レール、2本の曲線状レールが乗ったもの*5を曲線(2)レール、1本の直線状レールが乗ったもの*6を直線レールと呼ぶことにします。

左から順に、曲線(1)レール、曲線(2)レール、直線レールの例

乱択DFSによるループ経路の変更

あるループについて、「ループの一部を壊して、壊した部分を別の経路に置き換える」ということを考えます*7。

ループの一部分を別の経路に置き換えるイメージ。青矢印から赤矢印までで示した区間の経路を置き換えている

始点と終点を決めた後、進入先タイルの座標、タイルの進入方向、各タイルの2つのループ中での使用回数*8を管理しながら、終点のひとつ先のタイルと座標・進入方向が一致するところに到達するまでDFSをします。このとき次に進入するタイルの種類に応じて以下のように場合分けをしながら探索します。

曲線(1)レールの場合

タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます。

まず0回の場合、そのタイルはループ中ではまだ使われていないので、適切にタイルを回転させることで、進入方向から見て90度時計回り、90度反時計回りに回転した方向のどちらにも進むことができます。
最初にどちらに進む方を探索するかはランダムに決めてしまってよいです*9。

使用回数が0回の曲線(1)レールに左から進入する例。適切にタイルを回転させることで上下どちらにも進むことができる

次に1回の場合ですが、そのタイルはループ中で使われているので、タイルを回転させてしまうとループが壊れてしまいます*10。
また、タイルへの出入口は2方向しかないことと、ループで1回使われているということから、必ず出入口ではない方向から進入することが分かるので、そのタイルには進むことができません。

使用回数が1回の曲線(1)レールに左から進入する例。既存の青色で示したループが壊れるので進むことはできない

曲線(2)レールの場合

同様に、タイルの使用回数が0回と1回の場合でそれぞれ分けて考えます*11。

0回の場合は曲線(1)レールの場合と同様です。ただし、後から同じタイルを再び通る可能性があるので、タイルの回転を探索中の時点で行っておく必要があります。

次に1回の場合、曲線(1)レールの場合と同じく回転させることはできませんが、まだ使っていない側のレールの進行方向には進むことができます。

使用回数が1回の曲線(2)レールに左から進入する例。回転はできないので上方向にのみ進める

直線レールの場合

同じくタイルの使用回数が0回と1回の場合で分けて考えます。

0回の場合、適切に回転させることで進入方向と同じ方向に進むことができるので、同じ方向にある次のタイルを探索すればよいです。

1回の場合は、曲線(1)レールの場合と同様にループが壊れてしまうので進入することはできません。

その他

以上のように場合分けして探索をすればよいですが、乱択なので行きたい方向とは全く別の方向に探索が進んでしまい、非常に時間がかかってしまう可能性があります。
そのため、探索ステップ数や探索時間に上限を設定して、上限に達したら探索を打ち切って元のループを復元することにしています。

この手法が使える類題として、短期コンテストではAHC002、長期コンテストではMM119などがあります*12。
（AHC002は移動方向に対する制約が少なく、実装も今回に比べて単純なので、そちらで練習してみるのもおすすめです。）

焼きなまし法

典型的な焼きなまし法です。焼きなまし法自体の解説はgasinさんやツカモさんの記事などが詳しいのでそちらにお任せすることにします。

gasin.hatenadiary.jp

qiita.com

解の持ち方

焼きなましにおける解の持ち方ですが、現在の盤面のタイルの種類*13と、ループごとに経路情報を表す(タイルのx座標, タイルのy座標, このタイルから出る方向)の組の列を状態として持つことにしています。

初期解

盤面の初期状態の時点で存在しているループの中から、中心までのマンハッタン距離が最も近い2つのループを選択します*14。
選択した2つのループについてそれぞれの経路情報を求め、これを初期解とします。

状態遷移

状態遷移は1種類のみで、どちらか1つのループの中からランダムに始点と終点を選択して、その区間について「乱択DFSによるループ経路の変更」の項で説明した方法で新しい経路を探索する、というものです。
探索が(打ち切られずに)終了して新しい経路が求まったら、後述の評価関数で新しい経路を使った場合の評価を行い、状態遷移を行うかどうかを決めます。

評価関数

評価関数は2種類用意して、前半と後半に分けてそれぞれ使用する評価関数を変更しています。

前半は2つのループの長さの線形和を評価関数としています(最終提出時の解法では 10 \times \min((ループ1の長さ), (ループ2の長さ)) + \max((ループ1の長さ), (ループ2の長さ))としました)。
この問題の(本来の)スコア計算方法では、現在の解のスコアが大きくなるほど、ループの長さが1だけ短くなったときのスコアの下げ幅が大きくなりやすくなり、温度が同じでもスコアが下がる遷移が起きにくくなるのであまり望ましくないと考えられます。
そこで、ループの長さによるスコアの下げ幅が大きくならないようにすればそのようにならなくなるのではないかと思い、この評価関数を使うことにしました。

後半は問題のスコア計算方法と同じものを評価関数としています。

結果

以上の解法により、最終提出時での点数は20,218,968点となりました。
本番中に20M点台を出したのは自分一人だけだったようです*15。わーい。

実際の出力の結果ですが、例えばseed = 0の場合は以下のようになります。

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

本番中にやったことや考えていたことを時系列順に書いています*16。

0:00 - 開始

問題文を読んだ。 ビジュアライザを確認するとmanual modeが用意されているみたいなので試すことに。

0:10 - 考察

manual modeで試してみている過程で、以下のようなことを思った。

  • 既存のループを少しずつ大きくしていくとよさそう。
  • タイルは回転しかできないので、今のループを少しだけ変えて大きくするのは難しそう。
  • 一方で、今のループを一旦壊して別の経路を作ろうとすると、手で適当にDFSっぽいことをすれば普通に作れる
    • ループを壊す部分は、今のループのうち曲線部分2つの向きを変えればできそう

経路を部分的に破壊して別の経路を作るといえば、AHC002で似たようなことをした覚えがある。
・・・ということは、これはAHC002の類題か？だとしたら部分経路破壊+乱択DFSでの再構築と、焼きなましを使えばよさそう。

0:15 - 実装(前編)

実装開始。とりあえず初期解を選ぶところ(と、それに必要なループ判定)から実装。

初期解を選ぶときに回転を考えながらやるのは面倒なので、最初から既にあるループの中から適当な2つを選ぶことにする。
入力を20種類ほど確認してみたが、どれもループは少なくとも2つあるので、とりあえずこれで進めてしまってよさそう。

あとは、端の方にあるループを選択してしまうと大きくできないまま詰まってしまう気がするので、できるだけ中央に近いループを選択することにする。

1:15 - 実装(中編)

初期解の選択を実装した。続けて焼きなまし部分と経路再構築部分の実装に入る。

ループの状態をどう持つべきか悩ましいが、とりあえず各ループが通る位置とその方向を、ループごとに 30 \times 30の配列で持つことにした*17。

2:00 - 実装(後編)

経路再構築部分の実装をしていたが、考えていたループの状態の持ち方ではうまくいかないことが分かった。

最初に考えたループの状態の持ち方で対応できないケースの例

仕方がないのでループの状態を変えて、ループごとに(x座標, y座標, タイルから出る方向)の組の列で持つことにする。

この時点では、実装が間に合わずに提出しないまま終わってしまうのではないかと思ってかなり焦っていた。

2:45 - デバッグ

一通り実装が完了した。が、segmentation faultで落ちていたり、コード側で求めたスコアが実際のスコアと一致しなかったりと、バグが多い状態。
幸い、ちゃんとassertを入れていたことで、大部分については何が起きているかすぐに分かって、どこにその原因があるかを探すだけだったので、複雑な実装をした割にはスムーズにデバッグができた。

また、この時点でも100k点程度が出るケースがあることは確認できていたので、方針としては正しそうだと思った。

3:35 - 初提出

デバッグが完了し、初提出。11.044M点(最終18位相当)を出した。

3:40 - パラメータ調整(1)

残り時間が少ないので、あまり大きな改善はできなさそう。
とりあえずパラメータ調整をまともにやらないまま提出をしていたので、まずは焼きなましの温度を手で調整して、200k点程度出るケースがあることを確認して再提出。19.799M点を出して暫定1位になった*18。

3:45 - パラメータ調整(2)

この時点でも既に勝ちを確信しつつあったが、逃げ切るためにさらに改善を入れることに。
次は試行回数を増やすため、経路再構築時のDFSの探索回数上限を下げた。点数が何となく上がっていそうなことを確認して提出したところ、20.131M点が出た。

3:50 - 評価関数の改善

これ以上調整できそうなパラメータは無さそうなので、今度は評価関数を改善することにした。
これまでは問題のスコア計算方法をそのまま評価関数にしていたが、これだと点数が上がるほど状態が戻りにくくなってしまい良くないので、先にループの長さの線形和を評価関数として焼き、その後本来のスコアで評価することを考えた。
この時点では小さい方のループの長さだけを使っていたためか、点数は改善しなかった(20.064M点)。

3:59 - 最終提出

最初に使う評価関数で長い方のループの長さも使うよう変更。
パラメータ調整もさらに行ったところで最終提出を行い、20.218M点で終了した。

感想

途中までは実装方針のミスなどでタイムロスがあり、どうなるかと思いましたが、結果として優勝することができたのはとてもうれしいです。
ヒューリスティックレートも2533 → 2757になり、†レッドコーダー†入りが一気に現実に近くなりました*19。

今回の問題は以前の4時間コンテストと比べると少し複雑な印象でしたが、4時間コンテストの難易度感・実装量としてはちょうどいいぐらいかなと思いました*20。

*1:うち提出者678人、正の得点を得た参加者660人

*2:問題文中では「環状線」と呼んでいますが、本記事では「ループ」で統一することにします。

*3:作られたループが3つ以上なら、その中で最も長い2つだけが点数計算に使われます。

*4:問題文中では0～3番のタイルが該当します。

*5:問題文中では4, 5番のタイルが該当します。

*6:問題文中では6, 7番のタイルが該当します。

*7:ここでは「壊す」と書いていますが、実際の処理ではその区間に含まれるタイルのループ中での使用回数を減らしているだけです。

*8:DFSで探索中のものも含みます。

*9:乱択なので。

*10:場合によっては回転させることで新しいループが完成することがありますが、ここでは面倒なので考えないことにします。

*11:厳密には2回の場合もありますが、この場合はそのタイルに進入する方法がないので、ここでは考える必要はありません。

*12:グリッド上などでできるだけ長い経路を求めたいときに使える印象があります。

*13:出力する解自体は、この情報だけから求めることができます。

*14:初期盤面によっては最初から存在するループが1つ以下の場合もあり得ますが、採点用のテストケースではそのようなケースはなかったようなので特に考えていません。

*15:ちなみに2位のRafbillさんは19,646,280点でした。

*16:本番中にこの辺の内容を書く余裕は無かったので、終わった後にうろ覚えで書いています。ご了承ください。

*17:下でも書いているが、実際はこの方法だと、曲線が2つあるタイル上を1つのループが2回通る場合に対応できない。

*18:この時点で最終1位相当の点数になっていた。

*19:次に2890perf(4位相当)程度以上を取るとレッドコーダーになれるらしい。

*20:難易度に対する個人的な思想ですが、解として詰め切れていそうな人が2, 3人程度で、パラメータ調整や乱数お祈りだけでは優勝できないぐらいが丁度良いと思っています。