Kazun の競プロ記録

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

AtCoder Beginner Contest 251 B問題 At Most 3 (Judge ver.)

AtCoder ABC ABC251 B問題 200 pts

問題

提出解答

問題の概要

$W$ 以下の正の整数 $n$ のうち, 以下を満たすのはいくつか?

$A_1, \dots, A_N$ から異なる要素 (同じ整数でも場所が異なっていれば可) $3$ 個以下を取り出して, その和が $n$ .

制約

$1 \leq N \leq 300$
$1 \leq W \leq 10^6$
$1 \leq A_i \leq 10^6$

解法

要素の選び方は高々 $N^3$ 通りである. 今, $N \leq 300$ であるから, $N^3 \leq 3 \times 10^7$ である. よって, 愚直に計算しても間に合う.

ここで, 実装について, 長さ $N+2$ の列 $B=(B_i)$ を

$B_i=\begin{cases} A_i & (i=1,2, \dots, N) \\ 0 & (i=N+1, N+2) \end{cases}$

として, $B$ から異なる $3$ 要素を選ぶということにすると, $A$ における $3$ 要素以下の選び方を漏れなく列挙できる ( $B_{N+1}, B_{N+2}$ の選択が $A$ においては選ばないと同一視できる).