トヨタ自動車プログラミングコンテスト2023#6(AtCoder Heuristic Contest 026)に参加した記録です。
方針1:貪欲法
4時間の短期間コンテストなので、まずは正の得点を得られる簡単な貪欲ができないかを優先した。
とりあえずビジュアライザを動かしてみて、どういう貪欲法がいいかを考える。
ターゲットの箱より上のすべての箱を、最も使わなそうな山を選んで、そこに積んでいく貪欲法をした。
「最も使わなそうな山」は、ターゲットの箱となるものが時間的に最も遠い山を選んだ。
提出コード:https://atcoder.jp/contests/ahc026/submissions/47302082
得点:1,356,657
この得点の人が多かったので、似たような解法をやってる人多そう。
方針2:ソートする?
箱を動かす時、なるべく上から昇順になるようにしたほうが、同じ体力で効率よく動かせるのでは?
結果的に言えば、重さ+1の体力を消費するのでそんなことなかった。
提出コード:https://atcoder.jp/contests/ahc026/submissions/47305951
得点:1,324,254
得点下がっちゃった。
方針3:ビームサーチ
多様性が確保できそうなのでビームサーチいけるかなと思って実装。永遠にバグらせて終了。
最終結果
方針1のコードが最終提出になった。
得点:1,356,657
順位:426位
強い人の方針
同じ色を集めてワーッてやって 70 位くらいでした #AHC026 pic.twitter.com/IHzgovj3sq
— iwashi31 (@iwashi31) 2023年11月5日
「片方に集める」「寄せる」みたいなのはAHCの典型なので最初そうしようかなと思ったのだけど、後半すっかり忘れていた。
#AHC026 1 位でした
— 和解 (@rsat__m) 2023年11月5日
各列について「全部の箱を別の列に出す」「sorted な状態で元の列に帰す」を行う方針を基本として、帰るときに出した先の箱もいい感じにくっつけて連れて帰ったり、既に sorted な列に出した分で帰ってこなくてもいいものを考慮したりするとじわじわスコアが改善する pic.twitter.com/TEvBTH0UO3
山が10個あるからうまくソート状態を作ればいいのか?(ハノイの塔のイメージ?)
感想
- 最初の貪欲の方針は悪くなかったと思う。
- ビームサーチバグらせたのは残念。実装方法のテンプレートをNotionにまとめておこう。
- でもビームサーチあんまりよいスコアでないらしい
- AHC楽しいので毎週開催してほしい。
- レートが単調増加は嬉しい。