ARC046A ゾロ目数

問題

https://atcoder.jp/contests/arc046/tasks/arc046_a

方針

まず、ゾロ目数を列挙してどのような法則に従っているかを考察する

# N=20までのゾロ目数
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222]

どうやら、ゾロ目数に使われる数字は1~9までの9文字で周期が9であることがわかる

# ゾロ目数に使われる数字
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

この数列Bをどの様に作るか考えてみる。周期が9であるので9による剰余が関わってきそうだ。

>>> C = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
>>> [ c%9 for c in C ]
[1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2]

これだけではBを作ることはできない。周期は9となっているが、使われている数字が19ではなく08となってしまっている。つまりこの数列に1を足せば良い。

>>> [ c%9+1 for c in C ]
[2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3]

今度は数列の始めがすれてしまった。これを修正するのは簡単で、9の剰余を取る前に1を引けば良い（数列全体が右にシフトするイメージ）

>>> [ (c-1)%9+1 for c in C ]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2]

これで所望の数列Bが完成した。

あとは、数列Aの各項の桁数を表現できれば良い

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 111, 222]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3]

これまた、周期が9であるので9による剰余が関わってきそうだ。

>>> [ c//9 for c in C ]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

1を足す。

>>> [ (c)//9+1 for c in C ]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]]

シフトする。

>>> [ (c-1)//9+1 for c in C ]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3]

これで数列Aの各項の桁数を表現できた。

Pythonは文字列に整数をかけることで、与えられた文字列を繰り返す文字列を生成できる。

>>> 'A' * 3
'AAA'

つまり、ここまでで数列の各要素に使われている数と桁数を求めることができたので、これらを以下の様に組み合わせることで、所望の数列が得られる

>>> [ str((c-1)%9+1) * ((c-1)//9+1) for c in C ]
['1', '2', '3', '4', '5', '6', '7', '8', '9', '11', '22', '33', '44', '55', '66', '77', '88', '99', '111', '222']

問題では数列を求める必要はなく、与えられたNに対する要素だけを求めれば良い

コード

N = int(input())
print (str((N-1) % 9 + 1) * ((N-1) // 9 + 1))

その他の解法

1から数を1ずつ増やしていき、ゾロ目数かどうかを確認していくだけでも解ける。Nが最大で50なので計算時間的にも問題はない。