# AHC025 2023/10/14 12:00 ～ 10/22 19:00

https://atcoder.jp/contests/ahc025/

## 1日目
### 所感
未知の重さのアイテムを指定した数の集合に振り分け、できるだけ合計の重さを均等にする。
アイテム数Nが30～100個に対し、秤にかけられる回数が2N～32Nなので、相当類推が必要。
基本的には重いやつを見つけて、軽い集合に渡す操作をするのだと思うが、うーん。

よくあるクイズ問題なので、まずはそこらへんの知識を調べるか。
あとは単純に重さの分布の調査。指数分布らしいので、極端なやつが含まれるはず。

重さ順に並べる方法はあった。
https://note.com/epr/n/n87c9f357521f
普通に全パターンを潰すだけだ。
5!と2^7とを比較しているので。

とはいえ、軽いやつは調整に使えばいいだけで、基本は飛び抜けて重いやつの特定が大事そう。
期待値を追い求めて比較する先を決定する必要がありそう。なので重さの類推は大事。

MM127のこれに近そうだけど、これは複数同時比較ができるので違いそう。
https://inaniwa.hatenablog.com/entry/2021/06/17/171416
うーん、とはいえかなり性質は近そう。ちょっと追う。
iwashiさんの記事丁寧でたすかるー。
https://iwashi31.hatenablog.com/entry/2021/06/17/175032
同時出走台数K=2の時は流石にマージソートのよう。
これは今回も同じで重いアイテムと軽いアイテム(真ん中は適当でいい)をちゃんと決める時便利そう。
マージソートの列を全部やるのではなく、部分的にやるイメージ。★

内部的に重さを仮決めして、スコアの期待値を求めるようなモテカルロ木的な方向は面白そう。

秤のメモリとして、最小なものは最も小さいアイテムの重さとなる？
そうなら最小のアイテムを載せた時と載せない時で結果が変わる組み合わせが最もよい。
→大体近しい重さの集合と、軽いアイテムから順に数点確保し、帳尻をあわせるようなのがよいか。★

うーん、スコアが一致しない。
ローカルツール見る。ここらへんあやしくない？
間違っていたが分散の定義を知らない私がバカなやつだった。
ローカルツールの計算式が賢そうなので、それを流用する。
よし一致した。

### 実装
愚直解を出す。
初期解を作って、ランダムで集合を選び、重い方から軽い方に大小関係を変化させない範囲で渡せるアイテムを探す。
クエリ制限いっぱいまでやる。
seed=0、きれいにいく。
seed=4、大きいアイテムが動かせなくなる。

今は1点swapしか無いので、これは当然。1:2swapを考えれば解決はする。
ただ、ちょっとここで足を止めて考える。

### 考察

重さの分布について
seed=3がN=80で多い。
数が多い分には、色々と楽そう。

重さの平均は70,000～120,000辺りだけどあんま当てにならないな。
上位の外れ値もそうだけど、意外と上位除いてもブレる。
dfsで理論値求めといてもいいなぁ。
分布見る限り、やはりでかいやつから順にならして、あとで細かいので微調整って感じに見える。★
まずはそれを目指す。
その後、でかい組み合わせでそれよりいい解(各集合の真ん中くらい)になるやつが見つかれば、
それを固定した上で、残りを詰めてみるとか。☆

良し悪しをはかる物差しが難しい。
小さい順に5つとか持っておいてもいいが、最後詰める時には測れない。
うーん、他ができてから考えるか。

ある集合を使う時、既存の集合と比較しようとしても被りがあるとできない問題。
→やはり雑に平均に近い集合を複数持つのは大事そう。全体の平均は変わらないので。

seed=14、こういうパターンもあるっぽい。これはこれで選択肢が減って良い。ちゃんと検知するのが大事そう。

■DFSで理論値近く
ある答えが出た時の平均からのdiffが小さくなる組み合わせのみ考える。
seed=6、完全一致出る。

うーん、Nが大きくなるとD=2でもだめだ。
別途焼きなまし的な解法で近似解だそう。★

### 実装2

でかいやつからならすのをやる。
まずは赤部分の両端の順序をハッキリさせる。真ん中はなだらかなのでざっくりでいい。

それっぽいのできた。0～30をソートする。両端8番目まではちゃんとして、間を適当に。
[0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 13, 14, 15, 21, 9, 10, 12, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
↓ここが適当ソートになっているんだけど、頭とお尻を混ぜた方がいい。
[8, 11, 13, 14, 15, 21, 9, 10, 12, 16, 17, 18, 19, 20, 22]

混ぜた。いい感じ。
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 10, 13, 12, 14, 16, 15, 17, 21, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]

先頭側の方が精度高めにでるので、重い順に並べることにする。
8番目までをlimitにしているが、ソート済み範囲であれば正確にソートしたらよさそう。★

できた。seed=0
この時点でN=31でQを120使ってる。これじゃ2Nに入らないのでだめ。

マージソートがN×log(N)なので、それはそうなのだが、
2Nでおさめないといけない。
limit = 1 でも、seed=0で両端ソートしただけで60クエリになる。
Qがめちゃ少ない時は特別処理が必要。★
→でかい方だけ求めて、あとはよしなに。
→seed=5が全然だめ。Q=202なのに、今のだと272回かかる。
→両端マージが終わった時点では121回なので、どうにかなるはず。
→100ケース中、半分がover。

Dが大きい時に上手く減らしたい。
集合の比較を小さいのから順ではなく、pivot作って飛ばすのが良さそう。

(seed=15560がScore=1出る。)

**TODO**
~~入出力作成~~
~~内部シミュレータ作成~~
~~バッチ処理~~
~~愚直解出力~~
~~スコア計算(ベストを保存する機構)~~
~~分布の確認~~
~~dfsで理論値(もしくはそれに近いもの)を求める→だめ~~
焼きなましで理論値近似解
でかいやつからならす
~~→両端だけマージソート~~
→ソート済範囲はlimitに限らずソートしきる
~~→ソートの結果から順番に入れる~~
Qがめちゃ少ない時の対処

