AtCoder Regular Contest 057 B : 高橋君ゲーム

arc057.contest.atcoder.jp

当初の方針

DP？　→考えたDP:dp[N][K]

Kが10^9ほどあるので無理

先頭から最小の勝利数で勝率が上がるような貪欲？

実装中に全部使い切らないと行けないケース

（ $\sum a_i = K$ ）でうまくいかない。

諦め

解法を読んで

$\sum a_i = K$ のケースは特殊化して省く。

そうすることで、それ以外のケースで、

全く勝たない遷移と
最小の勝利数を獲得する遷移

をするDPになる。

余った勝利数は、後ろから消費することとして無視する
（これで勝率の上下には影響がない）。

たくさん余ったら、勝率が変化（上昇）するように思うが、
それは別の遷移ですでに同等のことが行われているので、
無視していい。

$\begin{eqnarray} dp[i][j] &:=& i日までにj回勝率が上昇した場合の \\ &&勝利数の最小値 \end{eqnarray}$

dp[N][i] != \inf を満たす最大のiが答えになる。

解説では、dp[N][i] <= K となるiだけど、
遷移が個人的に気持ち悪かったので、
あり得ない遷移（勝利数が試合数を超えたり、
勝利数がKを超えたりするもの）は省くことにした。

どっちがスマートに感じるかは個人の好み。

Submission #935724 - AtCoder Regular Contest 057 | AtCoder

それにしてもこの証明、頭がいいなあ。

自分で一からできる自信がない。

ちょっと補足。

次の試合で全部勝利すると、勝率は上がるのか。

$\begin{cases} \frac{a}{b} &(a < b)\\ \frac{a+c}{b+c} & \end{cases}$

$\begin{eqnarray} \frac{a+c}{b+c}-\frac{a}{b} &=& \frac{b(a+c)}{b(b+c)} - \frac{a(b+c)}{b(b+c)} \\ &=& \frac{ab + bc - (ab + ac)}{b(b+c)} \\ &=& \frac{c(b-a)}{b(b+c)} > 0 \end{eqnarray}$

確かに。
(a < bなのは、特殊化したことによって、少なくとも1回は負けているから)

こういうのが感覚で分からないと苦労するなあ。