0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴5年10か月のかえでです。
これは、2025年10月19日日曜日午後7時から午後11時までの4時間コンテスト「RECRUIT 日本橋ハーフマラソン 2025秋（AtCoder Heuristic Contest 055）」に参加したときのメモを元にした簡単な参加記と、その後の復習を書いたものです。
1.問題の概要
【メモ】
- 宝箱N=200個固定
- 宝箱 B（ID）
- 宝箱 硬さ H
- 武器 耐久 C
- 武器 攻撃 A Cが1減る
- 素手 Hを1減らす
- 使用武器 攻撃対象B
2.コンテスト参加時の記録
問題文理解も兼ねて、ChatGPTに問題文を投げます。
最初に素手で全ての宝箱を開けるプログラムを提出をします。全てのテストケースが1点なので、150点を得ました。（19時9分）
その後、高効率武器から使うプログラムを書くように指示します。解法価値として（価値/硬さ）を使用したプログラムを提案されます。
プログラムをpahcerで実行し、100テストケースの結果を見ます。最初に書いた素手で全ての宝箱を開けるときは全てのテストケースが1点でしたが、平均スコア、53312が出ました。
オーバーキルをしない方が良いのではないかと考えますが、結果は芳しくありませんでした。元に戻して提出をします。
コンテスト開始から15分が経過したところでした。スコアは7968139が出ました。
プログラムの内容に自分の理解が追いつきません。プログラムの内容を説明させて、今後の方針を考えます。
このときのプログラムは下記のような内容になっていました。
- 解法
- 入力
- N 個の宝箱。硬さ H_i。各箱を開けると同番号の武器 i が手に入り、耐久 C_i 回だけ使える。
- 武器 w で箱 b を殴ると A[w,b] だけ削れる（1 手消費）。素手は常に 1 ダメで無制限。
- 事前評価
- ループの方針
- 使える武器がある間：
- まず「一撃で開けられる」(A[w,b] ≥ hp[b]) 組合せを探し、score_ratio[b] が最大になる箱を優先して開ける（＝新しい武器の解放を重視）。
- 一撃候補がなければ、素手との差分 A[w,b] − 1 が最大になる (w,b) を 1 手だけ撃つ（＝1 手あたりの得最大）。
- どの武器も実質 1 ダメ相当しか出せない/使える武器が無いとき：
- 箱が開いたらその武器が使えるようになり、上記を繰返す。
- 出力は時系列に (W,B)（素手は W = -1）。
- 使える武器がある間：
- ねらい
- 入力
-
いまの方針の強みと限界
強み
限界（改善余地）
問題理解を努めている間に、現在の提出人数は342人。順位は76位まで落ちていました。入力生成方法を見ます。Aの攻撃力は小さな数字が並び、ところどころに大きな値があるということに気づきます。
- 得意な宝箱を攻撃するようにします。
プログラムを修正して提出をすると、順位は少し上がりました。（19時47分）
順位表のトップです。トップでは、1ケース平均57,246.7スコアが出ているようです。
まずはビームサーチにしてみます。しかし、スコアは上がりません。改善する目途も立たなかったのであきらめます。
次に焼きなますことを考えます。
さて、何を焼きなますかという話なのですが、ある宝箱のグループを作り、それを素手で先に全て開けることとし、その後貪欲をします。
その最初に開ける宝箱のグループを焼きなましました。最初に素手で開ける宝箱の数が少なくなることを目標とします。
少しよくなったので提出をします。得点は8191768となり、478人中31位になりました。（20時4分）
改善するために、ログを出力して、結果を見ます。得意な武器を使う方法が思いつきません。
良いアイデアが浮かばないまま、時間が過ぎていきます。得意な武器の重みや、使用する閾値を変えたりといったことを試しますが、ベストを更新することができません。
順位表のトップを見ます。コンテスト開始から1時間40分が経過していました。1位のnikajさんのスコアは、8773373、1ケース平均にすると58489.2です。私のベストの提出での平均は54611.8です。
この差をどうやったら埋めることができるのでしょうか。
ビジュアライザを見ます。
- 素手で攻撃する宝箱が最後まで残っていること
- 攻撃回数が複数回残っている武器が残っていること
が気になりました。
- 宝箱を開くことができなくても、武器を使うことで手数が減ることを評価に追加します。
うーん、うまくいきません。
時刻は午後9時を過ぎました。順位は669人中86位まで下がっています。
- 高速化します。
提出をすると、ほんの少しだけ良くなりました。
ビジュアライザを眺めます。素手で開く宝箱がまだ多く残っています。
近傍の入れ忘れに気づいてので、近傍を追加します。
- 素手と武器1回のswap
良くなりません。
- 時間を10秒にしてスコアが良くなるかを見ます。
ほんの少しよくなる程度でした。やはり、今の解法に足りないものがありそうです。
- たまに2番目に良いものを選択するようにします。
結果はイマイチでした。
- 攻撃力が高い、回数が多い、武器を良い武器と評価します。
- 良い武器を最小手数で壊すために、その宝箱の攻撃力が高い武器がある宝箱をその前に開けると考えます。
そのような再帰的に考えたとき、素手で最初に開ける宝箱が見つかりそうです。とは思うものの、実装方針が思い浮かびません。
午後10時を過ぎました。残り時間は1時間を切りました。
順位表のトップスコアは8826896になっていました。トップの1ケース平均スコアは58,846です。
その後、焼きなましの近傍を追加し、少し良くなりました。
しかし、大きな改善方法が見つからないまま、コンテストが終了しました。
最終提出のスコアは8223523で、スコア更新をすることはできませんでした。
最終結果は852人中201位という結果に終わりました。
3.反省
最初のChatGPTの解法でのスコアが思った以上によかったので、自分の思考が停止してしまったように思います。ルールで使用が許可されている以上、4時間のコンテストで自分が使わないという選択肢はないのですが、もうちょっと良い距離感で使用できるようになりたいものです。
結果としての順位はそこまで悪くないのですが、不完全燃焼なコンテストでした。
入力を見て、得意な武器で攻撃することが重要だということには気がついていました。そこからもうちょっと考察を深めたかったです。
4.復習（貪欲）
さて、復習を開始します。chatGPTは使わない縛りで、自分の理解度にあわせて進めます。
AHCラジオのtomerunさんの解説を参考にします。
【貪欲1】
- 0からスタートして、N個をID順に宝箱を開ける
- 2個目以降はその前に開けた宝箱の武器を使用する
seed0 スコア2820 ターン数54462
【貪欲2】
- 0からスタートして、次の宝箱は持っている武器の攻撃力が一番高くなる宝箱を選ぶ
seed0 スコア37342 ターン数19940
【貪欲3】
- 貪欲2に追加
- スタート位置をN通り試してベストを出力する
seed0 スコア40917 ターン数16365
【貪欲4】
- 貪欲3に追加
- 前の宝箱の武器以外に、残っている武器も使う
seed0 スコア41753 ターン数15529
【貪欲5】
- 貪欲4に追加
- 宝箱に対する攻撃力が10以下の武器は温存
seed0 スコア46897 ターン数10385
【貪欲5-2】
- 貪欲4に追加
- 宝箱に対する攻撃力が25以下の武器は温存
seed0 スコア48333 ターン数8949
【貪欲6】
- 貪欲5に追加
- 次の宝箱を選ぶときは、今ある武器で一番攻撃できるものを選ぶ
あ、バグってました。一番最初に開けた宝箱の武器を追加するのを忘れていました。修正します。
seed0 スコア50077 ターン数7205
あ、判定時に攻撃力に使用回数を掛けるのを忘れていました。
【貪欲6バグ修正】
seed0 スコア50929 ターン数6353
というわけで、貪欲で本番467位相当の得点、7922030になりました。
5.復習（焼きなまし）
次に、先ほどの貪欲6を初期解にして焼きなましをします。ここからは適宜LLMの力を借りることにします。
しかし、貪欲6の初期解を作るのに、すでに700msかかっています。何か無駄なことをしていそうです。
時間を計測したところ、スタート位置をN通り試していて、一回につき3msほど使用しているので、600msほど費やしているようです。
- 初期解を作成する際、解法価値（攻撃力*使用回数/硬さ）を計算して、一番良いものからスタートすることにし、N通り試すことをやめます。
実行時間は21msになりました。提出すると、得点は7677374になりました。これを初期解とすることにします。
宝箱を開ける順番を2点swapで変更し、シミュレーションをします。seed0での試行回数は5971回、改善数は38でした。初期解のターン数7250が5394に改善しているので、かなり良くなっているものの、100テストケースの平均は53742でした。解説放送でのスコア（平均56077）には到底及びません。
また、数万回試行できるということなので、高速化を考えます。
なお、実行時間を10秒にすると、さらに1000程度スコアが良くなることがわかりました。
- 毎回シミュレーションしていたのを、swap前後で、その前後の宝箱との関係のみ、ターン数を調べて差分を取ります。
試行回数9万回くらいに増えましたが、スコアは悪化しました。予測を本番に近づけます。
- Aが10以内のときは使用しない
また、悪化したときも一定の確率でシミュレーションを行うことにします。
- 20分の1の確率で悪化時もシミュレーションを行う（割合は適当）
試行回数は5～6万。seed0での改善は42になり、ベストを更新しました。とはいうものの、解説の数字にはまだ遠いです。シミュレーションと予測時に、攻撃回数を考慮していないことに気づきました。修正します。
また、シミュレーション時に使える武器の情報を全部持っているのがボトルネックになっていそうだったので、武器の保持数を限定します。（ソートするO(N)の削減）
- 武器の保持を上位10個に限定する
これを取り入れると、明らかに良くなりました。100テストケースの思考では平均55489になりました。
seed0の試行回数も17万回、91回ベストを更新できています。
スコア53288 ターン数3994
提出すると、得点は8307768になりました。本番144位相当の得点です。
やっとコンテスト当日のスコアを超えることができました。
予測ではなく、実際のシミュレーションに戻しても良いかもしれません。しかし、やってみると1000くらいターン数が増えたので、予測を入れた方がよさそうです。
時間が足りないので、初期解のスタート位置を1回しか試していなかったのをN通り試すように戻します。
うーん、良くなりませんでした。
6.復習（より良い評価）
AHCラジオのtomerunさんのスライドから引用
なお、上記引用スライドは下記の問題の解説タブのリンクよりご覧いただけます。
というわけで、攻撃の優先方法を変えます。
スライドの評価を入れてみますが、スコアは良くなりませんでした。なぜ…。
この後使えるかどうかで、攻撃力の重みづけを変えてみました。
- この後得意な宝箱がある・・・0.2倍
- この後得意な宝箱が無い・・・2.5倍
提出すると、8337915、本番130位相当の得点になりました。100テストケースの平均は55659です。
先は長い…。
ところで、ビジュアライザを見ると、使われていない武器が残ってしまっています。閾値をつけているからです。また、全部の箱に対して攻撃力が低い武器が使われないようです。
一日がんばってみたものの、スコアを上げるのが難しかったです。一旦ここで終了したいと思います。
