0.はじめに
はじめまして、もしくはお久しぶりです。競プロ歴4年8か月のかえでです。
今回は、 第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）に参加しました。2024年9月15日(日)19:00から23:00までの4時間、短期コンテストです。4時間というのは長く見えてあっという間に終わってしまいます。
長期に比べて短期は苦手意識が強いのですが、今日は4時間を少しでも上手に使って順位を上げることができればと思います。きちんと書けないかもしれませんがメモをしながら考察を進めていきたいと思います。これを読んだ方にコンテストの雰囲気をわかってもらえれば、うれしく思います。
1.問題文
- ベースとなる飲料水にシロップと炭酸を加えて炭酸飲料を作る。
- 飲料は (甘さ x, 炭酸 y) で表記されます。
- 最初に持っている飲料は (0, 0) だけで、以下の操作を繰り返して目的の炭酸飲料を作る
- 既に持っている飲料 (x, y) を選ぶ。
- 新しい甘さと炭酸 (x', y') を選ぶ。ただし、x' ≥ x かつ y' ≥ y。
- (x, y) を二つに分け、一方にシロップと炭酸を追加して (x', y') を作る。
- 操作のコストは (x' - x) + (y' - y)。
- 与えられた N 種類の炭酸飲料 (A_i, B_i) を全て作り、コストの総和を最小化する。
2.ビジュアライザ
「例を見る」のリンクをクリックしてビジュアライザを見ます。スタートは左下(0,0)から。全ての点を赤に変え終わると終了。遷移が青線。
例を見るのスコア予測 149,987,424
順位表を見るととにかく提出が早い。焦る気持ちを抑えます。
3.考察（アイデア出し）
何かよくわからない。青い線を短くする方法を考えれば良さそう。スタート位置からの距離が近い点を選ぶ。
貪欲法。今ある飲料から最小コストのものを探す。甘さと炭酸の値が小さい飲料からソートする。
スコアの予測 3,430,697,513
4.100テストケースの結果
100テストケースの結果。
5.考察
グリッドみたいにやりたいなと思います。ビジュアライザを見るとバグってそうな何かができました。
格子点9か所を最初に追加してみます。スコアが悪化しました。
格子点9個の作り方を修正してみます。
貪欲より悪くなりました。何か違う。
6.最初の提出
最初の貪欲を提出します。
すでに1時間20分が過ぎました。提出は600人を超えていて、順位は170位でした。
7.やることを考える
適当な答えをいくつか出力してみて、問題が少しわかってきました。ビジュアライザで言うならば、右上の方向にしか進めないということ。
- x′ ≥x かつ y′ ≥y を満たす整数 x′ ,y′ を選ぶ
この制約がものすごく効いている感じです。ぱっと見、本当に貪欲が強い気がします。ちょっと上に3,605,538,738というスコアが並んでいる場所があるので、これも貪欲な気がします。何を変えれば良いのかな。
「例を見る」のリンクからビジュアライザを見ます。
そうか、無い頂点を足して中間地点を作っても良いのだったと思い出します。
- ランダムな1点を加えて貪欲を行い、スコアが良くなれば採用する山登りを行います。
ループは1500回くらいしか回っていませんが、スコアは少し良くなっていそうです。うーん、なんか違いそう。短期は5分間隔で提出できるので、とりあえず提出します。その一方で100テストケースも試します。（追記：青い点が追加点なのでほぼ追加された点がありません）
得点が少し上がり、3448215125になりました。
順位は249位でした。
seed0のビジュアライザです。
得点は少し上がったものの、順位は312位に下がりました。
順位表を見ると、5,388,249,433というスコアが複数並んでいました。
これ、何だろう？
バグっていそうなスコア計算を修正しました。点が追加される数が多くなりました。seed0では114点追加されました。スコアも少し良くなりました。
提出をします。その間に100テストケースも試します。1ケースごとに2秒かかると100テストケースを試すのもちょっと時間がかかるなあと思います。その間にブログを書き進めます。うーん、トップは平均36,592,730というスコアで自分の約1.5倍。随分差があります。
提出した結果は363位でした。相対的に順位が下がっていきます。
制限時間を10秒にしてみたらスコアが上がりました。
高速化したいと思います。…バグらせ続けたので別の方法を考えます。
出来上がりはグラフの木なので、部分木をつなぎ変えることを試します。
うまくいかなかったのでビジュアライザを見ます。
そうか。ランダムに追加する点を、例えば下の図のように2転換の距離が長い箇所を選び、その線分上の１点を選ぶようにします。
悪くない発想だと思ったのですが、思ったようにスコアが上がりません。
そしてそのままコンテストが終了しました。
8.最終結果
985人中508位でした。
レーティングは変わらず、1682でした。
9.終わりに
やはり、あっという間に4時間が終了してしまいました。
いろいろと気づき始めたのが遅すぎました。ビジュアライザをもっと見続けなければいけなかったなあと思います。
今なら追加したい点が思い浮かびます。例えば下の緑の点。これがあれば、もっと短くすることができそうです。
どうやればいいのかは試行錯誤中です。復習をしたいと思います。
2024年9月18日の午後8時からはAHCラジオがあります。ゲストにkozimaさんが来てくださります。皆さんもぜひご覧ください。