## 2日目
### 所感
10時、提出してないと順位表の情報量ないなー。
simanさん久しぶりな気がする。

### 実装
クエリを減らす。
→Dが多い時にバブルソートしちゃってるので、2分探索で工夫する。
→所謂バイナリソートだった。した。seed=5が312→215回に。Q=202回なのでもうちょっと。
→少し上目に寄せたほうがQの回数は減りそう。
両端マージソートで、指定のサイズじゃなくソート済範囲のは比較することにして、
所定のサイズ自体は小さくすることでクエリ回数を減らす。
→そもそも小さいサイズでの挙動確認。→サイズ1でもoverしてる。
→ソート後でクエリN回弱くらい、リミットまでN～2N回の余裕はある。
→真ん中当たりは2個積みをするか。→重い順に20～90%の区間でした。がまだこれだけある。

OverQ=239>199 N/D=88/17 SQ=74
43=0.0822 s=6700244 T=7
OverQ=194>161 N/D=74/12 SQ=61
93=0.0296 s=8912767 T=0

→(2個積みをした方がいいかは後続のswapの回数稼ぎとトレードオフなので後でcheck)★
→Dが大きめではある。
集合のソートを遅延にできないか？
→遅延セグ木的なやつ。(遅延セグ木はわかりませんが)
→最軽の集合に追加してあるpivotより重くなるのが見えたのなら、
　そのpivotより軽い集合に対して、それぞれ追加しちゃっていい。
→追加後もpivotを越えないのであれば、越えるまで追加する。
→全ての集合がpivotを越えたら、pivotの集合にも追加した上でソートする。
→だめだ比較が2Nくらい増える。ソート済であることが重要っぽい。
→や、これpivotを越えたやつの細かい順序評価を遅延できるのが嬉しいのであって、
　pivot前後をごちゃ混ぜにしていいわけじゃないな。
→違う。pivot後はソート済なので、pivot前の不明集合を部分ソートして、マージするんだ。
→した、が、クエリ回数が微増。この方向はちゃんとソートしちゃってよくない。
→ソート順が不明にならなければいいので、大きい順にItemを追加とか？✕
→ヒープでやるか。最軽の集合さえ特定してたらよいので。
→した。が、やっぱりクエリ回数が増える。
　→rootの集合をshifDownしていく方法でやったが、削除後に挿入した方がよいか？
→フィボナッチヒープとかいう最強のヒープを見つけた。顧客が求めていたものじゃん。
　https://37zigen.com/fibonacci-heap/
この動画が神がかったわかりやすさ。
https://www.youtube.com/watch?v=6JxvKfSV9Ns
突然フィボナッチ数が出てきて鳥肌たった。
　→これを理解するに、任意の集合の値をdecreaseできそう。
　→decreaseじゃなくてやりたいのはincreaseじゃん。
　→今回の最軽=根の値更新は、popとinsertを同時に行ったのに同じ。
→実装重そうだけど、kenko4さんがjavaの実装書いてくれてるー。
　https://kenkoooo.hatenablog.com/entry/2017/12/01/184539
→フィボナッチヒープや他ヒープは、popのオーダーが大きい。今回pop/insertのみなので厳しい。
→pop/insertは必ず重くなるので、単調優先キューと言える。
→単調優先キューで計算量が下がるのはバケットソート系(Heap On Top Queues)しか出てこない。
→soft heap なるものがあるらしいが解説が見つからない。
　→どうも、pop後の根について一定壊れた状態を許すらしい。
　https://github.com/millimat/Soft-Heap
→今回の問題でも厳密に最軽である必須性はない。顧客が求めていたもの2。
→データ構造を理解する。
　→まず木構造のNodeが単一要素ではなく複数要素を持つらしい。
　→これでのなんらかの変化があった時に"相乗り"して移動するのだと。
　→ランク、という概念との比較がありこいつは整数限定なのかもしれない。なら使えない。
→単調優先キューでpop/insertオンリー、厳密じゃなくていい、という前提条件で、
　新しいデータ構造を作るしか無いかぁ…。
(こういうインタラクティブな比較問題、ソートアルゴリズムの勉強になるなぁ。)

オリジナルの単調優先キューを作る。
→フィボナッチヒープをベースに複数の二項ヒープ木があるのは良さそう。
→pop/insert(以降popint)時に、比較回数を抑えるのが大事。
・単調増加でpopintオンリーの性質を使って
　→popintした後、片方の子ノードと比較して子ノードより重いなら子供にしちゃうとか。
　→重くなければ、純粋にinsertと同じ処理。
・firstが厳密じゃなくていいという性質を使って
　→更新したターンを覚えておいて、古い順から候補に上げるとか。
　→候補になった古いやつは、親がいるならその親に候補権を譲る。(再帰)
　→候補のノードとpopintノードを比較、候補ノードが小さいならfirstにしちゃう。
　→popintノードが小さい時、フィボナッチヒープのpop時と同じくリストを整理。
・その2、popint後のもそこそこ軽い期待の上で
　→子供が0のノードは、それが一定数溜まるまでは放置。
　→基本は子供が1以上のノードとpopintノードを比較、小さい方をfirstにする。
　→popint後、子供0ノードが一定数溜まったら、popintノードも含めて整理。
　　→(多分)比較回数が多くなりがちなpop後の整理をサボれて嬉しい。
その2とかの方向でええんちゃう？

FBH(Fibonacci Based Heap)を実装する。
→kenko4さんのやつ、ちょっとようわからんくなる。
→メモリとかは潤沢に使っていいので、やりやすいように書き直すか。
→明日popint()の実装から

