問題
問題文
未知の重さのグッズがたくさんあるので、天秤だけを使ってできるだけ公平に等分する
より正確には
の条件の下で N個のグッズをQ回以内の比較でD個に分けて、その分散の最小化をする。
また、グッズの重さは指数分布からランダムに決められる。
思いついた解法
数理計画法
大小関係の情報を条件として、分散最小化（LPに落とし込むなら平均との絶対値の差の合計最小化とかになる？）を目的関数としてうにゃうにゃやればできそう。 が、条件として聞く比較対象の決定がめんどくさそう & LPの自前実装が大変そう ということで却下
ベイズ最適化みたいななにがし
上と近いが、重さの分布が与えられてることなどを考えて、最尤推定みたいなことをやれば理論上最強 が、そんなことを器用にできる数学力があるわけはなく却下
貪欲
実装が楽なのでこれを採用（内容は後述）
最終解法
結局たいして時間は取れず、最低限の実装だけして終わった。
（Qに余裕があれば）ソートして大きい順に並び替え
↓
D個の袋を用意したうえで「現時点で最も軽い袋を算出し、そこにグッズを入れる」を最後まで繰り返す（これはheapqを使うと非常にシンプルに実装できる）
ソートにしてもheapqにしても自前実装がだるいなあと思っていが、演算子オーバーロードを使えばそのまま標準アルゴリズムが使えることに気づいて感動。
# 演算子オーバーロードを用いたソート（説明のため単純化）
class Item():
def __init__(self,n):
self.n=0
def __lt__(self,other):
print(f"1 1 {self.n} {other.n}")
res=input()
return res=="<"
def main():
L=[Item(i) for i in range(N)]
L.sort()
Qに余裕があるケースではそれなりにうまくいってるっぽい。
このあと、山登り的なのをためそうとしたがあっという間にサチってうまくいかず、306位（1523 perf）フィニッシュ