AGC066-B 解法 - とりゐのブログ

自分のコンテスト中の解法

$N=4$ の場合を考える．次のような数を考える： $5^0, 5^1, 5^2,5^3,5^4$ を並べる．ただし，お互いが干渉しないように適宜間に $0$ を追加する．

ここでは，間に $0$ を $10$ 個追加して $x=10000000000500000000002500000000001250000000000625$ とする．

このとき， $x,2x,4x,8x,16x$ は次のような振る舞いをする．

 10000000000500000000002500000000001250000000000625
 20000000001000000000005000000000002500000000001250
 40000000002000000000010000000000005000000000002500
 80000000004000000000020000000000010000000000005000
160000000008000000000040000000000020000000000010000

例えば $x$ から $2x$ への変化に注目すると， $x$ から $625$ を削除して，新たに $2$ を追加したものとみることができる．同様に， $2^{i-1} x$ から $2^{i}x$ への変化は $5^{5-i}$ を削除して新たに $2^{i}$ を追加したものとしてみることができる．したがって， $5^{5-i}$ の桁和が $2^{i}$ の桁和より大きくなっていればよい．

このままでは不十分だが，次のように問題を一般化してみる：

$5^{0}, 5^{1}, \ldots, 5^{M-1}$ の間に適宜 $0$ を追加した数を考える．このとき，各 $i=1,2,\ldots,N$ に対して $5^{M-i}$ の桁和が $2^{i}$ の桁和より大きくなっているか？

これを厳密に紙面上で判定するのは難しいが， $2^{i}$ がそこまで大きくない（せいぜい $10^{15}$ ぐらい）ため， $2^{i}$ の桁和も雑に見積もっても $15\cdot 9$ にしかなりえない．よって， $M$ を比較的大きめにとることで $5^{M-i}$ の桁数が増え，結果的に $5^{M-i}$ の桁和を $2^i$ の桁和よりも大きくすることが（期待）できる．

実際に，例えば $M=100$ ，間の $0$ の個数を $20$ 個（これで十分干渉しない）にすることで AC が得られた．