マージソートの端数がよくなさそう。今は2の倍数からあぶれたやつが最後にマージされる。
→マージするペアを上手くバランスを取る。★
→マージ挿入ソートという、最初だけK個に分割して挿入ソート後マージするものがあるらしい。
　1959年のNが小さい時の比較回数最小化を狙ったものだとか。顧客が求めていたものじゃん。
　https://en.wikipedia.org/wiki/Merge-insertion_sort
　マージペアのバランス取る問題もこれと合わせちゃえば良さそう。
　通常のソートと違って合算値を比較できるので、これも組み合わせたい。★
　→基本的に軽いより重いが差が大きいので、重い順の挿入ソートが比較回数少なそう。

貪欲で構築した後のswapの一般化。
集合G1とG2がG1>G2の時、それぞれの部分集合g1,g2がg1<g2として、
G1-g1+g2>G2-g2+g1、が成り立てば改善したと言える。
g1,g2はなるべく小さい要素だと、あとで使い回せて良さそう。
→使いまわしやすい部分集合の比較を選んでいけると色々と捗りそう。

**TODO**
でかいやつからならす
→ソート済範囲はlimitに限らずソートしきる
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
~~→Dが多い時に2分探索でソートする~~
~~→複数個を一気に積む~~
~~→ヒープで最軽集合だけに注目する~~
~~→より良いヒープを見つける~~
→FBHの実装
　→popint
　→pop後のfirstを上手くサボって求める
複数積みのON/OFFをスコアを見て調整
マージソート時のペア選択の工夫：マージ挿入ソート
→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう
焼きなましで理論値近似解

## 3日目
### 所感
10時半頃、やはり情報量ない。Rafbillさん抜かれたと思ったけど、また返り咲いてる。
意外と上位の差がない。まだ重実装に移れてないのかどうか。
比較問題、重実装になりがちだと思っているけど、みんなそれを既にやってるとは思えん。

そういえば、今回は相対評価がスコア比じゃなく順位で決まるのは、
偶然めちゃいいスコアが出た人がいると、スコア比にすると他がほぼ0点になるからだな。

### 実装
FBHの実装、popint()作る。
→あれ、pop時にfirstを探す時、比較したはずの木をなんで分けた残しとくんだ？
→うーん、柔軟な操作のために残してるだけっぽくて、1つの木にしちゃっても良さそう？
→二項ヒープとして色んな操作を高速に行うために各次数に応じて置いてるだけっぽい。
→今回高速化は不要なので、比べたならヒープに混ぜて良さそう。
→popint時に生成される子供の数は本質一緒。
→となると、FBHでは大きな木があって、pop時に切られた枝のpoolがあって、
　pop後、poolの枝は全て整理されて大きな木を再構成するでいい。
→できた。ひとまず厳密に返す。1件ずつでこれなので多少良い？

OverQ=324>199 N/D=88/17 SQ=74
43=0.0829 s=6646561 T=4
OverQ=273>161 N/D=74/12 SQ=61
93=0.0331 s=7951264 T=4

→前と同じ条件で2つ一気に入れるとこれ。前よりも下がった！

OverQ=221>199 N/D=88/17 SQ=74
43=0.0804 s=6853589 T=9
OverQ=182>161 N/D=74/12 SQ=61
93=0.0298 s=8831462 T=0

(前回)
OverQ=239>199 N/D=88/17 SQ=74
43=0.0822 s=6700244 T=7
OverQ=194>161 N/D=74/12 SQ=61
93=0.0296 s=8912767 T=0

うわ、両端マージバグってて、batch=1の時比較skipしてた。
ちゃんとするとこう。うー、また遠のいた。

OverQ=283>199 N/D=88/17 SQ=121
43=0.1123 s=4902777 T=1
OverQ=231>161 N/D=74/12 SQ=100
93=0.0397 s=6634614 T=0

単純化のため、また1つずつ入れるのに戻す。キビシー！

OverQ=414>199 N/D=88/17 SQ=121
43=0.2206 s=2496466 T=1
OverQ=320>161 N/D=74/12 SQ=100
93=0.0713 s=3694029 T=1

FBH、firstを求めるのさぼるやつやる。
→pool内の個数が一体以内なら、一番次数の大きな根とだけ比べることにする。
→次数が大きな木ということは、それだけ中では優先度が高いことの証明。←これ天才ポイントでは？
→やった。とりあえず根の数がDの20%を対象にやった。
seed=43は解消、93もほぼほぼOKになった。やったね。ただし得点は1/3になった。

OverQ=162>161 N/D=74/12 SQ=100
93=0.0036 s=72580670 T=0

→2つ一気に入れる。Dが大きいやつのクエリオーバーはなくなった。
→一方、両端マージの修正でDが小さいやつでクエリオーバーが出てきた。seed=57とかやばい。

OverQ=232>200 N/D=96/3 SQ=128
57=0.0477 s=784255 T=1

→5つ一気に入れてようやくオーバーしない。
　→seed=57、5つ一気にいれても意外と悪くない。
→これまでのいろんな優先度付きキューと比べたけど、流石に今のが一番クエリが少ない。

→今回のはDが小さいから起こるものでもない。単純にNに対してQが小さいから起きる。
→と思ったけど、20%の恩恵がないD<11しかない。調べよう。
→seed=57、D=3で、2つ一気に入れることもあって結構な頻度で2回クエリ叩いてる。
→Dの20%だとskipが全くされないので、poolの根が3以下で常にskipにする。
→バグってた。skip時にpoolをクリアしちゃってた。直してこれだけ残る。

OverQ=112>97 N/D=43/6 SQ=57
17=0.0784 s=1938590 T=7
OverQ=228>226 N/D=80/7 SQ=108
28=0.2093 s=2394226 T=1
OverQ=272>199 N/D=88/17 SQ=121
43=0.1250 s=4407168 T=1
OverQ=174>162 N/D=61/5 SQ=81
53=0.0202 s=5263703 T=0
OverQ=231>161 N/D=74/12 SQ=100
93=0.0397 s=6634427 T=0
OverQ=228>204 N/D=74/14 SQ=103
98=0.1935 s=3297633 T=0
TSum=4.3717394E8
RAve=0.10615807497395621

