トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）参加記録

こんにちは。競技プログラミングをしているssaattooと申します。トヨタ自動車プログラミングコンテスト2024#5（AtCoder Heuristic Contest 033）に参加して暫定39位でした。

反省、または誰かの為になることを期待して参加記録を残します。

問題概要
解法
日記
終わりに

問題概要

https://atcoder.jp/contests/ahc033/tasks/ahc033_a コンテナが流れてくるので指定の位置、指定の順番で搬出してください。

解法

大まかな解法は以下の通りです。

タスク（搬出、ストックに置く）の優先度を決める
優先度が高い順にクレーンにタスクを割り当てる
割り当てられたタスクをもとにクレーンの操作を決定する
クレーンを操作する
2～4を搬出終了まで繰り返す
1～5を時間まで繰り返す

ストックを利用することで、ターン数以外のペナルティ０を達成することができ、ローカルでは平均74手で完成しました。

これで暫定テストで85%程度（39位）の点を得られます。

タスクの優先度

タスクとは、搬入口から搬出口への輸送、搬入口からストックへの移動、ストックから搬出口への移動のいずれかを指します。タスク列とはタスクの列のことで、実行可能なタスクが2つ存在するとき、タスク列の左に存在するタスクが優先して実行されます。

タスク列の生成は、小クレーンが一つでクレーンの移動を無視していいとして考えました。

ストック

ストックとは、搬入口にあるコンテナを搬出口以外に移動させるときの一時的な置き場のことを指します。主にストックは6個としていましたが、6個での達成が困難であるときは多めにストックを確保しました。

タスクのアサイン

タスク列をもとにクレーンにどのようにタスクを割り当てるかを考えます。

まず、各クレーンについてコンテナを持っている場合は現在のタスクをそのまま割り当て、コンテナを持っていないクレーンは一度タスクをリセットし毎ターン割り当て直します。その操作後、タスクが割り当てられていない個数を $x$ 個とすると、タスク列の内完了しておらず実行可能なタスクを左から $x$ 個取り出します。各タスクとクレーンの全組合せ $x!$ 通りを全探索し、クレーンとコンテナのマンハッタン距離の総和が最小のものをタスクの割り当てとして採用します。

クレーンの操作

割り当てられているタスクのコンテナ番号が小さい順にクレーン操作を決定していきます。

クレーンの位置と目的の位置が同じときはPまたはQのどちらかです。そうでない場合、前ターン操作後のコンテナの位置と先に決定したクレーンの次ターンの位置をもとに最短経路となる手をBFSをせずに計算して選びます。

日記

メモなので汚いです。

目標

2330パフォ以上で橙になる。
考察を頑張る。特定のケースから考えてみる。
小さなところから根拠をもとに大きくしていく。

コンテスト１日目

問題読んだ。マルチエージェント。実装が膨大になりそう。きれいにメソッドを作りたい。
全てのペナルティ０を達成可能そう。上位は僅差になりそう。
- 全ケースペナ０は達成容易だった。
最初の実装は4列目までコンテナを出し終えたら大クレーン以外を爆破するか。手動seed0が286ターンだった
- 平均290ターンのを提出。37で12位。
- 爆破するんじゃなくて、右端で待っているのが賢いか。
ターンを縮めるには、小クレーンを残して道整理役を作る？
理論値を見積もりたい。最終的に100ターンくらいで完成するんだろうか。
トヨタ決勝みたいに、id%Nが小さいのを左側に、大きいのを右側に配置するのがいいのかな。
探索方法がわからない。

コンテスト2日目

290手が14.2まで下がっている。1位は82手程度ってこと？
- 13.1まで下がった。76手程度。
テスターを参考に作る
80ターンくらいならビーム撃てるかも。
- 目的地への距離の総和を評価値。まだ出ていないのはコンテナに邪魔されているとする。空きコスト１コンテナコスト５くらいにする。
- 行０で搬出できていない場合、コンテナ0..=4の重みは、10,3,1,-1,-2くらいにする
置き場は２３列目に６－８個のみにする？
- ストック６でほぼすべてのケースで成功するっぽい。８なら100%
- 30-40個くらいの運ぶタスクに分解される。N個に分解される。このタスク全てを完了させるスケジューリング問題？
- １つのクレーンが8個のタスクをして平均10手なら80手くらいで完成する。
- タスクの割り当ては最初はとりあえず順番でいい
- タスクが決まったとき、デッドロックは発生するか？０，１列目で発生しそう。発生したら前のターンに戻って片方を停止をするようにすれば大丈夫そうか

コンテスト3日目

