https://kaede2020.hatenablog.com/entry/2025/09/17/072423

0.はじめに

はじめまして、もしくはお久しぶりです。競技プログラミング歴5年半のかえでです。

これは、2025年9月13日土曜日午後7時から午後11時までの4時間コンテスト「第12回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 053）」に参加したときのメモを元にした簡単な参加記と、その後の復習を書いたものです。

1.問題の概要

atcoder.jp

今回の問題はとてもシンプルでした。

あなたは N 枚のカードに 1〜U まで任意の整数 A_i を書きます（この時点では目標値B はまだわかりません）。
その後、乱数生成器が M 個の目標値 B₁, …, B_M を提示します。
- 各 B_j は区間 [L, U] の一様乱数で生成され、昇順に並べられています。
あなたはカードを好きなだけ捨てつつ、残りを M 個の山に分けます（空山OK）。
各山 j の合計を S_j とします。
評価値： E = ∑_j=1^M |S_j − B_j|を最小化します（小さいほど高得点）

2.コンテスト参加時の考察メモと提出

今回やると決めたこと
- 30分タイマーをかけ、30分ごとに立ち上がって、一旦手を止め、頭の中を整理する時間を強制的に作ることにしました。

さて、問題文を読み、「2べきで適当に埋めれば良いのでは」と思ったところがスタート地点でした。

まずはACするコードを出します。

【19:12】定数（U）で1個ずつ埋める

【19:19】1山に10枚くらいずつ割り当てると考え、Uを1,2,4,8,...512で割ったものをM枚ずつ用意して貪欲に割り当てる。

順位表のトップを見ると、nikajさんが、28分で95,962,662,322を出していました。テストケース数の150で割ると平均639,751,082です。

自分はといえば、seed0のビジュアライザを見ますが、青と赤。何だこれ、という状態。

近傍2-optの焼きなましをします。枚数10枚ずつなので、それも変更してみました。捨て札も入れてみました。

うまくいきません。

ブレイクタイム

30分経過し、ブレイクタイムが来たので立ち上がります。特にやりたいこともないのですが、台所に行って家事をします。5分も経たずに戻ります。

簡単な例で問題理解のためのサンプルを作ってもらうことにしました。
- N=3,M=2,L=10,R=100
- A1=50,A2=30,A3=80と書き込む
- B1=75,B2=110だった
- 3枚をどう分けますか

といった感じです。やっと問題の意味がわかりました。

とはいうものの、方針は特に変わりません。おもりの割り当てをイメージして、2のべき乗の値をAに割り振る。Bの分配は焼きなましで行いたいと思います。

ビジュアライザを見ると、Aの数が小さくて、全然足りていないようでした。

順位表のトップを見ます。

トップのスコアを150で割ると、1ケース平均801,681,100、総誤差Eは9253らしい。

え？こんなに誤差が小さくなるの？

誤差0のときのスコアは1,000,000,000 です。

ブレイクタイム

何にも進んでいないのに立ち上がるのはどうかと思いながらも、立ち上がると、今やっていることを客観視できるような気がして悪くないと思います。でもちょっと焦り気味。

もっといろいろな数を作ればよいのかな。

Nは500個なので、U×1/1、U×1/2、U×1/3、U×2/3、U×1/4、U×2/4、U×3/4・・・と500個作ることにします。
貪欲に大きい方からAを割り当ててM個に分けます。
1.9秒焼きなましで、捨てる、１対Ｙ個で入れ替える等の近傍を試します。

うまくいきません。

発想を変えよう。

Aは、BがLからUの間で生成されるなら、LからUの間からランダムで１個ずつ50個生成し、残りは小さい数にする。

上がった！

100テストケースの平均が425,912,989になったので、提出をします。

ビジュアライザのブルーとレッドが少し薄くなりました。

そうか、誤差が減ると色が薄くなっていくんだな…。

この時間になってやっとわかったことでした。

時刻は21時。2時間が経過していました。

順位とパフォーマンスは時間経過とともに、著しく下がり続けていました。

Aの生成される数を増やしてみます。

捨てているカードが多そうに見えます。

小さな値のカードを増やしました。

ほんの少し改善しました。順位は下がり続けています。

ブレイクタイム

新しい方法を考えますが、なかなか思いつきません。Bを予測できないのかなあと考えます。

L,MからBのサンプルを作って、Aを決定し、期待値の高いものを出す。

