GCJ18 Round1B A. Rounding Error

問題

無数にあるプログラミング言語について、N人に、どの言語が好きか？を聞いた。
今、途中までの集計結果(C_1,...,C_L)が与えられている。
例として、「1 2」という集計結果は、3人に回答してもらっていて、言語1が好きといった人が1人、言語2が好きといった人が2人、を表す。

ところで、集計結果を報告したいが、パーセント表記で小数点以下を四捨五入したものを用いると、パーセントの合計が正確に100%にならない場合がある。
残りの人の回答によって、最終的なパーセントの合計が最大となる場合の合計値を答えよ。

制約

• 1 <= テストケース数 <= 100
• 1 <= 途中集計での言語の数L < 質問した人数N <= 10^5

解法

直感的に期待されるのは、ある言語xがパーセント表記にすると四捨五入で切り捨てられていたところ、残りの人がそこに投票することで四捨五入が切り上げられるように変わって、最終的な合計値が増えること。

現在の投票数で四捨五入が切り捨てになっているか、切り上げになっているかは、「(100*x)%Nが、ceil(N/2)以上かどうか」で求められる。
ある言語xに、残りの人のうち1人が投票するということは、この「(100*x)%N」のxを1増やすということで、「100%N」だけ増える。

したがって、y=(100*x)%Nとして、0～N-1までのすべてのyについて、ceil(N/2)以上になるまでに何回「100%N」を足せばよいかをメモ化dfsなどで求めておけば、与えられた途中集計結果のうち、加える数が少なくceil(N/2)以上になるものから必要な分を貪欲に投票していけばよい。
すでに切りあがっているものは無視。最終的に余る場合は、ceil(N/2)以上になるように新たな言語に投票していけばよい。
ただし、「100%N」が0になる場合は、どう操作しても変化させられないことに注意。

部分点解法

• N<=25の場合
  • 分割数を考えると、N=25でも1958通りしかないので、全パターン列挙して条件を満たすものについて計算できる
• N<=250の場合
  • 「dp[a][b] := a個の分割(x_1,...,x_a)において、合計がb、かつ、x_i >= C_iを満たすとき、小数点以下を四捨五入したパーセント合計値の最大値」を考えると、dp[N][N]が答え。計算量はO(N^3)