数列をうまくつくることで,数列から3個以下の数を選んで以下の任意の数をつくれるようにせよという問題
が最大値であるときに解となる数列さえ求めれば,この数列を使って以下の任意の数がつくれるのでを満たす任意のに対する解にもなっていることがわかる. よって,の場合の解を求めることに注力すれば良い.
与えられた数をいくつかの数の和に分解したいので,このために都合の良い表示を考えたい. このときに桁を分けて考えるというのが有効な考え方になる. 例えば,適当にという数を考えると, や, のように桁が独立している数どうしの足し算は考えやすい.
未満の数は10進で6桁の数として表せるので,2桁ずつに分解して各グループについてからまですべての数をつくれば,各グループから1つずつ数を選んで組み合わせることで6桁以下の任意の数を表現できる.(は 0 であり,そのグループからは数を選ばないということによって表現できるので,明示的につくる必要はない)
最後に,という数だけは7桁なのでこれだけ別に数列に加える. 以上で任意の数を構成できた.
実装例
備考
もちろん10進ではなく2進表示などでも原理的にはよいのだが,たとえば2進で以下の数を表現しようとすると20桁いる. 7桁,7桁,6桁に分けて各グループについてすべての数をつくると,程度の数が必要になるので制約を満たさない. 今回は上限がという10進できりの良い数になっているので10進表示で考えるのが一番無駄がないということだろう.