AtCoder Regular Contest 057 B : 高橋君ゲーム
当初の方針
- DP? →考えたDP:dp[N][K]
- Kが10^9ほどあるので無理
- 先頭から最小の勝利数で勝率が上がるような貪欲?
- 実装中に全部使い切らないと行けないケース
()でうまくいかない。
- 諦め
解法を読んで
のケースは特殊化して省く。
そうすることで、それ以外のケースで、
- 全く勝たない遷移と
- 最小の勝利数を獲得する遷移
をするDPになる。
余った勝利数は、後ろから消費することとして無視する
(これで勝率の上下には影響がない)。
たくさん余ったら、勝率が変化(上昇)するように思うが、
それは別の遷移ですでに同等のことが行われているので、
無視していい。
dp[N][i] != \inf を満たす最大のiが答えになる。
解説では、dp[N][i] <= K となるiだけど、
遷移が個人的に気持ち悪かったので、
あり得ない遷移(勝利数が試合数を超えたり、
勝利数がKを超えたりするもの)は省くことにした。
どっちがスマートに感じるかは個人の好み。
Submission #935724 - AtCoder Regular Contest 057 | AtCoder
それにしてもこの証明、頭がいいなあ。
自分で一からできる自信がない。
ちょっと補足。
次の試合で全部勝利すると、勝率は上がるのか。
確かに。
(a < bなのは、特殊化したことによって、少なくとも1回は負けているから)
こういうのが感覚で分からないと苦労するなあ。