AHC049

omochi_gyuhi
·
公開:2025/6/22

問題文:https://atcoder.jp/contests/ahc049/tasks/ahc049_a

最終順位 43位

4時間フル参加、Gemini2.5Proを使用

業務分担

方針決定:自分

コーディング:Gemini 2.5Pro

アイデア出し:双方

コンテストが始まる前に以下投げておく。応答が安定しそうなので。

これからAHC049が始まります。あなたは最適化問題を解決する競技プログラミングのトッププレイヤーです。通常の応答は必ず日本語で実施してください。最初はpythonで実装し、実行速度の向上が必要になった時点でC++に翻訳し改善を続けます。

ついでに最近制定された生成AIルールも投げておいた。

問題文が公開されたらすぐにページをPDF化してGeminiに投げ、問題文の要約と最も簡単な貪欲法の実装をお願いする。

最も簡単な貪欲法として実装されたのは箱1個だけ持って出入口へ向かう方法。絶対つぶれないのでスコアは確実に取れる。これを提出してスコアを獲得できることを確認し、これを基準に改善することを確認。

出入口からスタートし、箱を拾って出入り口まで戻り下ろすひと巡りの手順をツアーと呼ぶことにした。それぞれのツアーで改善があればそれは最終的なスコアの改善に直結する(ほかのツアーで発生するスコアへの寄与に影響を及ぼさないから)。

まずはこの最も簡単な初期解をもとに焼きなましを頼む。1箱ずつ運ぶツアーから徐々に改善して行く。あるツアーが箱をつぶさず運びきれるかというのは高速に判定できる。

この時点での得点:1,351,022・Seed0のスコア:約8900

重い順に拾うことで小難しいことを省略する。

この時点での得点:1,727,344・Seed0のスコア:約11300

初期解用の貪欲法を改善する(振り返ってみるとここの判断はちょっとまずかったかも?)。適当な箱(遠くて重い箱を重視)を核としてその箱に地理的に近いものをどんどん追加していく。同じところまで何回も行ったりしたくないし、遠い箱同士をつなぐくねくねルートは非効率そうだし。ついでにC++に書き換えてもらう。

この時点の得点:1,754,968・Seed0のスコア:約11700

大きめの近傍として一番下の箱を入れ替えることを思いつく。あとは微調整。

最終得点:1,825,986・Seed0のスコア:約12000

参考:最終提出版をpythonに再翻訳してもらった場合の得点:1,764,424