Kazun の競プロ記録

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

AtCoder Beginner Contest 227 B 問題 KEYENCE building

AtCoder ABC ABC227 B問題 200 pts

問題

提出解答

問題の概要

$N$ 個の正の整数 $S_1, \dots, S_N$ のうち, 正の整数 $a,b$ を用いて, $4ab+3a+3b$ と表せないのはいくつか?

制約

$1 \leq N \leq 20$
$1 \leq S_i \leq 1000$

解法

ある正の整数 $a,b$ が存在して, $S_i=4ab+3a+3b$ と表せるならば,

$S_i=4ab+3a+3b \geq 4a+3a=7a, \quad S_i=4ab+3a+3b \geq 4b+3b=7b$

で, 制約 $S_i \leq 1000$ から, $a,b \leq \frac{1000}{7}$ でなくてはならず, $a,b$ は整数であるから, $a,b \leq \left \lfloor \frac{1000}{7} \right \rfloor=142$ である.

よって, 集合 $U$ を

$U:=\{4ab+3a+3b \mid 1 \leq a,b \leq 142, a,b \in \mathbb{Z}\}$

として, $S_i \not \in U$ となる $i$ の個数を数えれば良い.