Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 222 C問題 Swiss-System Tournament

AtCoder ABC ABC222 C問題 300 pts

問題

提出解答

問題の概要

$2N$ 人が参加するじゃんけん大会が開催された. 大会は以下のようにして進行される.

第 $i$ ラウンド第 $k$ 回戦では, 第 $(i-1)$ ラウンド終了時の $2k-1$ 位と, $2k$ 位の人が戦う.
第ラウンドの第回戦を終えた後, 以下のようにして, 第ラウンド終了時の順位を決める.
- 勝利数が多い順. ただし, 勝利数が同じ人同士は, 番号が小さい方が上位

第 $M$ ラウンド終了時のランキングを求めよ. ただし, 全ての選手の各ラウンドで出す手は判明している.

制約

$1 \leq N \leq 50$
$1 \leq M \leq 100$

解法

$N,M$ が小さいので, 愚直シミュレーションでも間に合う. 具体的には以下のようにすればよい. 以下, $A_{i,j}$ で選手 $i$ が第 $j$ ラウンドで出す手とする.

ここで, 関数 ${\tt result}(\alpha, \beta)$ を

${\tt result}(\alpha, \beta):=\begin{cases} 1 & (\alpha の勝ち) \\ -1 & (\beta の勝ち) \\ 0 & (引き分け) \end{cases}$

とする. そして $R_{i,a}$ で, 第 $i$ ラウンド終了時に, $a$ 位の人の番号とする.

$R_{0,1}=1, R_{0,2}=2, \dots, R_{0,a}=a, \dots, R_{0,2N}=2N$ である.
$i=1,2, \cdots, M$ の順に以下を行う.
の順に, 以下を行う.
- ${\tt result}(A_{i, R_{i-1, 2k-1}}, A_{i, R_{i-1, 2k}})=1$ ならば, 人 $R_{i,2k-1}$ の勝利数を $1$ 加算する.
- ${\tt result}(A_{i, R_{i-1, 2k-1}}, A_{i, R_{i-1, 2k}})=-1$ ならば, 人 $R_{i,2k}$ の勝利数を $1$ 加算する.
勝利数と番号を基に, $R_{i,a}$ を構成する. 具体的には, 人 $p$ の勝利数を $W_p$ としたとき, 長さ $2N$ のタプルのリスト

$\mathcal{L}=[(-W_1, 1), (-W_2, 2), \cdots (-W_{2N}, 2N)]$

を辞書式の意味で降順にソートしたものを $\mathcal{L}'=[(w_1, t_1), \dots, (w_{2N}, t_{2N})$ ] としたとき, $R_{i,a}=t_a$ である.

この愚直シミュレーションの計算量は $O(MN \log N)$ であり, 十分高速である.