Kazun の競プロ記録

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

AtCoder Beginner Contest 261 B問題 Tournament Result

AtCoder ABC ABC261 B問題 200 pts

問題

提出解答

問題の概要

$N$ 人による総当り戦の結果が与えられる. この結果は矛盾していないか? ただし, 結果は $A_{i,j}$ で表され.

$i=j$ のときは $A_{i,j}={\tt -}$ である.
$i \neq j$ で, $A_{i,j}={\tt W}$ のとき, 人 $i$ は人 $j$ に勝ったことを意味する.
$i \neq j$ で, $A_{i,j}={\tt L}$ のとき, 人 $i$ は人 $j$ に負けたことを意味する.
$i \neq j$ で, $A_{i,j}={\tt D}$ のとき, 人 $i$ は人 $j$ に引き分けたことを意味する.

制約

$2 \leq N \leq 1000$
$i=j$ ならば, $A_{i,i}={\tt -}$
$i \neq j$ ならば, $A_{i,j}$ は ${\tt W}, {\tt L}, {\tt D}$ のいずれか.

解法

$N \leq 1000$ なので, 各対戦について矛盾が無いかを見ればよい. 厳密には, 全ての $1 \leq i,j \leq N~(i \neq j)$ に対して以下のうちのうちのどれか1つが成り立つかどうかを判定すれば良い.

$A_{i,j}={\tt W}, A_{j,i}={\tt L}$
$A_{i,j}={\tt L}, A_{j,i}={\tt W}$
$A_{i,j}={\tt D}, A_{j,i}={\tt D}$

計算量も $O(N^2)$ 時間で判定できる.