GCJ 2012 Round 1B
通りませんでした。それはいいとして、A問題の二分探索手法。
A問題の概要
数値列S[1..N]が与えられる。これらに対してXをSの合計とする。
ここでP[i] = S[i] + X * Y[i]の式から各iの点数P[i]を計算する。ただしsum Y[1..N] == 1.0
このとき各iに対して他のY[j]がどのようであってもP[i] >= min(P[j])を満たすようなY[i]の下限を求めよ。
どうやって解いたか
P[j]の最小値を最大化するのはi!=jが成り立つjに対してP[j]を等しくすること。
で、なるべく等しくするように求めるんだけど、値が違いすぎると等しくできないので、その時は高い点数のやつを省いてこれを繰り返す云々。
この解放を思いつくのに1時間+2WA orz
二分探索
こういう問題は二分探索だ！ただ、二分探索する以上は「もっと簡単な合否判定」をしたい。
合否判定
二分探索なので具体的なY[i]は与えられている。
これに対してP[j]の最小値を最大化するには簡単で、T[1..N-1]=S[1..N/i]を昇順にソートしておいて、なるべく下の方の奴らの点数が同じになるようにレートを配分していく。
この解法を思いついてからのバグ数
- まず合否判定をきっちり思いつかない。これはいいとしよう。
- あれ、N==2の時は動かない、手で直そう。
- レートを使い切る場合しか考慮していなかった。例えば、みんな点数が25 25 25 25のような場合に関しては点数を同じにするフェーズでは点が変わらない。最後に余ったレートを全員に配分する必要がある。で、さっきのN==2は点数を等しくするフェーズがなかったからこれの部分集合だったわけだ。
- …というのを実装したと思ったら、今度はレートを使い切った場合にもレートを2重に全員に配分してしまっていた。レート=0という代入を忘れていたわけだ。
- ここまでやってなんで合わないんだ…あ、high-low < 1e-6ってあるけど精度足りない…？1e-8にしてみよう。
これでようやく正解。あまりにもバグが多いし、正解を見ながらデバッグしているわけで本番には全く対処できない。クソだなぁ。
他の問題
B問題は（問題文はだるいが）ただの二次元グリッド上のダイクストラだったが、制限時間中はなぜか「道は左上から右上にしか進まない」という仮定をおいて死亡。ぐるっと回ることもあるので、そんな仮定は置いちゃ駄目。
C問題は数の集合に対して異なる部分集合が同じ和になるかを答える問題。
smallは総当たりで各部分和を計算して計算結果を保存すればいい。
乱択のやり方が結構人によって違って面白いなぁ。自分はランダムに26個くらい取ってきて半分全列挙かなぁ、と思っていた。20個くらい取ってきちゃって和だけでやる人もいるのね
