Kazun の競プロ記録

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

AtCoder Beginner Contest 251 D問題 At Most 3 (Contestant ver.)

AtCoder ABC ABC251 C問題 300 pts

問題

提出解答

問題の概要

次を満たす正の整数列 $A=(A_i)_{i=1}^N$ を一つ構成せよ.

$N \leq 300$
$1 \leq A_i \leq 10^6 \quad (i=1,2, \dots, N)$
以上以下の全ての整数に対して, 以下が成立する.
- $A$ から異なる要素を高々 $3$ 個選び, その和を $n$ にすることができる.

制約

$1 \leq W \leq 10^6$

解法

$W=10^6$ の場合の $A$ を構成できればよいので, $W=10^6$ とする.

結論から言うと, $A$ は

$B=(i \times 100^j)_{\substack{i=1,2, \dots, 99 \\ j=0,1,2}}$

として, 適当に添字を $1$ 次元に直した列を $A$ をすればよい.

実際, $n \lt 10^6$ のとき, $n$ の $10$ 進数表記を上から $2$ 桁ずつ区切り, 各区切りに対応する項を採用すれば良い ( $00$ のときは選ばないを採用する). (例: $123456 \to 12|34|56 \to 120000+3400+56$ )

$n=10^6$ のとき, $10000+990000=10^6$ である.

$N$ の長さは $99 \times 3=297$ であるからこの $A$ が答えになる.