Kazun の競プロ記録

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

AtCoder Beginner Contest 269 B問題 Rectangle Detection

AtCoder ABC269 ABC B問題 200 pts

問題

提出解答

(解法 1) atcoder.jp

(解法 2) atcoder.jp

問題の概要

次のようにして $10$ 個の文字列 $S_1, \dots, S_{10}$ を生成した.

$i=1,2, \dots, 10$ に対して, $S_i={\tt ..........}$ とする.
次を満たす4個の整数をそれぞれを選ぶ.
- $1 \leq A \leq B \leq 10$
- $1 \leq C \leq D \leq 10$
$A \leq i \leq B, C \leq j \leq D$ を満たす全ての整数の組 $(i,j)$ に対して, $S_i$ の $j$ 文字目を ${\tt \#}$ に置き換える.

完成後の $S_1, \dots, S_{10}$ が与えられるので, $A,B,C,D$ を特定せよ.

制約

$S_1, \dots, S_{10}$ は問題文に記載の方法で生成され得る文字列.

解法1

$1 \leq A \leq B \leq 10, 1 \leq C \leq D \leq 10$ を満たす整数の組 $(A,B,C,D)$ の数は $55 \times 55=3025$ 通りに限られ, 各パターンにおける検証もマスの数に比例する時間で可能である. よって, $L:=10$ として $L^6$ くらいの計算量で計算できる.

解法2

$\mathcal{I}:=\{(i,j) \mid 1 \leq i \leq 10, 1 \leq j \leq 10, S_i[j]={\tt \#} \}$ とする. このとき,

$\displaystyle A=\min_{(i,j) \in \mathcal{I}} i, \quad B=\max_{(i,j) \in \mathcal{I}} i, \quad, C=\min_{(i,j) \in \mathcal{I}} j, \quad D=\max_{(i,j) \in \mathcal{I}} j$

である. なお, $\mathcal{I}$ に辞書式順序を導入することにより,

$(A,B)=\min \mathcal{I}, \quad (C,D)=\max \mathcal{I}$

ともなる.