→Dで制限なく、単純にNに対するQが苦しいやつで揃っているので合ってそう。

あれ、こうなるとseed=43とか前の方が軽い？
→そんなことなかった。いまのが一番軽い。
→5つ同時に入れるとなると全て通るが流石におかしくなる。
seed=43

ヒープを再構築する時、どうせ比較するならItemを追加した上で比較したらいいんじゃない？
→子供がいるノードなら最大で無いことは保証されるので。
→いや、むしろ優先付きキューを重い順にして、末端に同時に追加したらいいのでは？
→そうすればフィボナッチヒープの良さが出る。(popが発生しないので)
→すると、2つの問題が出る。
　・同時にいくつのノードに追加するか？
　・根のひとつ下に小さいノードが残り続けちゃうのをどうするか？
→HP制を導入する。二項ヒープ構築時に深さに応じてHPを設定。
→HPが0になったやつをpoolに移動してItem追加。二項ヒープを再構築する。
→ダメージをどう与えるか？末端ノードに対して均等に1ずつで良さそう。
→こういうのがあると、左2番目のやつに無条件で追加はまずい。
→元が一定の深さ以下で、poolに流れてきたやつをItem追加対象にするか。
→HPの調整で追加頻度は調整できるので便利そう。
→偶然更新を避けられちゃわないよう、更新の古いノードの順に比較する。
→根を深さ1とした時、深さ3以降はItem追加をしちゃって良さそう。
→ただし、D<4は深さ2までしかできないので、深さ2に対してItem追加しちゃって良さそう。
→うーん、そもそも避けたいのは単一Itemでほぼほぼ平均に近いやつ。
→初期Itemを格納後、自身より軽い初期Itemのみの集合があるのはLockしておくとか。
→比較回数も下げられて良さそう。
→この状況なら、HPが0になったやつは無条件でItem追加しても大きな問題にはならなそう。
　→HPが0になるのはItemが2個以上あるやつで、自身より大きな集合を期待でき、
　Itemのsortから自身より大きな集合の直近の追加Itemより、軽いItemが追加されるため。
　→同時追加のタイミングがDに応じて上手く調整されてよい。

唐突にこのヒープを Fall Heaps と名付けるのが良さそう。
(落ち葉のように末端ノードが落ちて、根から木が成長するので。)

**TODO**
でかいやつからならす
→ソート済範囲はlimitに限らずソートしきる
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
~~→FBHの実装~~
　~~→popint~~
　~~→pop後のfirstを上手くサボって求める~~
Fall Heaps の実装
複数積みのON/OFFをスコアを見て調整
マージソート時のペア選択の工夫：マージ挿入ソート
→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう
焼きなましで理論値近似解

## 4日目
### 所感
11時半頃、Rafbillさんが結構極めてきた印象。ここがラインになりそう。

### 実装
FH(Fall Heaps)を作る。
仮で最深か深さ2以上を毎回追加対象にするようにした。クエリoverがこれ。

OverQ=221>200 N/D=96/3 SQ=128
57=0.0246 s=1519822 T=10
OverQ=134>125 N/D=58/2 SQ=78
87=0.0009 s=530101 T=3
OverQ=170>161 N/D=74/12 SQ=100
93=0.0383 s=6874136 T=4

seed=43がこれ。5個同時追加よりはまし。

いまはfirst(最重)の扱いも適当なので、マージに時間かかっちゃってるかも。
seed=93あたりはDが大きめで解消できるはず。
→見直してlockも考慮。回数としては1だけ悪化？
→そこから2つ同時追加を加えてようやく収まった。

TSum=6.69953349E8
RAve=0.06710639263842898

ここからさらに減らすには、両端マージ側を減らすしかない。
→やはり小さい方は諦めて大きい側だけソートするか。

Itemの重さをちゃんとソートしてないのもあるけど、最小じゃないのでこういうのが生まれちゃう。
やはり最小は常に入れるのが大事そう。
→FHで最小ヒープにして、根から一定距離をpopするとか。
→HP制は有効なはず。根から枯れていって、枝から先はpoolに回して二項ヒープを再構築するとか。
→最軽を優先して増やしたいが、最軽だけ変えた場合は比較が勿体ない。
→最軽には2つとその直下の子持ちには1つずつItem追加するのがいい。
→挿し木っぽいな、挿し木ヒープ(Cuttage Heaps)というか。

実装した。2-1の追加だとオーバー。

OverQ=103>97 N/D=43/6 SQ=57
17=0.0494 s=3074178 T=11
OverQ=246>199 N/D=88/17 SQ=121
43=0.1609 s=3423678 T=1
OverQ=212>200 N/D=96/3 SQ=128
57=0.0287 s=1304694 T=1
92=0.0960 s=6869732 T=2
OverQ=200>161 N/D=74/12 SQ=100
93=0.0548 s=4810297 T=0
100=0.2614 s=3847164 T=5
TSum=4.23420431E8
RAve=0.08364217056209343

FHよりクエリ回数は多く、点数は高い。
結局子供がいるNodeを更新しちゃうので、バラバラになって整理に比較が必要になる。
→FBHの時のように、上手くサボりたい。
→Itemを1回追加するのにどうやっても比較を1回しないといけない。
→Item側をまとめるしかないか。

Item側をまとめておくと、重い集合はまとめたアイテムをバラして渡すということができる。
→Itemは2個セットがいい。1回の比較で大小がハッキリするので、
　2個セットをバラして集合のdiffを縮めるのに役立つ。
→2個セットの欠点、重いのは分布的に逃さないが、軽いのは逆にまず見つからないこと。
→最初に個別に求めるか、最後のswap中に求めるかが難しい。
→Qに余裕があるなら、最初に求めた方がいい。どうせでかい方も後でバラすし。

