- 0.はじめに
- 1.問題文を読んだ印象
- 2.9個の山のうち、一番最後に取る山に移動させる
- 3.ビジュアライザを見る
- 4.別の山に移動した場合9か所全てを貪欲プレイアウトで試す
- 5.考察
- 6.終わりに
- 7.最終結果（2023年11月18日更新）
- 8.復習（終わっていない）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴約4年のかえでです。
今回は、トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）に参加しました。開催期間は2023年11月5日(日)15:00から19:00までの4時間の短期コンテストでした。
短期コンテストですので、簡単なメモ書きになります。それでも今回の問題がどのような問題なのかを知ってもらったり、簡単な解法を伝えることで興味を持ってもらえたらいいなと思い、公開することにしました。AtCoderのAHCの解説には誰でも投稿することができるので、ぜひ他の方も自分の解法を投稿してもらえればと思っています。それでは、始めましょう。
1.問題文を読んだ印象
詳細は省略しますが、1番から200個の箱を順番に取り出していきます。上に他の箱が乗っていると取り出せないので、邪魔な箱を別の山に移動する必要があります。うまく箱を移動させながら、番号順に箱を取り出していく問題でした。
箱の重みはないようなので、単純に積む数が少ない方が良さそうです。まずは入力を受け取り、箱の番号順に上に乗っている箱をランダムで別の場所に移動します。
書いて提出します。時刻は1時間ほど経過しました。残りは3時間です。
2.9個の山のうち、一番最後に取る山に移動させる
ランダムで別の場所に移動していましたが、貪欲に変えることができないかを考えます。いちばん良さそうなのは、10個の山があるので、この先取りたい箱が10番目になる山（最後に移動させることになる山）に移動させることです。（後日追記：言い替えると「MINが最大の山に移動させること」）
書いて提出します。時刻は16:31。残り2時間半です。
思ったよりも順位が上がって驚きました。
貪欲解なので、同じ得点の人が大勢並んでいました。
3.ビジュアライザを見る
seed0のビジュアライザを見ていると、途中でどう見ても今はよくても後が困るんじゃない？という状況になっていました。一つの山が極端に高くなっています。
うーん。
案としては、小さい山を2つ重ねて空いた場所を作り、そこに置くというのもありそうです。ただ、もう一つ気になっていることがありました。操作回数が5000回使えるのに、今は340回しか使っていないということです。
もっと細かく移動させたい。そう思うものの、具体的な方法が浮かびません。
考えているうちに、あ、そうか。どの列に置くと一番良いか、その後を全てシミュレーションして、一番良かったものに決定すればよいのかもしれないと思います。（後日追記：「その後を終わりまでシミュレーションすること」を「プレイアウト」と呼ぶとのこと。私は「貪欲プレイアウト」を行おうと思ったのでした。）
4.別の山に移動した場合9か所全てを貪欲プレイアウトで試す
というわけで、細かく移動させることはできないものの、どの山に移動させるかを全て試して一番スコアの良かったものを選ぶことにします。
書けたので提出します。時刻は17:36。残り1時間半です。
パフォーマンスはいつもより良いです。このまま青パフォで終了できるよう改善を重ねたいです。
5.考察
順位表を見ると、他の参加者が制限時間いっぱい回している気配を感じます。ジャッジ中の砂時計マークがついた状態が続いている様子からそのように思いました。時間いっぱい回すとしたら何だろう？
ああ、そうか。貪欲プレイアウトで出した解を初期解として、山登りをしてみたいと思います。
また、ランダムで山を2つに分けるという操作を入れてみたい気がします。
と、思いましたが、残り時間は1時間ちょっと。実装できる気がしません。
6.終わりに
結局いくつか試したものの、貪欲プレイアウトで出した以上の良いスコアは出ませんでした。4時間、あっという間に終わってしまいました。だいぶ順位も下がってしまって残念です。コンテストが終わったら、皆さんの解法を見て、復習をしたいと思います。
seed0はこんな感じでした。スコアは9207です。
7.最終結果（2023年11月18日更新）
最終結果は789人中257位でした。システムテストは行われないのですが、まだジャッジ中だった提出があったようで、19時の順位より少しだけ下がりました。パフォーマンスは1573で、青パフォには届かなかったものの、Ratingは25上がり、1481になりました。
8.復習（終わっていない）
11月8日にAHCラジオが放送されました。
私の貪欲プレイアウト解法は、ちょっとしたことで、ぐんと順位がよくなることがわかりました。1番の箱から順番に取り出すことにしていましたが、それを全ての箱を貪欲プレイアウトで試して一番スコアの良いものを選ぶように変更すると77位相当のスコアが出るとのこと。
そんな簡単なことで良いのかと放送時は思いましたがコードを書きなおそうとすると、修正箇所が意外と多くありました。復習が終わってから参加めもの更新をしようかと思いましたが、まだ時間がかかりそうなので、先に参加メモを更新してしまうことにしました。
また、今回は自分とは異なる、ソート解法を使った人がかなり高得点を出すことができるようでした。そちらも試したいなあと思いつつ、何となくそこまでたどり着かなそうな感じです。
復習は時間を空けるとダメですね。
次のAHCは12月の前半にあるHACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）です。次こそはさらなる上位を目指してがんばります！
