はじめに
JR西日本・ALGO ARTIS プログラミングコンテスト（AtCoder Heuristic Contest 064）に参加しました。
結果は 35位、performance 2402、score 742,777 でした。
最終提出: 提出コード
問題は A - Non-Crossing Railcar Rearrangement です。
出発線と待避線の間で車両を移動し、各出発線に指定された順序で車両を並べ直す問題です。
最終的な解法は、ざっくり言うと次のような方針でした。
正しい連続ブロックを壊さないようにしながら、
非交差な複数操作を1ターンとして生成し、
差分更新ビームサーチでターン数を削る。
また、今回の 実装には生成AIをかなり利用しました。
実装面をAIに補助してもらうことで、実験や考察に時間を使えたのが大きかったです。
この記事では、最終解法だけでなく、初手の構成解からどのように改善していったか、どの変更で悪化したかも含めて参加記としてまとめます。
問題概要
問題文はこちらです。
出発線が R 本、待避線も R 本あります。
全ケースで R = 10 です。
初期状態では、各出発線に10両ずつ車両が置かれており、待避線は空です。
車両 ID は 0..99 の順列で与えられます。
目標は、各出発線 r に
10r, 10r+1, ..., 10r+9
を先頭から順に並べることです。
操作は2種類あります。
type = 0:
出発線 i の末尾から連続する k 両を取り出し、
待避線 j の先頭に連結する。
type = 1:
待避線 j の先頭から連続する k 両を取り出し、
出発線 i の末尾に連結する。
1ターンには複数の操作を同時に実行できます。
ただし、同じ出発線・待避線を同一ターン内で2回以上使ってはいけません。
さらに、出発線 i1 < i2 に対応する待避線が j1, j2 なら、j1 < j2 でなければなりません。
つまり、同一ターン内の操作は 非交差 である必要があります。
完全一致した場合のスコアは
100R + 4000 - T
です。
R = 10 なので、1ケースあたりの完全一致時スコアは 5000 - T です。
全150ケースなので、全ケース完全一致している提出については、
合計ターン数 = 750000 - 提出スコア
としてターン数を読むことができます。
解法の要約
最終解法は、出発線・待避線の状態をそのまま持ち、1ターン分の操作集合をビームサーチで選んでいく方針です。
大まかな流れは次の通りです。
- 出発線→待避線、待避線→出発線の候補操作を生成する
- 非交差制約を満たす複数操作を1ターンとしてまとめる
- 1ターン適用後の状態を評価関数で評価する
- 評価値の高い状態をビームに残す
- hash によって重複状態を除く
- 状態更新・評価・hash 更新を差分更新して探索量を増やす
評価関数では、単に「今すぐ何両揃っているか」だけでなく、後でまとめて揃えやすい形になっているかも見ました。
具体的には、次のような観点を重み付きで足し引きしました。
・出発線の先頭から正しく揃っている部分が長いか
・待避線の先頭から出発線へすぐ戻せるブロックがあるか
・目標順に隣接している連続ブロックを作れているか
・次に必要な車両を取り出すための邪魔な車両が少ないか
・出発線や待避線の容量に余裕があるか
要するに、現在の完成度と、将来の戻しやすさの両方を評価しました。
評価項目の詳細は、後半の「評価関数」で説明します。
最初からこの形ができていたわけではなく、まずは確実に完全一致する構成解を作り、それをベースラインとして改善していきました。
初手解法では「全て待避線へ振り分けてから戻す」という2段階に分けていましたが、最終解法ではその分離をやめ、戻せるブロックは途中で戻すように探索しました。
最初の考え
問題を読んだ時点で、完成済みの操作列に対して焼きなましなどで後から改善するよりも、構築途中の状態を選んでいくビームサーチのほうが向いていそうだと感じました。
理由は、この問題では操作列の一部を後から変更するのがかなり難しそうだったからです。
各操作は、出発線の末尾と待避線の先頭しか触れません。
さらに、同一ターン内では非交差制約も満たす必要があります。
そのため、完成済みの操作列に対して1ターンを削除したり、2つの操作を入れ替えたりすると、容量制約、非交差制約、車両の順序がすぐに壊れ、近傍設計がかなり難しそうでした。
一方で、この問題にはビームサーチで評価しやすそうな構造がありました。
- 出発線の先頭から正しく揃った
prefixは基本的に壊さなくてよい -
10r+i, 10r+i+1のような正しい連続ブロックは将来そのまま使えそう - 次に揃えたい車両を取り出すための
blocker数を評価できそう - 待避線の先頭にあるブロックが、出発線の
prefixに接続できるかを評価できそう - 同一ターン内の操作は、非交差な matching として生成できそう
そのため、方針としては最初からビームサーチを意識していました。
ただし、いきなり本格的なビームサーチを書くのではなく、まずは確実に完全一致する構成解を作ることにしました。
これは、ベースラインを作るためでもあり、ビジュアライザで車両の動きを観察して、どのような操作が無駄になっているかを見るためでもあります。
実際に完全一致する操作列を出してビジュアライザで見ると、次のような無駄が見えました。
- すべての車両を一度待避線へ振り分けてから戻しており、往復が多い
- 待避線内の順序が悪く、目的車両の前にある
blockerを何度も一時退避している - 途中で出発線へ戻せそうなブロックまで、最後まで待避線に置いている
- 正しい順序の連続ブロックができているのに、それを十分に活用できていない
ここから、ビジュアライザで見えた無駄をもとに、ビームサーチの遷移候補や評価関数をルールベースで改善していく方針にしました。
初手提出：まず完全一致する構成解を作る
初手提出では、次の2段階の方針を取りました。
1. 各車両を、目標出発線ごとの待避線へ振り分ける
2. 待避線から 0,1,2,...,9 の順に出発線へ戻す
車両 car の目標出発線は
car / 10
です。
そのため、まず各出発線の末尾から、同じ目標出発線に属する連続区間をまとめて取り出し、対応する待避線へ送ります。
例えば、ある出発線の末尾側が
... 31 34 35
なら、34 35 はどちらも目標出発線3に属するので、まとめて待避線3へ送ることができます。
このとき、1ターンに複数の出発線から待避線へ移動できるなら、できるだけまとめたいです。
ただし非交差制約があるため、出発線 i と待避線 j の対応が単調増加になるように選ぶ必要があります。
初手コードでは、出発線集合を bitmask で選び、
・その mask で同時に動かせるか
・何両動かせるか
・残りを処理する下界がどの程度か
・待避線内の inversion がどの程度か
を見て、clearing phase の順序を小さめのビームサーチで探索しました。
この初手の時点でも、BEAM_WIDTH = 2000、ACTION_LIMIT = 20、MAX_CLEAR_DEPTH = 90 としていました。
clearing phase が終わると、各待避線 r には、目標出発線 r に属する車両だけが入っています。
あとは、待避線 r から
10r, 10r+1, ..., 10r+9
の順に取り出して出発線 r へ戻せばよいです。
ただし、目的車両が待避線の先頭にあるとは限りません。
目的車両の前に blocker がある場合は、それらを一時的に隣の出発線へ逃がしてから目的車両を取り出します。
具体的には、偶数行と奇数行を分けて、偶数行では隣の奇数行、奇数行では隣の偶数行を一時退避先として使うような処理にしました。
この方針で初手提出し、スコアは 736,891 でした。
全ケース完全一致しているとすると、合計ターン数は
750000 - 736891 = 13109
なので、平均ターン数は
13109 / 150 ≒ 87.39
です。
初手時点で、平均90ターン弱で完全一致する構成解ができました。
ここから先は、完全一致できるかどうかではなく、どうやってターン数を減らすかが主な課題になりました。
初手解法から見えた課題
初手方針は安定していましたが、無駄も多かったです。
一番大きい問題は、
すべて待避線に振り分ける
その後、改めて出発線へ戻す
という2段階が強すぎることです。
実際には、途中で出発線へ戻せる車両や、すでに良い順序になっているブロックがあります。
それらまで一度すべて待避線に出してしまうと、余計なターンが増えます。
また、待避線内の順序もあまり制御できていませんでした。
各待避線には正しいグループの車両だけが入りますが、順序が悪いと sorting phase で blocker を何度も一時退避する必要があります。
そこで、次のような改善が必要だと考えました。
1. 全部退避してから戻すのではなく、途中で戻せるものは戻す
2. 待避線内の順序も評価する
3. 正しい連続ブロックを作り、それを壊さない
4. 1操作ではなく、1ターンにまとめた操作集合を探索する
このあたりから、本格的にビームサーチで状態を持つ方向へ移りました。
スコア推移
主な提出スコアは次のように推移しました。
完全一致している提出については、
合計ターン数 = 750000 - スコア
として換算できます。
| 段階 | スコア | 初手からの差分 | 合計ターン換算 | 平均ターン換算 | 主な内容 |
|---|---|---|---|---|---|
| 初手 | 736,891 | - | 13,109 | 87.39 | 目標出発線ごとに待避線へ分類し、あとで順に戻す構成解 |
| 改善1 | 742,419 | +5,528 | 7,581 | 50.54 | 状態全体を持つビームサーチへ変更 |
| 改善2 | 742,499 | +5,609 | 7,501 | 50.01 | 評価関数・候補生成の微調整 |
| 改善3 | 742,769 | +5,878 | 7,231 | 48.21 | 待避線から戻しやすい状態や連続ブロック評価を強化 |
| 悪化1 | 738,789 | +1,898 | 11,211 | 74.74 | 評価重み変更で探索が近視眼的になり悪化 |
| 悪化2 | 690,636 | -46,255 | 59,364 | 395.76 | 枝刈り・評価変更の組み合わせが大きく失敗 |
| 最終 | 742,777 | +5,886 | 7,223 | 48.15 | 差分更新・hash・固定長配列まわりを詰めて微改善 |
最終的には、初手の平均約87.4ターンから、平均約48.2ターンまで削ることができました。
大きな改善は、736,891 -> 742,419 の部分です。
ここで、単なる構成解から、状態全体をビームサーチする方針へ移りました。
その後の 742,419 -> 742,769 は、評価関数や候補操作の改善によるものです。
最後の 742,769 -> 742,777 は差分8点なので、平均では約0.05ターンの改善です。
この段階では、大きな方針変更というより、実装高速化やパラメータ調整の詰めでした。
なお、690,636 の提出は、全ケース完全一致していた場合に平均約395.8ターン相当です。
実際には一部ケースで完全一致できていなかった可能性もあります。
いずれにせよ、評価や枝刈りを変えると大きく崩れることが分かりました。
最終解法
状態と操作
初手では clearing phase と sorting phase が分離していました。
最終的にはこれをやめて、出発線・待避線の状態そのものを持ち、
出発線 -> 待避線
待避線 -> 出発線
の両方をビームサーチの遷移として扱いました。
状態は概ね次のように持ちます。
struct Line {
unsigned char n;
unsigned char a[20];
};
struct State {
array<Line, 10> d; // 出発線
array<Line, 10> s; // 待避線
long long value;
uint64_t hash;
};
出発線の容量は15ですが、実装上は待避線容量20に合わせて固定長配列で持っても問題ありません。
vector を使うとコピーやメモリアロケーションが増えるため、固定長配列を使いました。
操作は次の形式です。
struct Move {
unsigned char type;
unsigned char i;
unsigned char j;
unsigned char k;
};
1ターンに複数操作できるので、遷移は Move ではなく Turn として扱いました。
struct Turn {
SmallMoveList ms;
};
1ターンを1遷移として扱うことで、スコアに直結するターン数を直接減らしにいけます。
非交差な1ターンの生成
同一ターン内では、出発線と待避線の対応が交差してはいけません。
操作を (i, j) のペアとして見ると、i1 < i2 なら j1 < j2 である必要があります。
これは、候補操作集合から 単調な matching を選ぶ問題として見られます。
実装では、まず単独操作候補を作り、それらを組み合わせて1ターンを作ります。
候補操作には主に次のものを入れました。
1. 目的車両を露出させる操作
2. 待避線から出発線 prefix に接続する操作
3. 正しい連続ブロックを作る操作
4. 容量に余裕を作る操作
1ターンに操作を追加するときは、次を確認します。
・同じ出発線を使っていない
・同じ待避線を使っていない
・出発線 index と待避線 index の対応が非交差
・容量制約を満たす
擬似コードは次のような形です。
void build_turns() {
cur = {empty turn};
for (int i = 0; i < R; i++) {
nxt = cur;
for (partial in cur) {
for (op in candidate_ops_by_departure[i]) {
if (op.j <= partial.last_j) continue;
nxt.push(partial + op);
}
}
keep_top(nxt);
cur = nxt;
}
}
全列挙すると重いので、各出発線ごとの候補数、部分解数、最終的に残す Turn 数には上限を設けました。
最終付近では、候補操作を最大90個、各出発線あたり最大12個、部分解を最大45個、最終的に1状態から最大18個の Turn を出すような設定にしていました。
評価関数
最終的な評価関数は、概ね次のような形です。
value =
+ fixed prefix
+ completed clean line
+ ready commit
+ ready load
+ chain score
+ correct position
+ correct line
- target blockers
- dirty suffix
- capacity penalty
実装上は、各項にかなり大きな重みを掛けています。
特に fixed prefix は非常に強くしました。
fixed prefix
各出発線 r について、
10r, 10r+1, ...
と先頭から正しく並んでいる長さを数えます。
これは最重要の評価項です。
出発線から取り出せるのは末尾側なので、一度できた正しい prefix は基本的に壊さなくてよいです。
そのため、完全一致へ向かう進捗として非常に信頼できます。
ready commit / ready load
ready commit は、待避線の先頭に、ある出発線の prefix 直後へそのまま接続できるブロックがある場合に加点します。
例えば、
出発線 5: 50 51 52
待避線 j: 53 54 ...
なら、53 54 を出発線5へ戻すだけで prefix が伸びます。
このような状態は次のターンで強いので、高く評価しました。
ready load は、次に必要な車両が出発線の末尾側に露出しており、すぐ待避線へ動かせる場合に加点します。
例えば、出発線 r の次に欲しい車両が 10r+p で、それが別の出発線の末尾にあり、しかも 10r+p, 10r+p+1, ... という連続ブロックになっているなら、そのブロックは価値があります。
target blockers
次に必要な車両を取り出すために、どれだけ邪魔な車両があるかを評価します。
出発線にある場合は、その車両より末尾側にある車両が blocker です。
待避線にある場合は、その車両より先頭側にある車両が blocker です。
blocker が少ない状態ほど、次に prefix を伸ばしやすくなります。
chain score
途中からかなり重要になったのが chain score です。
これは、正しい連続ブロックを評価する項です。
例えば、
41 42 43
というブロックは、まだ出発線4に置かれていなくても価値があります。
将来的に 40 の後ろへ接続すれば、そのまま使えるからです。
最初は prefix を強く評価していました。
しかし、それだけだと、
今すぐ1両だけ prefix は伸びるが、
待避線が汚くなって後半でターン数が増える
という状態を選びやすくなりました。
そこで、今すぐ prefix が伸びるかだけでなく、将来 prefix に接続できる部品ができているかを評価するようにしました。
たとえば、10r+i と 10r+i+1 がつながったら、それは小さな完成部品と見なせます。
この部品は基本的に分割したくありません。
初手では、
車両 car は car / 10 の待避線へ入れる
という粒度で考えていました。
しかし、スコアを伸ばすには、それだけでは粗すぎました。
最終的には、同じ目標出発線に属するかだけでなく、その中で正しい順序の連続ブロックになっているかを見るようになりました。
その他、すでに完成していて触る必要のない出発線、正しい出発線にある車両数、正しい位置にある車両数も補助的に評価しました。
逆に、正しい prefix の後ろに余計な車両が残っている状態や、容量上限に近く次の操作が打ちにくい状態にはペナルティを入れました。
差分更新ビームサーチと高速化
本格的にビーム幅を広げるには、状態コピーが重くなります。
普通に書くと、
State ns = st;
apply(ns, action);
evaluate(ns);
のように、候補ごとに状態をコピーすることになります。
しかし、この問題では各状態から多くの候補ターンを生成します。
そのため、状態コピーや全評価を毎回行うと探索量が制限されます。
そこで、差分更新ビームサーチを使いました。
参考にしたのは、thunder さんの差分更新ビームサーチの記事です。
この記事では、状態を丸ごとコピーするのではなく、
expand
move_forward
move_backward
の形で、状態を進めたり戻したりしながら候補を評価する考え方が説明されています。
自分の実装でも、これに近い形にしました。
move_forward(action);
evaluate();
move_backward(action);
1つの状態をDFS的に進め、候補を評価したら戻します。
これにより、候補ごとに State 全体をコピーする回数を減らせます。
また、状態の重複除去には hash を使いました。
1回の操作で変わるのは、基本的に出発線1本と待避線1本です。
そのため、各線の hash を持っておき、変更された線だけ差し替えれば十分です。
hash ^= old_line_hash;
apply_move();
hash ^= new_line_hash;
のような形です。
最終版に近づくにつれて、アルゴリズムの大枠というより、細かい実装高速化も重要になりました。
主に行ったのは次のような改善です。
・vector<Move> を固定長の SmallMoveList に変更
・候補操作リストを固定長配列に変更
・TurnList も固定長配列に変更
・unordered_map を自前の open addressing hash に変更
・calc_hash の全再計算を避け、変更された線だけ hash 更新
・same_next(a,b) を事前計算テーブル NEXT_OK に変更
・car / 10, car % 10 を ROW_OF, POS_OF に事前計算
・候補選択に nth_element を利用
・memcpy / memmove を使って線の移動処理を軽くする
この段階では、スコア改善は大きくありませんでした。
ただし、2秒制限の中でビーム幅や候補数を維持するためには重要でした。
最終的には BEAM_WIDTH = 1275、TIME_LIMIT = 1.975 付近まで攻めました。
失敗した変更
スコア推移で特に重要なのは、次の悪化です。
742,769 -> 738,789 -> 690,636
AHCでは、良さそうに見える変更でも普通に悪化します。
今回も、評価関数や枝刈りを変えた提出で大きく落ちました。
ready commit を強くしすぎる
待避線からすぐ出発線へ戻せるブロックは強いです。
しかし、これを強くしすぎると、今すぐ戻せるものばかりを優先してしまいます。
その結果、より長い連続ブロックを作るための整理操作や、後半を楽にする操作が残りにくくなりました。
枝刈りを強くしすぎる
高速化のために候補数を削りたくなります。
しかし、この問題では一見弱そうな操作が、数ターン後に良いブロックを作ることがあります。
候補削減を強くしすぎると、探索が単調になり、局所的に良いが後半で詰まる状態を選びやすくなりました。
690,636 まで落ちた提出は、かなり大きな失敗でした。
この結果から、次の方針に戻しました。
・prefix は最重要
・ただし prefix だけでなく chain score も見る
・ready commit は強くしすぎない
・候補削減はしすぎない
・高速化は探索の性質を変えない範囲で行う
悪化提出を見て、評価関数のバランスがかなり重要だと分かりました。
全体の流れ
最終的な探索の流れは、次のようになります。
beam = {initial_state};
while (time remains) {
selector.clear();
for (state in beam) {
turns = generate_candidate_turns(state);
for (turn in turns) {
move_forward(turn);
value = evaluate(state);
hash = state.hash;
selector.push(turn, value, hash, parent);
move_backward(turn);
}
}
beam = selector.select_top();
if (found_complete_state) {
update_best_answer();
}
}
実際には、差分更新ビームサーチにより、木構造上で move_forward / move_backward をしながら葉を展開しました。
生成AIの利用について
実装面はかなりAIに頼りました。
C++コードの作成、差分更新ビームサーチ化、細かい高速化、バグ修正などをAIに補助してもらうことで、実装にかかる時間を減らせました。
その分、ビジュアライザを見た考察、評価関数の設計、スコアが悪化したときの原因分析、次に試す方針の検討に時間を使えたのが大きかったです。
最終的にどの方針を採用するかは、手元実験や提出スコアを見ながら判断しました。
結果
最終結果は次の通りです。
35位
performance 2402
score 742,777
最終提出は全ケース完全一致していたので、合計ターン数は
750000 - 742777 = 7223
なので、平均ターン数は
7223 / 150 ≒ 48.15
です。
初手の 736,891 点、平均約87.39ターンから、最終的に平均約48.15ターンまで削れました。
まとめ
AHC064では、非交差制約を満たしながら、できるだけ少ないターンで車両を目標順に並べる必要がありました。
初手では、各車両を目標出発線ごとの待避線へ振り分けてから戻す構成解を作り、736,891点でした。
そこから、全退避してから戻す方針の無駄をビジュアライザで確認し、状態ビームサーチへ移行しました。
最終的には、非交差な1ターン遷移の生成、評価関数の改善、差分更新ビームサーチ、hashによる重複除去、固定長配列化などの高速化を入れて、742,777点、35位を取ることができました。
感想
今回は、AHCでの過去最高順位に加えて、初めて橙パフォーマンスを取ることができました。
かなりうれしかったので、過去最高順位 + 初橙パフォ記念として、初めて自分の解法を記事としてまとめてみました。
最終的に35位という順位を取れたことももちろんうれしいですが、構成解、ビームサーチ、評価関数、高速化を順に積み上げて改善できたことが一番の収穫でした。
また、今回は実装面で生成AIをかなり使いました。
コードを書く部分をAIに助けてもらえたことで、実験結果を見て考察したり、次の改善案を考えたりする時間を多く取れたのが大きかったです。
せっかく良い結果が出たので、単に提出コードを残すだけでなく、どう考えて改善していったかも含めて記録しておこうと思います。