ペアItem、やる。
→ペアにしたItemはソートし切るために以前調べたマージ挿入ソートをやろう。↓がわかりやすい。
https://github.com/decidedlyso/merge-insertion-sort/blob/master/README.md
→ペアを作ったあと、重いペアは分割して余り同士でペアを作り直す。
→重さは指数的に増えるため、ペアは重い方の影響が支配的。
→なので、ペア状態でK=2のマージ挿入ソート前半した時、
　ペアを分割して大きい方の並びでほぼほぼソート済になる。
→これは、ペア分割後にソート済かの確認を省ける。
→Kが２以上の活用はあるか？

最後のswap段階、フィボナッチヒープで持つのが当然強い。
→両端フィボナッチヒープとかどうか。やりたいのは最大と最小のdiffを縮めることなので。

**TODO**
でかいやつからならす
→ソート済範囲はlimitに限らずソートしきる
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
~~Fall Heaps の実装~~
~~→適当実装~~
~~→整理時の適正化(lock)~~
→ペアItem化
複数積みのON/OFFをスコアを見て調整
マージソート時のペア選択の工夫：マージ挿入ソート
→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう
焼きなましで理論値近似解

## 5日目
### 所感
折返し。11時半頃。点数変わらなくて情報量ゼロ。
全然提出まで遠くて良くない気がしてきた。

### 考察
今回の問題、Qの余裕に応じてdiffのメモリをどれだけ小さくできるかの勝負。
・Qの余裕ある時、最軽Itemよりも小さいメモリをどう作るか、どう調べるか。
・Qの余裕無い時、Item集合からメモリレンジをなるべく小さくする。
すると、ロジック的には以下のパターンか
１．Item個別にソート(ペアマージ挿入)、順に詰めていき、最軽Itemのメモリレベルで整えた後、
　　最軽Itemよりも小さいメモリを作成、それでさらに詰める。
２．Itemを両端マージソート、途中は適当(ペアItem)だが最後は最軽Itemのメモリレベルで整える。
３．Itemをペア化、ペアマージ挿入でソート、Qの残りに応じてペアを分けて平均化していく。

Itemをペアにすると、N：15～50。マージ挿入ソートは2007年の論文でN<47で他に単一のよいアルゴリズムは見つかってないらしい。ほぼほぼ今回の問題に合致しそう。

but no better algorithm has been found for N < 47 and it has been proven that it would need to rely on a completely different strategy (Peczarski 2007). 

Item(ペア含む)の重さ順をソートしたあと、Item数N'に対しN'-D回の集合への追加が発生。
1回毎に最低1回比較がいる。なので、Qは[Itemソート] + N'-D + α となる。
Itemソートの比較回数、両端マージをやるとやはりかかる。
マージ挿入ソートで重いやつだけ判定してやる
1サイクル後、マージの片割れはマージ済の後である情報が残っているので、それらもまた加えてやる。
2サイクル目もマージの大きい方はちゃんとマージ済の中で順番を決める。
残りは一定順位以下な事がわかれば、細かい順序は不要。
→1サイクル目の時点で、マージの大きい方の正確なソートが不要。
→二項ヒープ的な方向で考えられるか？られそう。
→過去の比較結果から、挿入ソートの位置を絞れる。
(ペアとマージ挿入ソートのカップルがややこしいな。マージ挿入ソートはカップルと呼ぼう。)
→カップリングした状態で上半分だけソートをやり切る。
→上半分のカップルを破局させて、新たなカップルを作り、ソート済列への後ろ情報を活かして挿入。
　→これ、むしろ大上段から半々に分けていく方が賢いのでは？
　→集合を半分に割って重量を比較、一番重い集合をさらに割る。
　→集合を割る=popintになる。次数poolに入れて、すぐにマージ。
　→popintしたうちの重い方が、基本的には一番重い。
違うこうだ。
→全体を4or3個の集合に分け、カップリングを作ったあと二項ヒープ。
→最重が確定したら割る=pop。割った後の軽はsize2のwaitingに回し、重はsize2のヒープへ。
→最重のカップル相手はsize4のpoolへ。同サイズのpoolに2つ溜まったらカップリング後insert。
→残りで最重を作り、割っていく。半分くらい割れたら終了。(なのでsize3,4の集合で残す。)
→同サイズのpoolに2つ溜まったら、統合して倍のsizeのwaitingへ。=insert
→ヒープ領域に入れる際、軽い方から挿入ソート。2分探索いらないはず。
　→いや、これは最後1つになった時にやるだけにして、途中は省こう
→sizeをひとつ下げ、size2のヒープで同様に行う。
→割る場合にランダムにわると以前の情報を使えなくなるので、割り方は予め決めておく。
→マージ挿入ソート的なカップリングは最初だけなのでは？
　→ペア比べているので最後にカップル解消とも言える？
→最初に全て比較するのが大事なので、2の倍数で作る。

これで最後まで求めても早いんだろうか？挿入ソートの回数次第な気がする。
→計測用の機能を作っておこ。

### 実装
ペアItem化、やる。
→Kが２以上の活用はあるか？について続き。
→Kは問わないが、ソート対象がD個ならそのまま問題の解。
→ただ、N/2で15～50なので、それが間に合うならなるべくメモリレンジを狭めるためK=2のまま。
→NlogNで、15～50は、58.6～282.2。最小のQ=2Nで30～100なのでだめ。
→やはり後ろの方を適宜諦めるのが大事そう。大事なのは前だし。
ペアにはした。次、マージ挿入ソート。
→名前をつけよう、split sort かな。

ind順に降る初期回適当が以外と高い。
`RAve=0.016202684441662493`

**TODO**
でかいやつからならす
~~→ソート済範囲はlimitに限らずソートしきる~~→split sortで代替
→split sort
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
~~→ペアItem化~~
複数積みのON/OFFをスコアを見て調整
マージソート時のペア選択の工夫：マージ挿入ソート
→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう
焼きなましで理論値近似解

## 6日目
### 所感
(仕事ががが)