Aが足りません。

１割くらい捨てる前提で大きめの数を生成することにしました。

少し良くなりましたが、さらに順位は下がっています。

出力を見ると、M個の山に１個ずつしか使っていないことに気がつきます。

だったら、LからUの間でランダムにN個作って、一番誤差が少なくなるものを割り当てるのはどうだろうか。

と考えました。改善しません。

その後もアイデアをいくつかLLMに投げ実装させますが、良い解は得られませんでした。

Nは500個なので、Aは8個を足すと和がLからUの間になるような500個の値を作ります。8個はBを1/2, 1/4, 1/8, 1/16, 1/32, 1/3, 1/9, 1/27となるような割合に分けたものとします。Bより先にAを決めるので、BはLからUの間で等間隔にM個だと仮定してAを作成してください。初期はAを降順に貪欲に詰め込み、その後は 1.9秒焼きなましで、捨てる、1対Ｙ個で入れ替える等の近傍を試してください。
各M個の山にはBを超えないように、A１枚ずつ大きい方から配っていきます。 BもAも大きい順に配りますその後は焼きなましです。

そして、コンテストが終了しました。

3.結果

結果は1069人中647位、パフォーマンス1110で、Ratingは1969になりました。時間減衰の分、前回より6下がりました。

4.延長戦1日目（当日）

さて、気を取り直して復習（延長戦）をします。断片的なキーワードを目にしているので、詳細は見ずに行います。まず見たのがこれ。

AのM個をLにし、全ての山に1個ずつ配る

確かにLを引くことは無条件でできそうです。Lを0にすると、だいぶすっきりしそうです。

グラフにしてみました。一目瞭然です。

これをしないといけなかったなー。反省。

さて、自分の解法に取り入れてみます。

Aの最初のM個はLにして、1個ずつM個の山に配り、固定してください。残りは(U-L)の値を上限として、1/2, 1/3, 1/4, 1/8...みたいな値を生成して、埋めてください。焼きなましでスコアを伸ばします。

結果です。薄緑色のビジュアライザを初めて見ました。誤差は0です。

しかし、スコアは良くありません。Aの数値が小さすぎて足りてない？

Aの内訳で、個数を決めていなかったので、LをM個、その後は1/2, 1/3, 1/4, 1/8...をM個ずつ作って焼きなましをします。

スコアが悪化しました。

Aの中身を、LをM個、その後は1/2, 1/3, 1/4, 1/8...をM/2個ずつ作ります。

やはりAの値が足りない模様。

Aの内訳を、最初M個をLに固定をした後、Lから（L+(U-L))*0.2 の間からランダムに取る。

うーん、イマイチ。

というわけで、自分の解法が土台がLだったら、良いスコアが出ていたのかを、コンテスト後に1時間ほど試してみましたが、それだけでは良いスコアに到達できないということがわかりました。

うーん、難しい。就寝します。

5.延長戦2日目

翌日です。LLMを禁止して、自分で実装をします。

Aのカードの内、M枚はL、残りは(U-L)を適当な数で割った値（使用頻度を見て、今回は18を採用）で埋める。
全ての山に値がLのカードを1枚ずつ配る。
後は貪欲にBjを超えない範囲でカードを詰め込む
100テストケースの平均は、361,069,335
提出すると、53945298514になりました（本番799位相当）
ちなみに、(U-L)/18=222,222,222,222、seed0での1山の誤差平均は、97,964,578,118です。

今は均等に割ったカードを作りましたが、複数の値を作ることにします。

この値の作り方がこの問題のポイントだったようなのですが、詳細を見ないようにしていたので、正解を知らない状態で試しています。

まずは、

U-L=4000000000000

なので、1から4000000000000を18段階に指数的に分けることにします。

18段階なのは、(500-450)/(M/2)を計算して出しました。M/2は適当です。

Value 0: 1.0
Value 1: 5.5
Value 2: 30.4
Value 3: 167.5
Value 4: 923.0
Value 5: 5087.3
Value 6: 28040.5
Value 7: 154555.2
Value 8: 851885.4
Value 9: 4695467.3
Value 10: 25880726.6
Value 11: 142650767.3
Value 12: 786270096.0
Value 13: 4333805387.5
Value 14: 23887299328.9
Value 15: 131663288543.6
Value 16: 725708725436.2
Value 17: 4000000000000.0

4000000000000.0は使われない、それはそう。

