nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume21 問題リンク Finding the Top RPS Player 概要 N人の人を集め、じゃんけんを行う。 N人は最初0勝である。ゲームは1ターンに同時に任意の数だけ試合が行われる。ただし、試合は連勝数の等しい人同士のみ行う事が出来る。k連勝同士の人が試合をすると勝った方がk+1連勝となり、負けた人は0勝に戻る。 M連勝する人が現れるための最小ターン数を答えよ。 2 1 解法 貪欲のようなシミュレートで解きました。 勝数が大きい人を1ターン中にたくさん作り出したいため、行える試合は全て行った方が得です。 c[M]: M連勝している人の人数 という表を作りながら1ターン毎に試合結果をシミュレート… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20120509%2F1336551537" title="AOJ2119 Finding the Top RPS Player - nanikakaのAOJ航海日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-05-09 17:18:57 rich https://nanikaka.hatenadiary.org/entry/20120509/1336551537 1.0 100%