体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

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

問題のおさらい

自然数を 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 回がプラスされます。

1 2 3次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。
GetNews girl / GetNews boy

オスカー2018年晴れ着撮影会