1位68手
手動で6ストックをすると8６手が達成できた。大クレーンの機能は使っていない。これを探索の段階まで持っていけたら70手切りもできそう。
ストックの位置は個数はもっといいものがあるかもしれないから汎用的な感じで実装したい。
タスクの割り当てが決まったときの各クレーンの動作を計算する必要がある。
これか？
- 各タスクをaからbへの移動（移動後は爆破）とすればこれに落とし込める？
- 順番にルートを決める。それまでの決定に衝突しないように適宜停止する。これはbfsでいける。タスクが割り振られていないなら、(i, 0)をランダムに選ぶ。目的地を一致しているものを最初に動かす。
- これだと大クレーンの特性も生かせる。
何とか実装した。
- 2、3割で失敗する。
- 0が完了するまで１を出口に向かわせていない
- 平均150手くらい。２７.0で20位。たぶん上振れ。

コンテスト4日目

改善案
- ０が完了するまえに1を動かし始める
  - これはどうすれば実装できる？
  - タスクの割り当てという考えをやめる
    - 各コンテナに、持たれている、ターゲットになっている、なんもなしの３つの状態を付与する
  - 割り当ては置いといて、持っているクレーンの動作は、一つ前のコンテナが持たれていて自分より距離が短いならそこに向かう、そうじゃないならストックへ向かう
  - 割り当ては、まず搬出できるものを選ぶ、その後、1つ前を移動しているもので距離が遠いものを選ぶの繰り返し
  - 一個前のものが既に誰かに運ばれている場合のみに限定した方が楽か。一個前の出口までの距離<それに最も近いクレーンの距離+出口までの距離のときのみ許可
- タスクのアサインを近いものorマッチングさせる
- 操作長の最大値を最小化or総和を最小化するようなactionを採用
- 通れる場所を制限
- ストック個数を変えてみる
- ストックを選択するとき、できるだけ出口に近い行を選択する
- 逐次改善にしたい
- タスクの割り当てがないときも、次に来る位置に向かって移動しておく
- タスク作成関数の見直し
- コンテナを持っていないクレーンは毎ターンタスクをアサインしなおす
- ストック操作より搬出操作を優先
平均10５まで下がった。けどあんまり伸びず32.9で21位。
- 時間10倍にすれば96まで減る
- 100.8まで伸びた。
- ９６．９まで伸びた。
  - 35.5で19位
  - 時間10倍で90手
ビーム化は簡単そう
- うまくいかない。深さをターン数をではなく進捗でしてみるか
- 進捗でやっても多様性が確保できずに完成しない
搬出が偏っているときのスコアが悪い
明日は01を同時に動かすのを作りたい

コンテスト5日目

（タスクの概念は無しにしたいけど）タスクの長さとスコアに相関はあるか
追い抜きが発生してしまうこともあるけどとりあえず動くものができた。
- 0,1,2を同時に運んでいて、0,1を搬出、2をストックに置こうとしているときに、0を搬出すると1,2の距離が逆になってしまうことがある。
  - アサインかストックタスクの更新に問題がある？
- 実装がめちゃくちゃになったけど直した。
部分破壊で焼きなませる？
８５まで下がった
- 10倍で８２まで下がる
- ３８．９で20位
持ってないクレーンはストック上を動いた方がいいか？
今の方法だと限界が近そうなのでビームか焼きなましにしたい

コンテスト6日目

追い抜かないようにするの結構簡単だから持ってないときのアサインも早めにする？
明らかに悪いとわかったら早期breakして高速化
- 2倍くらい早くなって82まで伸びた
  - 10倍で80
完了分を[0,0,0,0,0]から[5,5,5,5,5]までのdp,ビーム？

コンテスト7日目

他のクレーンに影響を与えるのを1手目だけにしたら微高速化で80
- 10倍で78
スコアが悪い奴はcheck_stockが半分くらい使っている？
calc_actionはメモ化したら高速化しそう
ラスト5個以下になったら必ず割り当てるようにしたら79
- 10倍７７
初手の動きはどんなのがいいだろうか
均等に残るようにしたい
残り時間が僅かになったら今までのbesttaskを繰り返す
- ７８

コンテスト8日目

besttaskは半分で分割する？
1000ケース中3ケースが貪欲しか成功していない。これにより平均が0.6手上昇している。
クレーンpos=targetのものがあれば、操作させてからアサイン、アクション計算した方がいい？左端のを持った時点で搬出させたらバグるかもしれないけど、1手先に近づくことができる

コンテスト9日目

↑めっちゃバグらせている。
- やりたいこと
  - アサイン前に、置く、取ることが確定している（cranepos=target）ものは先に操作する
  - ストックタスクの更新
  - 搬入搬出できるならする
  - まだ操作していないもののアサイン
  - 動き計算
上のはバグったままだけど、apply時にそこにクレーンがあっても搬入するようにしたら伸びて76.5
- 10倍75
持ったときにtargetpos = !0にしてはいけない
バグらせまくりなのでとりあえずdpを先に試す
- ｄｐ（ビーム）したけど100手を下回れず