はじめに：構築(構成)とは？

この問題のような「条件を満たすものを構築して出力せよ」という問いからなる問題は、構築/構成 (constructive problem) というジャンル名で呼ばれています。構築問題はある種の閃きを要求する問題なので、通常の問題との違いに戸惑った方もいるかもしれませんし、逆にパズルに慣れている人はいつもより解きやすく感じたのではないかと思います。

ここではいくつかのヒントを載せた後に答えを提示する形式で解説していきます。

ヒント 1 : \(N\) 進法 (位取り記数法) の知識

\(N\) 進法とは数を表現する方法の一種です。特に \(10\) 進法は我々の日常生活で、 \(2\) 進法や \(16\) 進法はプログラミングの世界で広く用いられています。
ある整数の値 \(n\) を \(N\) 進法で表記する方法を説明します。\(n\) は \(0\) 以上 \(N-1\) 以下の整数列 \((a_0,a_1,\dots,a_r)\) を用いて以下のように一意に表現できます。

\[n = a_r N^r + \dots + a_2 N^2 + a_1 N + a_0\]

これを

\[a_ra_{r-1} \dots a_2a_1a_0\]

というように繋げて並べたものが \(N\) 進数を用いた表記になります。これを \(N\) 進表記と呼びます。

• 我々が普段使っている \(10\) 進法では \(N^0,N^1,N^2,N^3,\dots\) が \(1,10,100,1000,\dots\) に対応している、と考えるとわかりやすいと思います。

例えば \(10\) 進表記で \(251\) と表される数を \(7\) 進表記に直してみましょう。\(251\) は次のように表せます。

\[251 = 5 \times 7^2 + 0 \times 7 + 6\]

よって \(251\) の \(7\) 進表記は \(506\) になります。

一般に、\(1\) 桁以上 \(d\) 桁以下の \(p\) 進表記を用いると \(p^d - 1\) 以下のすべての非負整数を表現することができます。例えば \(10\) 進法では、\(10^4-1 = 9999\) 以下の非負整数は \(4\) 桁以下の \(10\) 進表記で表すことができます。

こうした \(N\) 進法の知識がこの問題を解く大きなヒントになります。

ヒント 2 : \(W = 999\) の場合の解法は？

上で説明した \(N\) 進数の概念を踏まえながら、\(W=999\) の場合の答えを \(10\) 進数を用いて解いてみましょう。
\(10^3 - 1 = 999\) 以下の整数 \(n\) は \(0\) 以上 \(9\) 以下の整数 \(a,b,c\) を用いて

\[n = a \times 10^2 + b \times 10 + c\]

と表すことができます。そこで、\(a \times 10^2,b \times 10 ,c\) の \(3\) つに対応する以下の \(27\) 個の数を重さとするおもりを準備してみましょう。

• \(1,2,3,4,5,6,7,8,9\)
• \(10,20,30,40,50,60,70,80,90\)
• \(100,200,300,400,500,600,700,800,900\)

実はこの \(27\) 個のおもりの集合は \(W=999\) のときの答えになっています。
実際に確認していきましょう。例えば \(n=251\) の場合、

\[251 = 2 \times 10^2 + 5 \times 10 + 1\]

と表せるので、重さ \(200, 50, 1\) の 3 個のおもりを使えば和が \(251\) になります。

また、\(n = 401\) の場合は

\[401 = 4 \times 10^2 + 0 \times 10 + 1\]

です。この場合は \(10\) の位に対応するおもりは不要で、重さ \(400\) のおもりと重さ \(1\) のおもりの \(2\) 個のおもりを使えば和を \(401\) にできます。

一般に \(1 \leq n \leq 999\) で説明すると、

\[n = a \times 10^2 + b \times 10 + c\]

としたとき、

• \(1 \leq a\) の場合は重さ \(a \times 100\) のおもりを選ぶ
• \(1 \leq b\) の場合は重さ \(b \times 10\) のおもりを選ぶ
• \(1 \leq c\) の場合は重さ \(c \times 1\) のおもりを選ぶ

とすれば \(3\) 個以下のおもりの重さの和で \(n\) を作ることができます。
よって \(W=999\) の場合は \(27\) 個のおもりで解くことができました。これを応用すると \(W=10^6\) の場合も解くことができます。

ヒント 3 : \(W = 10^6\) の場合が解ければよい

実はこの問題は、入力に関係なく \(W = 10^6\) である場合を解いて出力すればよいです。なぜならば、\(W=10^6\) で正答になる出力は「 \(1 \leq n \leq 10^6\) をみたす整数 \(n\) はすべて良い整数である」という条件を満たしているので、\(W < 10^6\) の場合でも良い整数に関する条件を満たす出力になっているからです。

解法

ここまで読んでみて「ヒントがそろったので残りは自分で考えてみたい！」という方のために、答えは以下のタブの内部に隠しておきます。

(ここを押すと解法が表示されます)

• $1,2,3\dots,98,99$
• $100,200,300,\dots,9800,9900$
• $10^4,2\times 10^4,3\times 10^4,\dots,98\times 10^4,99\times 10^4$

の計 \(297\) 個のおもりを用意すれば常に条件を満たします。

(証明) \(1 \leq n \leq 10^6\) を満たすすべての整数が良い整数であることを証明できればよいです。
\(1 \leq n \leq 10^6-1\) と \(n=10^6\) に分けて説明します。

(1) \(1 \leq n \leq 10^6-1\) の場合
\(999999 = 10^6 -1\) 以下の正整数 \(n\) は \(0\) 以上 \(99\) 以下の整数 \(a,b,c\) を用いて

\[n = a \times (10^2)^2 + b \times 10^2 + c\]

と表せるので、\(W=999\) の場合と同様に以下のようにおもりを用意すれば \(3\) 個以下のおもりを選んで重さの和を \(n\) にすることができます。 よって \(n\) は良い整数です。

• $1 \leq a$ の場合は重さ $a \times 10^4$ のおもりを選ぶ
• $1 \leq b$ の場合は重さ $b \times 100$ のおもりを選ぶ
• $1 \leq c$ の場合は重さ $c \times 1$ のおもりを選ぶ

(2) \(n=10^6\) の場合
\(10^6\) は重さ \(99 \times 10^4\) のおもりと重さ \(10^4\) のおもりを組み合わせれば作ることができます。よって \(n\) は良い整数です。
実装例, C++