Kazun の競プロ記録

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

AtCoder Beginner Contest 230 C 問題 X drawing

AtCoder ABC ABC230 C問題 300 pts

問題

提出解答

問題の概要

$N \times N$ のマス目があり, 最初は全て白マスである. $A,B$ が固定されており, 以下の操作を行う.

(操作1) $\max(1-A,1-B) \leq k \leq \min(N-A,N-B)$ を満たす全ての整数 $k$ に対して, マス $(A+k,B+k)$ を黒く塗る.
(操作2) $\max(1-A,B-N) \leq k \leq \min(N-A,B-1)$ を満たす全ての整数 $k$ に対して, マス $(A+k,B-k)$ を黒く塗る.

$P \leq i \leq Q, R \leq j \leq S$ を満たす全ての整数 $(i,j)$ に対して, マス $(i,j)$ の色を答えよ.

制約

$1 \leq N \leq 10^{18}$
$1 \leq A,B \leq N$
$1 \leq P \leq Q \leq N$
$1 \leq R \leq S \leq N$
$(Q-P+1)(S-R+1) \leq 3 \times 10^5$

解法

答えるべきマスの数は $(Q-P+1)(S-R+1)$ で, 制約から $3 \times 10^5$ が保証されているので, 1マスずつ条件を満たすかどうかを確認すれば良い.

マス $(i,j)$ が黒かどうかを判定する. (操作 1) で黒に塗られるかを判定する. (操作1) における条件を満たす整数 $k$ が存在することと, 以下は同値である.

$i-A=j-B ~\textrm{かつ} \max(1-A,1-B) \leq i-A \leq \min(N-A,N-B)$

証明 (クリックで表示, 非表示切り替え)

一方で (操作2) における条件を満たす整数 $k$ が存在することと, 以下は同値である.

$i-A=B-j ~\textrm{かつ} \max(1-A,B-N) \leq i-A \leq \min(N-A,B-1)$

よって, 判定すべきマスそれぞれについて, 上の2つの条件のうち, 少なくとも一方を満たせば黒であり, そうでなければ白である. よって, 判定すべきマスの数を $X:=(Q-P+1)(S-R+1)$ としたとき, 各マスの判定のための計算量が $O(1)$ なので, 全体での計算量として $O(X)$ で解答できる.