MAXの値を下げてみます。

MAXに0.8を掛けた値を、41段階に分割してみました。（分割数は適当。いろいろと試しながらやっています。）誤差0が17個できましたが、スコアは良くありません。難しいなあ。

6.延長戦3日目

昨日の方法がイマイチだったので、もう一度BからLを引いたところから始めることにします。

450÷50は9なので、真ん中が9個になる、だから多いもので18個、小さいもので0個使用するような同じ線分を使用することにします。

Bの(最大値-L)を18で割りたいですが、Bの最大値は未知なので、Uとします。

(U-L)/18

1本の長さは、seed0の場合、222,222,222,222、貪欲に、超えないように使用すると、seed0のスコアは365,498,046になります。

6個残っていたので、オーバーした方が誤差が減るものを上位6個に足します。

4個しか使えませんでしたが、スコアはほんの少し良くなり、368804516になりました。

誤差のグラフです。seed0の1山あたりの誤差平均は、84,127,826,453でした。

適当な赤線を引きました。最初に1枚足す値を、Lではなく、この赤線に沿った値にすると良さそうに思います。

やってみました。

そして、残りを等分したもので埋めます。（長さは使い残しがないように、適当に調整して66666666666を使用しました。自分の想定が500000000000を18等分したものだったのですが、1200000000000を18等分したものを使用しています。）

seed0のスコアは 401,535,115 になりました。

提出すると、得点は58996530800になりました。（本番727位相当）

450個をランダムで生成し、大きい方から埋めていくようにします。

1以上500000000からランダムで450個生成します。

seed0のスコアは473056741、100テストケースの平均は462774008となり、やっとコンテスト時のスコアを超えました。

1個くらいずつしか使っていないようなので、等差数列にします。

seed0のスコアは478404758になり、100テストケースの平均は473697962になりました。提出すると、70,998,375,434になり、本番467位相当の得点が出ました。

等比数列にします。初項1、450項が500000000000の等比数列を作ります。

思っているものと別のものができあがりました。

AのSUMは49,982,086,490,691,900、BのSUMは50,003,564,895,572,400なので足りていません。

AのSUMはBのSUM以上である

これはkojimaさんのXのポストで見ました。

うーん、手詰まり感が出てきたので、そろそろ他の人の解法を見ようかと思います。

LLMに450枚の生成をアイデアをもらいます。

残りの450枚の作り方を種類を14種、2進数の階段状に作ります。Rや種類数は結果を見ながら変えています。

const long long R = 1200000000000LL; // = 1.2e12
s ≈ R / (2^14 - 1)

1ステップsは16383です。

seed0のスコアは536874482になりました。
提出すると、76,291,979,592となり、本番355位相当の得点となりました。

スコアは良くなりましたが、使われていないカードだらけです。

とりあえず一回焼きなましをしてみます。近傍は捨てる、拾う、1対多のswapです。

少し良くなりました。

提出すると、78229576873になり、本番308位相当になりました。

なお。LLMで450枚の生成の調整をお願いしたら、82,843,523,250点、本番216位相当になりました。

ちょっと他の人の解法を見に行ってきます。

7.他の人の解法を見に行く

翌日です。いくつかの解法ブログを見てきました。

下記は優勝者のyosupoさんの解法記事です。

yosupo.hatenablog.com

すごすぎました。

同様のことを自分が試すのは難しいので、2種類のカードの分布を作って貪欲に組み合わせ、焼きなましでカードを変えることにします。

枚数を2枚から試すことにしました。大きい数の250枚と小さい数の250枚を組み合わせます。平均は521,072,229でした。

3枚で、大きい数、中くらいの数、小さい数を作ります。平均は554,957,678になりましたが、2秒を超過しています。

4枚で大、中、小、微小とします。実行時間が17秒近くかかり、678,187,374といった数値が出るテストケースもありましたが、412,462,142といったスコアの下がったものも出てきました。実行時間が超過しているので、焼きなまし時間がないからというのもありそうです。全探索なので、50×125の4乗、10の9乗を超えています。

yosupoさんは枚数を2分割にして、その和を目標に近づけるようにすることで、短時間で少しずつ精度を上げる工夫をして、8枚を使用していました。（ごめんなさい。自分ではきちんと説明できないので、yosupoさんのブログを読んでください。）

うーん、すごい。

というわけで、明日のAHCラジオを待ちたいと思います。