GCJ2012 Round 1B Problem A. 解き方

Google Code Jam 2012 Round 1B
Problem A. Safety in Numbers 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

Googleさんが公開したAnalysisでは Binary Search という話が出てきていますが、「単独最下位にならなければいい」という話なのでもっと簡単だと思います。

N人の出場者に審判が付けた点数の合計が X で、それと同じだけの得点を観客の投票に応じて振り分けるので、全体（出場者の得点の合計）は X×2 点あります。

最下位にならないためには、この全体得点の平均点（つまり X×2÷N 点）を取ればよいはずです。

なぜ平均点か？

• みんなが同じ得点を取ると、全員1位で全員最下位です。最低得点が2人以上いるので失格にはなりません。平均点はこの「みんなが同じ得点」を取ったときの状態です。
• ひとりでも平均点より高い点数を取った人がいたら、必ず、1人以上平均点以下の人がいるはずです。自分が平均点を取っていれば最下位ではないので、失格になりません。
• 逆に自分が平均点より 0.1点でも低いと、ほかのみんなが平均点を取っていれば（1人だけ平均点+0.1点の人もいるはず）、自分が単独最下位で失格になってしまいます。

したがい、平均点こそが、単独最下位にならない最低限の得点なのです。

単独最下位にならない最低限の得点（平均点）を need とすると、

X = sum(s0,s1, ..., sn)
need = X * 2 / N
Yi = (need - si) / X 

という形で各出場者が獲得するべき票の割合を求めることができます。

ここまでは単純な話なのですが、審判からの採点だけで need を超えている出場者（例えばWさんとします）がいる場合がちょっとフクザツです。上記の式に当てはめると獲得するべき票の割合がマイナスになってしまいます。

この場合、その出場者（Wさん）は明らかに単独最下位にならないので獲得するべき票の割合は 0 とするのですが、残りの出場者に必要な最低限の得点も変わってきます。
具体的には観客の投票で変わる X 点を、Wさん以外で分け合って、その中で単独最下位にならない最低限の得点を求めることになります。

Xj = sum(s0,s1, ..., sn) - sw
Xa = sum(s0,s1, ..., sn)
need = (Xj + Xa) / (N - 1)
Yi = (need - si) / Xa 

Xj … Wさん以外が審判から採点された得点の合計

Xa … 観客からの投票で浮動する得点（Wさんも含めた審判が付けた得点の合計X）
という具合です。need は単純な平均点ではなく、Wさんに1票も入らない場合のWさん以外の平均点となります。

Wさんのように審判からの採点だけで平均点を超える人が複数いる場合も同様です。Xj で合計(X)から減算する採点が増え、最低限の得点を求める式の (N - 1) が (N - 2) などのようになります。