Kazun の競プロ記録

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

AtCoder Beginner Contest 225 C 問題 Calendar Validator

AtCoder ABC ABC225 C問題 300 pts

問題

提出解答

問題の概要

$10^{100}$ 行 $7$ 列からなる行列 $A$ が与えられる. $A$ の $i$ 行 $j$ 列の要素は $7(i-1)+j$ である.

$N$ 行 $M$ 列の行列 $B$ が与えられるが, $B$ は $A$ から回転せずにある長方形で切り取った部分か?

制約

$1 \leq N \leq 10^4$
$1 \leq M \leq 7$
$1 \leq B_{i,j} \leq 10^9$

解法

$A$ において, $a~(1 \leq a \leq 7 \times 10^{100}-7)$ が書かれているのは, $q,r$ を $a-1$ を $7$ で割った商と余りとして, $q$ 行目 $r+1$ 列目である.

また, $A$ の要素は全て異なることから, $B_{1,1}$ を見れば, 存在する場合にどこから取り出したものがが一意にさだまる. 後は各要素について, 要素が一致するかどうかを見れば良い.

ただし, 7の倍数 $p$ において, $p,p+1$ は $A$ において異なる行にある整数であることに注意すること.