### 実装
split sort やる。
→1段階目をやった。

seed=0でクエリ 39回/128  N=31
seed=1でクエリ172回/1120 N=56
seed=2でクエリ278回/2009 N=98

→sort結果はあまり正しくない。
マージソートでソートしきるとこんな感じ。Nlog2Nから少し減る。

seed=0 sq=114
seed=1 sq=257
seed=2 sq=508

→2段階目ですでに1Itemまで割っちゃった方が良さそう。
　→1段階目のあと割ってるのでsortが正しくない
　→2Itemの状態でsortしなおすとsort回数が多いし、sort省くとじゃあ何やるの？になる。
　→マージ挿入ソートを使う。
　→実装、した。
全部sort仕切ってこれ。このままだとマージソートより弱い。

  0=0.001 s=10104951 sq=135
  1=0.002 s=38839035 sq=391
  2=0.011 s= 7793696 sq=753

→popした後のfirst決定について
　→後から入ってくるのは割ったやつとか、初回で軽かったやつ。
　→なので単純にfirstと比較するのは無駄多、最長の半分と比較してそれ以下になればいい。★
　→それ以上なら挿入ソートで1つずつ上げて最長にsortして伸ばすでいい。
やったが微減くらい。
　→まだ前回比較情報は使ってない。★

  0=0.001 s=10104951 sq=135
  1=0.002 s=38839035 sq=385
  2=0.011 s= 7793696 sq=743

やはり全部やるならマージソートが早い？
→最後sort仕切る時に後ろ寄りの二分探索する。★
→どこに回数かかってるかちゃんと調べる

→残ったやつどうするの問題、
　→2Itemにまとめてなおして、ざっくりsortしたい。
　→今度は軽い順でいい。既存のヒープ木は最長だけ残してカット。
　→軽い順でまたヒープ木作っていれていく。残した最長ヒープ木のうち、どこから開始するかは大事。

貪欲で詰める時、比較しながら詰めなくて良いのでは？★
→大きさの順序がわかれば後は順々に詰めていけばいい。
→詰め終わったらソートして動かしながら比較。
→Itemの重軽順はわかっているので、動かすItemを二分探索できる。
→仮詰めした時、一番重いItemがすでにオーバーしてないか調べるために、順番に詰めた時の一番軽いものと比較してとく。★
→オーバーしたなら、そこにはItemをskipして他だけを詰める。
→実験して何番目が少なくなりがちか見る。

**TODO**
でかいやつからならす
~~→split sort~~
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
複数積みのON/OFFをスコアを見て調整
マージソート時のペア選択の工夫：マージ挿入ソート
→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう
焼きなましで理論値近似解

## 6日目
### 所感
(仕事ががが2)
グェってたら、妻から「やれ」と。はい。。。

### 実装
クエリの計測、順にsort済:1Itemに割って大きい方をsort:1サイクル目後
→1Itemに割って大きい方をsortに結構取られてる？

  0=0.001 s=10104951 sq=135 :80 :39
  1=0.002 s=38839035 sq=385 :274 :166
  2=0.011 s= 7793696 sq=743 :497 :268

どうもこれをみるに、両端マージで最悪比較回数の理論値をかなり下回れてるらしい。
https://warwick.ac.uk/fac/sci/dcs/teaching/material-archive/cs341/fj.pdf

マージソートで、片方を並べきったら残りは比較無しで入れられる。
→これが起こりやすい環境を作れば、平均比較回数は減らせそう。
→最初に全体の比較をする効果はあるか？→結局比較をしちゃうので微妙そう。
→両端マージだと、極端な大小があって、最後まで残り続けることがないのと、
　毎回真ん中のあたりでどっちかが先に終われば終わりなので+1,2回得しそう。
→全sort可能ならやはりこっち。逆に部分ソートは微妙そう。最初に1:1比較をするのでN/2。
→両端マージは比較回数減らす工夫できそう。片方が残り1つとなったら二分探索で入れるとか。★
→両端マージのsort checkする。→OK、やはりこのソートはよいもの。
→両端マージじゃなく、純粋マージが動いていただけだった。両端側を全対応してみて測る？★

よって、間に合うならマージソート、間に合わないならsplitソートで上位だけ求める方針。
→splitソートで最後まで詰め切らずに、複数Itemのままsortは仕切りたい。
　→後の貪欲で詰める時に利用。
→1サイクル目の重軽関係は流用したい。末端から親がいたらsize=2のマージ済みとできる。
　→できた。ちゃんと動いてる。
→あー途中打ち切り時、2サイクル目が上から◯番目までは正しい、というのをちゃんとやらないと。
　→今日はもうダメ。明日ここから。

最軽Itemからさらに詰める時、ある集合とある集合があってその差が極小になることを確認してswapになる。
→この時、できるだけ数が多い集合の組からやった方がいい。あとの詰めが消去法になる。

**TODO**
でかいやつからならす
→貪欲で詰めた後swapする。
Qがめちゃ少ない時の対処
→split sortの打ち切り処理
~~複数積みのON/OFFをスコアを見て調整~~集合として扱うことになったので考慮済み
~~マージソート時のペア選択の工夫：マージ挿入ソート~~やらない
~~→挿入ソート用に合算値による比較の活用方法を考える→大雑把に大小作れそう~~やらない
~~焼きなましで理論値近似解~~もういらないかな

## 7日目
### 所感
残り30時間。。。今日は衣装合わせもある。いい息抜きか。
7時半頃、アルゴ強い人が強そう？USAさんが90Gだったりと、通常のマラソン問とは違いそう。

### 実装
splitソート打ち切り
→した。上位10%まで求めた

　0=0.001 s=10104951 sq=46 :22 :14
  1=0.002 s=38839035 sq=119 :49 :37
  2=0.011 s= 7793696 sq=245 :118 :90

