問題
正の整数を順に書き並べると 123456789101112131415... となります。位置 1 は 1、位置 10 は 10 の 1、位置 11 は 10 の 0 です。指定された各位置の数字を求めてください。位置は文字列として実際に作れる範囲をはるかに超えるので、同じ桁数の数のまとまり(1桁の数が9個、2桁の数が90個、3桁の数が900個、...)を丸ごと飛ばしましょう。
champernowne_digits(positions) を実装してください。
入力
positions:数字の列における位置(1 から数えます)のリスト。
出力
各位置の数字を、入力と同じ順に返してください。入力が空なら空のリストを返します。
制約
0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15
例
入力:
positions = [1, 9, 10, 11]
期待される出力:
expected = [1, 9, 1, 0]
入力:
std::vector<long long> positions = {1, 9, 10, 11};
期待される出力:
std::vector<long long> expected = {1, 9, 1, 0};
入力:
long[] positions = new long[] {1, 9, 10, 11};
期待される出力:
long[] expected = new long[] {1, 9, 1, 0};
解説
文字列は 1 2 3 4 5 6 7 8 9 1 0 1 1 と始まるので、数字は [1, 9, 1, 0] です。
入力:
positions = [15, 190]
期待される出力:
expected = [2, 1]
入力:
std::vector<long long> positions = {15, 190};
期待される出力:
std::vector<long long> expected = {2, 1};
入力:
long[] positions = new long[] {15, 190};
期待される出力:
long[] expected = new long[] {2, 1};
解説
位置 15 は 12 の 2 です。位置 10 から 189 には 10 から 99 が並ぶので、190 は 100 の最初の数字です。答えは [2, 1] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
d 桁の数は、全部で 9 × 10^(d − 1) × d 個の位置を占めます。
ヒント 2
位置があるまとまりの中に入るまで、まとまりごと引いていきます。
ヒント 3
まとまりの中では、(position − 1) / d でどの数か、(position − 1) % d でどの桁かがわかります。
目安の計算量
時間 O(m × log P)(m は位置の個数)、追加メモリ O(m)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。