CodeIQ MAGAZINECodeIQ MAGAZINE

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

2017.10.26 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 6
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。
若干複雑なコーディングが必要な問題でしたが、多くの方に挑戦していただきました。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

自然数を 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さんの問題もご期待ください。

  • 6
  • このエントリーをはてなブックマークに追加

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