AHC021 解説

2023年7月10日 04:48

TOYOTA Programming Contest 2023 Summer（AtCoder Heuristic Contest 021）のコンテスト中 & 後に考えたこと、あと提出の内容と得点について書いています。
最終的にはコンテスト後に13,561,410点で本番9位相当の解法になります。

方針立て

問題を読む限りでは、

のどちらかが良さそうです。中途半端な数から順番に移動させると、移動させたものを再度移動させるような動きが発生するからです。

それで、この二つの方法を比較すると、大きい数から順番に下に持っていく方法はどの位置に置くのが良いかがわかりづらいです。
例えば

小さい数から順番に上に持っていく方法だと、0のボールは初期位置がどこにあってもピラミッドの一番上にしかおけません
大きい数から順番に下に持っていく方法だと、$${N \times (N+1) / 2 - 1 = 464}$$のボールは初期位置によってどこにおけばいいか選択肢が多いです。
- 464が最下段にある場合は、それより下に数字がないので動かさなくて良さそう
- 464が(0, 0)の位置にある場合は、最下段のどの位置に置こうとしても手数は変わらない

です。選択肢が多い割にメリットが見えなかったので、小さい数から順番に上に持っていく方法で実装を考えます。

次に問題になるのは小さい数を上に持っていく際の経路選択です。ぱっと見は

ということで、上2つのうち、大きい数と交換する、という方法を取ればとりあえず初期解として良さそう、と思っていました。

ここまででオンサイトの出場権は取れる解になるのですが、

と思ってこの解法を実装せず、ここからさらに別の方針に走り、点数を悪化させて305位となってしまいました。。。

さて、点数を悪化させた方針についてですが、こちらもなんだかんだで最終解法に考えをそのまま転用するので続いて記載します。

処理するボールは小さい順のままで、盤面を評価する関数を作成し、その評価値が最大または最小になるような移動を貪欲にするだけです。
具体的には

ピラミッドの上の方に小さい数字、下の方に大きい数字が来て欲しい $${\rightarrow}$$ ピラミッドの下に行くほど重みを大きくし、ボールの数字とその重みを掛け合わせて総和をとったものが大きい方が高評価になるようにする
ピラミッドの外側に小さい数字、内側に大きい数字が来て欲しい $${\rightarrow}$$ ピラミッドの外側に行くほど重みを大きくし、ボールの数字とその重みを掛け合わせて総和をとったものが大きい方が高評価になるようにする
先述の通り、基本的には上に持っていくので、2より1の方の重みを大きくする

と言った感じで評価関数を実装して、その値が大きい方に移動させる方針をとりました。

方針立てのところに記載した通りです。

13,139,945 点解法からたまに経路選択を乱択にし、制限時間いっぱいまで回して一番最小手数になったものを出力するようにしたものです。

小さい方から順番に上へ持っていく & 交換する数字は大きい数字を選ぶ貪欲法です。

方針立てで記載した評価関数を用いてのビームサーチです。ビーム幅は55。

具体的には1ステップの処理で

小さい数から順番に上に持っていく方法で、動かさなければならない一番小さい数について左 / 左上 / 右上 / 右の4方向の移動をさせる
移動させた後の状態数がビーム幅以下だった場合はそのまま次のステップに進む
移動させた後の状態数がビーム幅より大きい場合は、ビーム幅の数の分だけ以下の優先度順で状態を選択する
1. 次に動かさなければならない一番小さい数が大きい順
2. 評価関数が大きい順

を行います。一番最初に終わったものを出力します。