AHC064参加記
はじめに
AtCoder Heuristic Contest 064 に参加し、440位(perf 1298)でした。
成績は芳しくないですが、参加記を残そうと思います。
問題
https://atcoder.jp/contests/ahc064/tasks/ahc064_a
指定された線路に車両を指定された順番に少ないターン数で並べていくのが目的。
線路には最終的に列車がならぶ出発線のほか、バッファ的な意味合いの待機線がある
車両は全部で100台、出発線・待機線はそれぞれ10列。
列車は出発線ー待機線間を移動可能（出発線同士、待機線同士の直接移動は不可）
1ターンに車両が衝突しない限り（＝移動線が交錯しない限り）同時に複数の移動が可能
解法
ルールベースで車両を1台ずつ順番に揃えていく方法を採用しました。
ターゲットとする車両（以下、対象車両）を以下の3ステップで目的の場所へ運びます。
1. 対象車両を待機線の先頭へ移動
対象車両が出発線、待機線のどちらにいるかで分岐します。
- 出発線にいる場合：その列の末尾から対象車両までを待機線へ移動。
- 待機線にいる場合：対象車両より前にある車両を、目的以外の出発線へ一時退避
2. 目的地の整理
目的の出発線にある邪魔な車両を、対象車両がいる待機線とは別の待機線へ移動。
3. 目的地への移動
対象車両を待機線から目的の出発線へ移動。
出発線・待機線間の移動は、物理的な距離が近くなるものを優先して選択しました 。
処理順は「IDの下1桁（＝格納先の列番号）」が小さい順とし、同グループ内はランダムに決定。制限時間いっぱい試行してベストなスコアを採用しました。
最後に、全手順を見直して独立して行える（＝移動線が交錯しない）操作を1ターンに集約する後処理を行っています。
反省点
車両をひとつずつ処理することに縛られてしまった
この手順に縛られている限り、一つの車両を正しい位置に移動させ終わるまで、ほかの車両のことを考慮することが全くできません。
この手順の制約が大きすぎて改善する余地がほとんどありませんでした。
車両の処理順を一部ランダム化して山登り（あるいは多点スタート）のような形を試しましたが、ルールベースの制約が強く、スコアの改善幅は限定的でした。
ターンの操作手順をまとめる処理を全部後回しにした
一通り最後まで操作した後、最後にターンの操作手順をまとめるというアプローチもよくなかったです。随時1ターンに入る操作手順をまとめるようにしていれば、1ターンに可能な限り操作を押し込むという貪欲法に発展させていく余地が残っていたのですが、こうしてしまったことで改善余地がなくなってしまいました。
実装にリソースを持っていかれた
上記のルールベースを実装して初回提出するまでに2時間弱かかっているので、相対的にみると実装に時間かけすぎかなと思います。
ベースとなるコードは自分で書いて、その後AI使いつつ改善、と思っていましたが、実際やってみると実装面に時間的にも思考的にもリソースを終始持っていかれてしまいました。
上記2つの反省点が残ったのも、実装面にリソースを割かれた影響が無きにしもあらずということを思えば、ちょっとコンテストの立ち回りとして悪かったと思います。
頭の中で固まっていたルールベースの細かな実装は、もっと積極的にAIに任せられるような動きができるよう意識したいと思います。
感想
結果としては残念でした。ここ最近短期コンテストの成績が芳しくありませんが、基礎を固めるための参加と割り切って頑張ろうと思います。
問題はとても面白かったです。取り組んでいる時もそうでしたが、解説放送を見ていろいろなアイディアがあることを知って、発想次第ですごい改善ができるんだなと、ただただ感心してしまいました。
いい刺激が得られたのでまずは復習を頑張ろうと思います。