→Nが大きいと2Nを越えてくる。上位5%にする。→違う。Nが大きい方が苦しいので8-5%で。

  0=0.001 s=10104951 sq=87 :43 :25
  1=0.002 s=38839035 sq=132 :58 :39
  2=0.011 s= 7793696 sq=166 :63 :49

→案外上位の1Itemは拾えてない。が、拾えない時もでかい塊を崩せているのでよし。
→ただ、すでに2Nくらいかかっていて厳しい。
→最後、後ろからマージソートしているけど、前からでいい？でも早く終るならそれはそれでいい。

よーし、貪欲でうめるぞー。
→できた。重い集合から順にDをいったりきたりしながら詰めただけ。
seed=1、悪くないじゃん。

seed=33、こういうのも案外いける。
おっと、これでもoverするか。

OverQ=100>97 N/D=43/6 SQ=-1
 17=0.069 s= 2211742 sq=100 :45 :27

→かなり厳しい。N=35のQ=70とかだと全然ダメ。5-ceil(N*4%) にしてようやく。
→無理に割らずに4つセットで集合のソートだけでいいかも。
→4つセットの集合のままソートする。★
→した。最大Nくらいになった。

  0=0.002 s= 7458851 sq=17 :7 :7
  1=0.003 s=19191247 sq=53 :15 :15
  2=0.007 s=12267093 sq=96 :23 :23

（ただこれまで考察してきたことは全部無駄になったな。。。）

seed=9、まぁこういうことになるよね。
Dがでかいやつの時、1集合しか入れないのが出てくる。
→入れた順でsort済になる。それ以外は未sortとする。

貪欲で詰めた後swapしていく
→ソート済の頭と尻でswap検討
　→Item追加後、大小関係を変えないので前後関係が明瞭。
　→そのままマージソートできる。
　→した。
→swapできなくなったら、どんどん粒度を細かくしてく。
→粒度と粗い順に下記の通り。
・集合をまるっと移動　→　した。
・一番大きな集合を割って割ったものに対してこれまでのswapを試す
　→やる→したが色々エラー出るので対応。
　→あれ？ソートしただけで2Nかかってる。
　　`seed=57 OverQ=220>200 N/D=96/3 SQ=-1`
　　確かに元も結構ギリギリだったっぽい。
　　`57=0.001 s=44823869 sq=168 :50 :37`
　→バグってクエリを二重計上してた。クリア。
　 `57=0.018 s= 2033248 sq=108 :25 :25`
・重軽の順序を把握した上で集合同士を交換
　→1:1交換をやった。尻側を割る処理も追加。23%まできた。
`RAve=0.23451856552350137`
seed=9、難しいやつもいい感じ。ただ515/885回しか使ってないので、まだいける。
マージソートしない時はここまでだろう。
→重い方がすでに要素ひとつならこれ以上無理なので飛ばす。→やった。
→1Itemで最重なら参照を外す。
→max diffをどんどん下げて行く戦略、失敗操作を記憶してそれより小さい差のみやる。★
さらなる操作
・複数交換どうするか。
　→重バッグに細かいのが来て欲しいので、1→2の交換にする。
　→した。いーじゃーん。
・交換対象のバッグを変えていく？(2,3番目のも解消した方がいい。)
　→した。いーじゃーん2。
いくつか最高値も更新して40%。
`RAve=0.3939099784677868`
まだよくないのはこういうの。seed=11、Qが6N弱と小さいのもあるが、クエリ節約必要そう。

そういえばQに余裕があるやつは、フルマージがいいんだろうか？やってみる。
→上がるっぽい。無駄じゃなくてよかったというべきか。
　`RAve=0.4151414273822119`
→seed<100でこんな感じ。よいでしょう。

  1=0.571 s=   76717 N/D/Q=56/ 6/1120 sq=257
  2=1.000 s=   20545 N/D/Q=94/ 5/2009 sq=508
  3=1.000 s=   56966 N/D/Q=80/ 6/2288 sq=427
 10=1.000 s=  127385 N/D/Q=65/10/1690 sq=310
 26=1.000 s=    2551 N/D/Q=96/ 2/1344 sq=530
 42=1.000 s=   21412 N/D/Q=87/ 9/2486 sq=470
 46=1.000 s=    3512 N/D/Q=45/ 3/ 860 sq=194
 48=1.000 s=  103331 N/D/Q=54/ 7/1183 sq=249
 50=0.149 s=  120495 N/D/Q=66/ 4/1200 sq=343
 58=1.000 s=  223445 N/D/Q=49/ 8/1467 sq=216
 64=0.434 s=   10943 N/D/Q=86/ 3/1312 sq=468
 67=0.614 s=  152290 N/D/Q=70/11/2101 sq=379
 71=1.000 s=    3877 N/D/Q=54/ 3/1483 sq=235
 79=0.647 s=   44808 N/D/Q=51/ 4/1344 sq=228
 84=1.000 s=   23432 N/D/Q=51/ 5/1101 sq=230
 91=1.000 s=  115599 N/D/Q=74/12/2358 sq=391
 94=0.015 s=   26501 N/D/Q=66/ 2/2009 sq=370
 99=1.000 s=    1051 N/D/Q=64/ 2/ 956 sq=305

→同時にいくつか割るやつって有効なのか？
前の　　　`RAve=0.32503986504843374`
上位10%　`RAve=0.3329484306171475`
→有効だった。良かった。　指定はこれ。20-ceil(N/10)
念のためフル `RAve=0.38852255044420225`
細かい条件詰めはまたやる。

有効な操作を足していこう。
・小さい集合をpoolしておいて、最後の詰めに使う。
　→意外とやることあるな。割った時にpoolを出し入れしないといけない。
　→poolから徐々に割当ていくのもどうしよう。
　　→過去のpool値のindは増える
　　→とりあえず最大1個は保持、変数で指定して交換フェーズまでいったら0にする。
　　→うーん、ちょっと上手く動かない。ひとまず提出。
・ちょっとだけなら逆転を許す操作

