ガジェット通信 GetNews

見たことのないものを見に行こう
「ジャスティス・リーグ」特集サイト

数学の問題をプログラミングで解こう!「カウント・スリー」問題解説

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

自然数を 1 から順に書き並べていきます。
このとき、3 の数字が現れる回数を数えます。

自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。

例えば F(10)=35 です。
下の通り、10 個目の 3 は、35 を書いているときに現れます。

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, …

同様に、F(3)=23, F(7)=33, F(8)=33, F(1000)=3081 となることが確かめられます。
(「33」には 3 が 2 回現れるため、それぞれの 3 を別々に数える点に注意してください。)

標準入力から、自然数 n (1 ≦ n ≦ 1012)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針:問題を逆方向にとらえよう

自然数を順に書いていったときの 3 の出現回数に関する問題です。n の上限が 1012 と非常に大きいので、3 をひとつひとつ数えていくようなアプローチではうまくいかないことは想像ついたと思います。

本問では、問題文を逆方向にとらえてみましょう。「n 個目の 3 がいつ現れるか?」を考える代わりに、自然数 k に対し「1 から k の間に 3 は何回現れるか?」を考えるのです。そのような回数を G(k) とおきます。すると本問は「G(k) が初めて n 以上となる k はいくつか?」と読み替えることができます。

F(n) を高速にもとめることは難しいですが、G(k) ならなんとかなります。そこで以下では、まず G(k) を高速に求めるコードを考えます。

1 から k の間に現れる 3 の回数はどうすれば求められるでしょうか。もちろん、1 から k までループを回すようなコードでは時間がかかりすぎて本末転倒です。そこでここでは、「3 の現れる位置で分けて考える」ことがポイントになります。つまり「各位ごとの 3 の出現回数」を考えるのです。

例えば一の位です。1 から k の間で、一の位に 3 は何回現れるでしょうか? 10 回に一度 3 が現れるのですから、例えば k=12345 という数を例にすると、k を 10 で割った商の 1234 回と、さらに k の一の位が 3 以上のときはもうプラス 1 で、計 1235 回の 3 が現れます。

それより大きな桁では、いくらか考察が複雑になります。実際にノートに数字を書いていってみると見えてきます。例えば百(=102)の位を考えます。百の位には、300~399、1300~1399 のように、3 が 100 個連続で現れます。k=12345 を例にすると、このような 100 個連続のかたまりは、k を 1000 で割った商の 12 回現れます。さらに k の百の位が 3 の場合は、12300~12345 の計 46 回がプラスされます。

あるいは、もし k=12245 のように百の位が 2 以下の場合は、プラスはありません。k=12445 のように百の位が 4 以上の場合は、12300~12399 の 100 回をプラスします。

数学の問題をプログラミングで解こう!「カウント・スリー」問題解説

このように、各位の数字に応じた場合分けをしながら、各位の 3 の出現回数を計算できます。G(k) を求める関数(Python)を以下に示します。ループを回すごとに 1, 10, 100, … と増えていく変数 t をつかって、連続で現れる 3 の個数を数えています。

def g(k):
c, t = 0, 1
while k > t:
c += t*(k/(10*t))
d = (k/t)%10
if d == 3: c += k%t + 1
elif d > 3: c += t
t *= 10
return c

二分探索で高速にサーチ!

さてこれで、k 以下の自然数に現れる 3 の個数を高速に求められるようになりました。残るは、n に対し G(k) が初めて n 以上となる k を探すことです。

効率よく k を探すために、二分探索のテクニックが有用です。基本的なアイデアは下記の Wikipedia の記事を参照してください。二分探索を行うには対象のデータがソートされている必要があります。G(k) は k に対し単調増加の関数ですので、ちょうどこのアルゴリズムを適用できます。(参考:数学の問題をプログラミングで解こう!「ロング・ロング・ストリング」問題解説

参考:二分探索(Wikipedia)

ただ今回は、「G(k) がちょうど n となる k」を探すのではなく、「G(k) が初めて n 以上となる k」を探す点が少し悩ましいです。「G(k) が初めて n 以上となる」⇒「G(k-1) < n かつ G(k) ≧ n」と読み替えましょう。

具体的な二分探索のコードの書き方については上の記事を参照してください。下のコードでは、変数 left(初期値は 1) right(初期値は十分大きな値)の中央の値で変数 m を定め、G(m-1)、G(m) ともに n 以上であるなら right の方を更新し、ともに n より小さければ left の方を更新するというコードになっています。

def g(k):
c, t = 0, 1
while k > t:
c += t*(k/(10*t))
d = (k/t)%10
if d == 3: c += k%t + 1
elif d > 3: c += t
t *= 10
return c

def f(n):
left, right, m = 1, 10**16, 0
while True:
m = (left + right) / 2
c, d = g(m-1), g(m)
if c >= n: right = m
elif d < n: left = m
else: break
return m

n = int(input())
print f(n)

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックしてください。

CodeIQ「カウント・スリー」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
次回のKawazoeさんの問題もご期待ください。

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。