すべてのチャレンジ
中級 0件解決済み 正答率0%

チャンパーノウン定数の桁

正の整数を順に書き並べた文字列 123456789101112... の、指定された位置の数字を求めます。

このチャレンジで学べること

  • 各桁数の数が使う桁の総数を数えられる
  • 位置から対応する数とその桁を特定できる
  • 64ビット演算を安全に使える

問題

原文(英語)を表示

正の整数を順に書き並べると 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

例

例 1
入力:
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] です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。