AHC026参加記
Updated: 2024-07-19
はじめに
through です。この度 トヨタ自動車プログラミングコンテスト2023#6（AHC026）にて、好成績を収める事が出来たので参加記を書きます！
結果 : 1,399,432点 41位/789位
performance は 2329 で黄perf でした！
自分は短期コンが大の苦手で、AHC026 以前での短期コンでの最高perfは水色だったので良い成績を取れて凄い嬉しいです。
問題概要
N(=200) 個の箱があり、初めは 20 個の箱が詰まれた山が M(=10) 個ある。各箱には 1~200 の数が振られているので、以下の操作を行い、出来るだけ体力を温存するように全ての箱を 箱1 から番号順に運び出してね。
- 箱X とそれより上にある箱を、体力 (運ぶ箱の数+1) を消費して他の山に移動する。
- 箱X が山の頂上にある時、体力消費無しで運び出す。
解法概要
各山を頂上から見て昇順になるようにソートされた状態にする貪欲です。 全ての山がソートされている盤面は必ず体力消費0で全ての箱を運び出すことが出来る為、勝利を意味します。
山のソートの仕方は以下の通りで行いました。
- ソートしたい山の頂上から番号が単調減少な部分を取り出して他の山へ退避する。
- 1 を山に箱が無くなるまで繰り返す。
- 他の山に移した箱で山の頂上にあるもののうち、最大の番号の箱から元の山に戻す。
他の山に、単調減少を崩さずに移しておくことで、3の戻すという操作のみでソートが完了する & 複数の単調減少な部分を運ぶ時に手数が節約出来る という利点がある為この方法で行いました。
単調減少な部分が多数生成されてしまい退避可能な山が無くなるケースがありますが、その時は既に退避したもののうちサイズが一番小さいものとマージする処理を入れました。
これだけで本番最終82位 (1,394,313点) が取れます。
これに加えて以下の2つの工夫を入れました。
- ソートの操作中に今取るべき箱が来た時はその時点で取る。
- ソートの過程で退避する山は、山の最小要素が最大の山から順に選ぶ。
1 はソート中に運びたい番号があるなら勿論途中で取った方が、ソートすべき箱が減るので自明に体力が温存出来ます。2 は 1を行う上で、他の山がソートされている場合に他の山も巻き込みながら運び出しを進めることが出来る可能性が増えるので取り入れました。
この2つを実装すると 5000点 程上がり、本番最終41位 (1,399,432点) が取れます。
今回の戦い方で良かった点
貪欲の考察を突き詰めた
短期コンテストは時間との闘いがある為、一度間違った方針で時間を使ってしまうと、違う方針で試す時間が必然的に限られてきます。その為、いかに初めに核心に迫った考察を出来るかが重要です。
言葉で言うのは簡単ですが、実際にはそれが結構難しく、過去の短期コンテストでは問題の核心に迫った貪欲を書くだけで青perf~ が取れてしまう回が過去に何度もありました。例えば AHC015 Halloween candy や AHC021 Pyramid Sorting です。
過去回の詳細はネタバレになるので省きますが、実際にこれらの回では貪欲を書くだけで、それぞれ 80位程度(2000 perf付近), 156位(1860 perf) を取ることが出来ます。( AHC015 は天才すぎて感動した。 )
実際に今回もソート貪欲の解法だと、雑に書いても最低 1,380,000点 (225位付近 1640 perf) 程度を取ることが出来ます。( 各山のソートは基本的に箱を出す・戻すの2回で完了するので、体力消費は悪くても 200(箱の数) * 2(操作回数) * 2(1回の操作コスト) = 800 程度で済む。 )
自分が今回貪欲を考察する上で、最初に沸いた発想が、『今とるべき番号の箱より上の部分を、最小要素が最大の山の上に退避させて、その番号の箱を取る』 という貪欲方針でした。 この方針だと遠い未来に山の移動を擦り付けられるので良さそうと思いましたが、結局後々の体力の負債になっていると感じた為、妥協せずにもっと良い方針が無いかを探りにいきました。いつもはすぐに乱択ベースな解法に頼ってしまうので、貪欲の考察を突き詰めたのは良かった点だなと思います。
実装・改善方針の目途が立つまで手を付けない
今回は考察が定まっても、実装・実装後の改善方針 等の目途が立つまでは手を一切動かしませんでした。自分が残りの時間ですべきことを洗い出すことで、常に手を動かして無駄な時間を無くすことが出来、またバグを生みそうだなと思っていたソート部分もほとんどバグを生まずに実装出来ました。
感想
山登りや焼きなまし、ビームサーチ等の手法を用いずとも上位を取ることが出来、短期ならではの面白さを感じました。X の Timeline の感想戦を見ていると、ビームサーチ解法がとても気になったので時間がある時に実装してみたいと思います。
短期コンで 初の2桁順位 & 黄perf が取れたのでとても満足です！なんと少し諦めかけていた、Heuristic年内入黄が目前になったので、今年最後のAHC027にて入黄を果たしたいと思います！
