CodeIQ:カウント・スリー

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カウント・スリー」(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) の値を出力するプログラムを書いてください。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def countPlace(n, pl)
	mask = 10**pl
	now = (n / mask) % 10		# 現在の桁の値
	left = n - n % (mask*10)	# 現在よりも上の桁の値

	if now < 3 then return left / 10
	elsif 3 < now then return (left + (mask * 10)) / 10
	else return left/10 + (n % mask) + 1
	end
end

def count(n)
	ret = 0

	for i in 0...n.to_s.size
		ret += countPlace(n, i)
	end

	return ret
end

def solve(n)
	mn = 1
	mx = 10

	loop{
		break if count(mx) > n
		mn *= 10
		mx *= 10
	}

	loop {
		ret = (mx + mn) / 2
		c = count(ret)

#		printf("mn=%d, mx=%d, ret=%d, c=%d\n", mn, mx, ret, c)

		if c < n then mn = ret + 1
		else
			if mx == mn then return ret
			else mx = ret
			end
		end
	}
end

# main
while line = gets
	line.strip!
	next if line.empty?

	p solve(line.to_i)
end

解説

★★★の問題ですが、問題の半分は過去にやったことがあったのでそれほどでもありませんでした。その経験がなければ難しかったと思います。

考え方

基本的な方針はある数を仮定した場合、その数以下に含まれる3の数が何個あるかを数え、入力値より小さければ仮定した数より大きい数、入力値より大きければ仮定した数より小さい数を再度仮定して絞り込むという単純な方法をとります。

この方法で最初に問題になるのが仮定した数以下に含まれる3の数を数える方法ですが、これは過去に「「7」の数を数えよう」という問題で同じことを実装したのでそれを流用しました。詳細はリンク先を参照してください。

次に絞り込みです。基本的に二分探索を行うとして問題になるのが、最大値が分からないことです。私は10、100、1000、…、と一桁ずつ試して見て入力値より大きな個数になったところを最大値として二分探索することにしました。例えば1000以下の3の個数が入力値以上なら100〜1000の間を探索するというわけです。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(n)

mnは探索の下限、mxは探索の上限で、初期値はそれぞれ1と10です。
28〜32行目のループでmn,mxを10倍しながらmx以下の3の個数をcount()でチェックし、入力値を超えたところでmn,mxを確定します。

34〜46行目のループが二分探索です。mn,mxの真ん中の値をチェックし、結果が入力値より小さかったらmnを探索した値にします。それ以外の場合でmx=mnの場合はその場所が答えになるのでretを返却し、そうでなければmxを更新します。
入力値が7や8の場合、33が答えになるので探索対象の数が33の時はcount()は8を返し、32の時は6を返すのでちょうど7を返す場合を探索すると探索が終わらなくなります。なのでmn=mxを終了条件とする必要があります。

count(n), countPlace(n, pl)

「7」の数を数えよう」の実装と同じですのでそちらの説明を参照してください。

雑感

この出題者の問題の傾向からゆくと計算だけで答えを求める方法があるのではないか、と思いますが私にはわかりません。多分、もっとうまい方法があるのでは、と思います。