AHC056振り返り

はじめに

HACK TO THE FUTURE (AtCoder Heuristic Contest 056)に参加した．暫定順位としては100番台後半。

問題と大きな方針

問題は色とステートでアクションが決まるステートマシーンを使って全ての旗を回収するという問題。色の種類$C$とステートの数$Q$の和が小さい方が良い。正直言うと解法があまり思いつかなかった。最短経路をまず求めて、そらに状態をマッピングしていくのがいいのかな？という程度。

解法

最短経路のホップ数分状態を用意する

単純に最短経路の各状態をそのまま（色, ステート）の組みで表現してみる。(青, 0) → (赤, 0) → (黄色, 0) → (青, 1) → (赤, 1) → ... と推移していくイメージ。全部で$CQ$分の状態を表現できるので、$S$を最短経路長だとすると、$C = Q = \sqrt{S}$となる時が$C+Q$が最小となる。このため、スコアは$2\sqrt{S}$となる。経路を逆順にたどっていけば、塗るべき色も一意に決定できる。

配布された100問でスコアを計算すると7,276点。提出時に、同じ点数の人が多くいるかと思ったがそこまでいなかった。ここから減らしていくためには、状態か色を減らしていかないといけないのだけど、これといった方法が思いつかなかった。

圧縮してみる

最短経路は 'LRLRUUR...'という感じで4文字からなる文字列なので、これをLZ77的に圧縮してみてはどうかと思った。文字列を「単語」に分割して、単語を状態遷移で、単語間の遷移を色で表すというイメージ。ただ、長さ1000ぐらいの最短経路を圧縮しても合計100文字の単語にしかならなかった。これだと状態が100必要になるが、前述の方法だと$C + Q$が平均70になっているので、それより良くすることは難しい。ということでこの方法は却下。

状態を16個で固定する

状態を2回分の移動を示す16個で固定してみた。圧縮での「単語」の長さを固定長にしたイメージ。移動は上下左右の4種類なので、その2回分$4^2$で表すことができる。次の状態への遷移はマスの色で行う。1回目の移動は状態で一意に決まるので、マスの色を0に固定した。2回目の移動は0以外の色で次の状態遷移先を表す。このため、盤面が市松模様になっているのが特徴。
壁にぶつけたり、「移動しない」行動を使うと破綻してしまうが、最短経路ベースで解いているので問題ない。スタート地点の色は0に固定しているので問題ないが、状態は0でないので出力時に変換を入れる。

100問でスコアを計算すると14,057点。スコアとしては倍かかっているが、最適化の余地がありそうな気がする。

色数を固定する

前述のように状態数を固定すると、特定の状態からの遷移に使う色数が多くなってしまって無駄な感じになっていた。例えば、状態1と色20からの状態遷移があるとすると、別の状態$x$で色20を塗るような状態遷移が必要となる。このように使い回しがきかない状態ばかりが増えてしまっているので、色数を制限し、制限を超えた場合は状態を増やして色を共有できるようにしてみた。

1つの状態で、2回分の移動を表現するのは変えずに、各状態とセットとしてつかう色の数を制限する解法を実装した。100問でスコアを計算すると5,831点。最初の解放と比べて良いスコアをだすことができた。

おわりに

ここまでで時間切れ。最短経路の取り方で山登りなども考えてみたが、経路の評価式で良いものが見つからなかった。状態毎の出現バランスが取れていた方がいいのかとも思ったが、そうとも限らないようである。
最後まで計算して実際のスコアを求めるのは、時間がかかってしまうだけでなく、スコアは平均58点と小さいので、差がでてこなかった。