提出
→1000ケース、4つまとめてsortでこれ。
`RAve=0.5636891025870432`
→全マージを 4*N*pow(D, 0.5)以上で。
`RAve=0.5596338523205765`
→上位だけ割るのいらなそう。
提出！
まぁ妥当かなぁ。。。

パラメータ調整、4.5*N*pow(D, 0.3)

**TODO**
でかいやつからならす
~~→貪欲で詰めた後swapする~~
~~→いろんなswapをする~~
→小さい集合を後入れ
→逆転許可
~~Qがめちゃ少ない時の対処~~
~~→split sortの打ち切り処理~~

## 8日目最終日
### 所感
得点に直結するやつやらんと。
9時半時点で142位。

### 実装
100ケースで51%から。
`RAve=0.51216952882704`
過去結果流用、まずはメモ化だけでも。
→した。
`RAve=0.5021242167946359` →　`RAve=0.5329344129017346`
→提出。86,192,344,045、111位。

最軽プール、単純移動が起きなかったときに。
→悪化する。上がってるやつもあるっぽいが。とりあえずフルソートの時のみが良さそう。
→うーん、他の優先的にやろう。手放し。

2→1交換
→やった。2/100ケースしか該当しないけど、細かくなってからの改善なので大きい。
`RAve=0.4863008217650868`→`RAve=0.4899169511629622`

diff max の保存と打ち切り
→やったが点数みは見られず。→min保存してた。ちゃんと上がった。

seed=93、こういう時、0番目のバッグの2番目の重いのをより軽い他の集合と交換しちゃう。
→やったが、バッグ同士の並び替えで消費しちゃう。
→やはり大小関係は崩さない範囲で交換とする
　→崩さないので最大効果を狙う→結局普通に割るのと変わらない
→割る回数が増えて、割後のItemのsortにクエリを消費しちゃう。

割後のItem sortの効率化
→末尾からのマージソートになっているが、Itemは割当先が長いので特に序盤は狂う。
→した。ちょっと改善。

2→1交換が非効率だった。
→改善。seed=99で51！うぉおおお。
→提出103位、ギリギリ黄パフォ。

複数交換とQが少ない時の結果が流石によくない
→複数交換詰めて、極小改善を上げる方が特定ケースで順位は上がりそうだが、
　さすがにまだ全体的に低いので、Qが少ない時の対処に残り時間を使う。
seed=5、最初は移動をしているが、4つセットの時は単品と集合の交換を優先した方が良さそう。
→大きい交換なので失敗しがち。4つセット交換は難しいかも

そもそも、バッグのソートしているので、次のMaxより軽いならOKにする。
→単純moveに適用した。大分天井が伸びたっぽい。他にもかけてみる。

TSum=8.5154907E7
RAve=0.5045794571786041

→一通りかけた。昨日時点と比べると明白

昨日TSum=9.0782776E7
RAve=0.34936781431246594

今日TSum=8.412922E7
RAve=0.5125584334338946

→提出。89,069,223,577、74位。本当にあがいてよかった。。。

やはり1手でどれだけ効率的に詰められるかが大事。
→逆転時、限界まででかいのじゃなくて、逆転した瞬間にbreakした方がいいのでは？
　→大正解

昨日TSum=9.0782776E7
RAve=0.30917109279642035

現在TSum=7.8555588E7
RAve=0.49607266801814054

これで4つセット交換するとよくなったりしないか？
→よくなったりならなかったり、全体では減った。とりあえずOFFで。

バッグのソートに二分探索入れる
→あまりよくならない。
→D>10の条件で使ったらあがった。
→Itemのソートにも使う？Item>20が一番よかった。

昨日TSum=9.0782776E7
RAve=0.2983328261961896

現在TSum=7.1599018E7
RAve=0.5070789370999276

→フルマージソートの条件も調整。Q<4.8*N*pow(D, 0.2)

あとは最後に複数交換考えるかー。
→比較の際、以前の自分より小さければOKというのがある。
　→ダメだった。
→複数交換、とりあえず2:2交換を書く
　→あがるやつもあるっぽい。

ラスサブ。暫定テストには該当ケースが無かったぽくて変わらず。

**TODO**
でかいやつからならす
~~→小さい集合を後入れ~~
→複数交換高度化
→過去結果の流用
→逆転許可

## 反省
時間そこそこ使えたのに大敗北。
ヒープにこだわったけど、ほとんど無駄になったのがツラい。
どの道勝ちに繋がるアイディアは思い浮かばなかったけど。
事前に上手くソートしたり、整合性の取れた状態を維持することでクエリを減らすより、
今わかっているクエリ結果から、柔軟に次のクエリを考えて情報量を増やすゲームだった？
みなさんの解法で勉強する。

ymatsuxさんより「Largest differencing method」がQが大きくて、D=2の時にいいやつらしい。
https://en.wikipedia.org/wiki/Largest_differencing_method


いんたくさんより、推定は10Nくらいあれば結構正確に個別のが求まるらしい。
他の方もおんなじこと言ってる。
一方、大小比較だけで差を詰めていくのも本質一緒の操作。
Largest differencing method はまさにそれ。

私の解法で明確に劣っているのが、Itemを4つ集合でまとめるとこ。
無理にItemの順序を出さず、都度都度得られる情報で補間すべきだった。

推定じゃない方針で、simanさんのがめっちゃ丁寧で勉強になる。
複数交換もランダム入れ替えで確かに良かった。
https://simanman.hatenablog.com/entry/2023/10/22/190146

どうせアルゴリズムの勉強するなら、こっちだった。。。どうして。。。

数分割問題：折角久保先生が宣伝してくださってるんで、一通りナメないとなぁ。
https://scmopt.github.io/opt100/76npp.html#FFD

マージ挿入ソート、やはり比較回数が有利？

トーナメントソートというものが存在。これマラソンでよく使えそう。
https://www.baeldung.com/cs/tournament-sort-algorithm