Kazun の競プロ記録

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

AtCoder Beginner Contest 303 B問題 Discord

AtCoder ABC ABC303 B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 人の人が横一列に並んだ写真を $M$ 枚撮った.

$i$ 枚目の写真において, 左から $j$ 番目の人は人 $a_{i,j}$ である.

$N$ 人から異なる $2$ 人を選ぶ方法のうち, $M$ 枚の写真で $1$ 枚も隣同士になっていないような選び方は何通りか?

制約

$2 \leq N \leq 50$
$1 \leq M \leq 50$
$a_{i,1}, \dots, a_{i,N}$ は $1,2, \dots, N$ の並び替え

解法

$N \times N$ の配列を隣同士になったことがあるかどうかを記録する配列として用意し, 各写真について, 隣同士になっているペアについて配列に記録し, 最終的に記録がつかなかったペアの数を答えれば良い.

なお, $N$ 人から異なる $2$ 人を選ぶ方法について, 順番は考慮しないので, 注意する.