koba-e964 https://blog.hatena.ne.jp/koba-e964/ koba-e964の日記 https://koba-e964.hatenablog.com/ まあ基本だよね。 No.753 最強王者決定戦 - yukicoder 問題 16人の人間がいる。この16人を一列に並べて順番に組を作ってトーナメントを行ったとき、並べ方に応じて優勝者がただ一人決まる。全てのペアについて、戦ったときどちらが勝つかは決まっている。16!通りの並べ方全てについて優勝者を求めたとき、各人が何回優勝するかを計算せよ。 解法 DPで解く。DPテーブルは以下のようにする。 DP[i][S]: 集合Sの中の人が全員戦った時に人iが優勝する場合の数。ただし、組み方が同じで人の並べ方だけが違うものは同一視する。 (|S|は2べきのみを取り得ることに注意。) DPの遷移はDP[i… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkoba-e964.hatenablog.com%2Fentry%2F2018%2F12%2F20%2F003852" title="yukicoder No.753 最強王者決定戦 - koba-e964の日記" 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 2018-12-20 00:38:52 rich https://koba-e964.hatenablog.com/entry/2018/12/20/003852 1.0 100%