トヨタ自動車プログラミングコンテスト2023#6(AHC026)参加記

トヨタ自動車プログラミングコンテスト2023#6(AHC026)に参加したので、やったこと/コンテスト中に考えたことを振り返ってみようと思います。前回のトヨタコンでは青パフォを出していたのでまあまあ期待しており、気合は十分。早速見ていきましょう！

重要そうな条件として、

があるため、焼きなまし系は厳しそう。ということで貪欲ベースに決定。

次に取り出す箱(=残っている箱の中で最小のもの)をiとして、iが山の一番上にあれば無条件で取り除いて良さそう。

iが山の途中にあった場合、iより上の塊を別の山に動かさないといけないが、とりあえず(iがある山以外で)ランダムに選んで移動させ、山の一番上になったiを取り除く。

提出してみたところ、1216354点。30分弱しか経過しておらずまだ順位を気にする段階ではないのでこの解法を育てることに集中する。

この解法だと一回悪い移動をするとそれが点数に直接響いてしまうので、時間いっぱい繰り返し、一番よかったものを最後に出力してみる。

また、箱がなくなった山(山とは)を記録し、優先的に移動先にする工夫もしてみる。

提出し、1295764点を得る。少し伸びたが、やはり解法の中身を改良しないと上位には近づけなさそう。この時点で約1時間経過。

具体的にランダム移動先について考えてみると、i+1やi+2がある山に移動させてしまうと次の移動で動かす量が増えて損、ということに気づく。そこで移動先をi+1~i+5がない山の中からランダムに選んでみる。

手元で動かしてみるとseed0で8100→8800くらいに伸びたため、期待を込めて提出。

結果は1343716点で223位/498人、かなり伸びてテンションが上がる。

移動させる塊の中に比較的小さい数(i+3とか)が入っていたらそれを山の上に露出させておけば数回後で移動しなくてもよくなり得だと思い、

とする。勿論移動先はi+1~i+5が含まれない山の中から選ぶ。

ということで提出。

結果は1366399点で160位。まさかここまで伸びるとは。

実は前日に徹夜しており、かなり眠かったため改良案が思いつかず寝落ちを決断。ここで撤退することにした。

結局341位まで落ちてフィニッシュ。

Twitterで周りの反応を見てみると1356657点の貪欲の人が多かったらしく、ランダム移動が功を奏していたらしい。また、1343716→1366399で一気に伸びたのもその人たちを(知らぬうちに)追い越していたかららしい。

一応seed0で9115点のビジュアライザを貼っておきます

上位の人たちは各山をソートしていたらしく、かなり衝撃を受けた。が、よく考えてみたら

ということで、自分の解法からでも到達できそうだったことに気づく。後で自分でも実装してみようと思う。