「中学入試から：数字の個数」の解説・解題

CodeIQ に「中学入試から：数字の個数」という問題
https://codeiq.jp/ace/nabetani_takenori/q1138
を出した。

中学入試算数問題第4弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題が出ることがあります。
整数aのなかに現れるnの個数を《a, n》と表します。
例えば
《110, 0》=1
《1112, 1》=3
《1234, 5》=0
《141421, 4》=2
です。
このとき、100から200までの整数の中に現れる 2 の個数の合計、つまり
《100, 2》+《101, 2》+ … +《200, 2》 を求めなさい。
この問題を
整数aのなかに現れるnの個数を《a, n》と表します。
例えば
《110, 0》=1
《1112, 1》=3
《1234, 5》=0
《141421, 4》=2
です。
このとき、AからBまでの整数の中に現れる C の個数の合計、つまり
《A, C》+《A+1, C》+ … +《B, C》 を求めなさい。
と考え、A, B, C を入力として与えます。問題の答えを計算するプログラムを書いて下さい。
■具体的な課題
下記リンクの zip 内に data.txt というファイルがあります。
これらのファイルの各行は
　「データID、空欄A〜Cの内容、空欄A〜Cの内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。
■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。
・空欄A〜C は、空白なしのコンマ区切りでならべられています。
・0<A、A+1<B<(10の18乗)、A, B はいずれも整数、C は0〜9 のいずれかです。
■資料
http://nabetani.sakura.ne.jp/codeiq/q1138.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています
・ data.txt
　→ 調査対象およびテストデータです。
■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

で。
今回も出題ミスが。
問題文に「0<A」とあるのに、A=0 のデータが入っていました。
すぐに修正しましたが、A=0 のデータのまま解いてくださった方が何名かいらっしゃいました。
本当にすいません。

出題の背景と意図とか

これもかなりリアルな中学入試問題。
今回は字句解析がないので、かなり純粋な算数になっている。
簡単だったでしょ？

実装戦略と例

まず。
最大のデータは「98323006207907200」とかになっていて、これはおよそ 10の17乗、つまり京を超える数になっている。
現代のコンピュータでは素直にループを回してなんとかなることは極稀だと思う。
というわけで（中学入試でこのような問題を解くことになった小学生と同じように）計算量を減らす必要がある。

だいたいこの手の計算では（私の場合）境界でミスるので、境界を減らすために

f(B,C) = 《0, C》+《1, C》+ … +《B, C》

という関数を考える。これがあれば

答え = f(B,C) - f(A-1,C)

となる。こうすると、下側の境界のことはあまり考えなくて良くなるので楽になる。

で。f(B,C) を求めたい。
いろいろ考えると（この、いろいろ考えている部分をうまく説明できないんだけど）桁ごとに集計すると計算可能になるということがわかる。
で。軽く実装してテストを走らせると、C=0 の場合に間違えることに気づく。
それを補正すると実装完了。という流れになると思う。

今回はC言語で。

//clang -std=c99 -Wall
#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <assert.h>

int64_t max( int64_t a, int64_t b ){
  return a<b ? b : a;
}

int64_t min( int64_t a, int64_t b ){
  return a<b ? a : b;
}

// 0〜a の数 の x で示される桁に c が何個現れるか。(a<0 なら 0 を返す )
int64_t digit_count_at( int64_t a, int c, int64_t x ){
  if ( a<x ){
    return 0;
  }
  int64_t y=x*10;
  int64_t base = (a/y)*x;// 普通に繰り返す分
  int64_t last = min( max(a%y-c*x+1,0), x);// 最後の方にある分
  int64_t excess = ( c==0 ? x : 0 );// # c==0 の時に数えすぎる分
  return base + last - excess;
}

// 0〜a の数に c が何個現れるか。(a<0 なら 0 を返す )
int64_t digit_count(int64_t a, int c ){
  int64_t count=0;
  for( int64_t x=1 ; x<=a ; x*=10 ){
    count+=digit_count_at( a, c, x );
  }
  int zero_adjust = (c==0 && 0<=a ) ? 1 : 0; // A==0 である場合に対する対処(※1)
  return count + zero_adjust;
}

// 問題を解く。
// aからb(両端含む) の 10 進数表現の中に c が何個現れるか。
int64_t solve(int64_t a, int64_t b, int c ){
  assert( 0<=c && c<=9 );
  return digit_count(b,c)-digit_count(a-1,c);
}

今回は main 関数省略。計算をする部分だけにした。
入力データの字句解析は、C言語なので、fscanf するのが良いと思う。

動作確認は clang-600.0.54 on MacOS X でしか行ってませんすいません。

digit_count_at がちょっとごちゃごちゃしていてわかりにくいかもしれないけど、まあこんなところで。
→ この記事の末尾に解説追記しました。

digit_count の「※1」の部分は、当初の data.txt にあった、A==0 のデータに対する対応。修正後のデータについては zero_adjust による補正は不要である。

あと。min と max を関数として定義しているので、このコードは Visual Studio だとエラーになるかも。その場合は NOMINMAX すればいい。

感想など

今回もほぼ全員が正解だった。
おめでとう！

いつも通り、締切後はコード公開大歓迎。
コードを公開したら、 twitter などで知らせてくれると見つけやすくて助かります。

今回は 60bit ぐらいの整数が扱えないと苦しいので、 JavaScript では苦しい展開に。
ということに後から気づき、ちょっと申し訳ないような、逆に新たな言語を学ぶ機会を与えられてよかったような、どっちだろう。

そうそう。
解答の数字は、2, 3, 5 の整数乗を適当にならべたものでした。

最後に

次の問題がもう公開されている。
https://codeiq.jp/ace/nabetani_takenori/q1188
しつこく中学入試算数。簡単だよ？

それと。
オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/ )。
次回は未定だけどそのうちやります。

もうちょっと解説

ソースコード見てもわからんという意見を頂いたので、まじめに解説。

抽象的に考えるとわからなくなるので、具体的に考える。
考えるのは、以下の4通り。
a) 0〜12345 の 100 の位に 1 は何回現れるか
b) 0〜12345 の 100 の位に 3 は何回現れるか
c) 0〜12345 の 100 の位に 5 は何回現れるか
z) 0〜12345 の 100 の位に 0 は何回現れるか
なんで 4 つも考えるのかというと、境界条件をはっきりさせる必要があるのと、0を特別扱いする必要があるから。

で。まずは (a)。注目する数字は 1。

0〜(12000-1) の間に、12000÷10 回現れる。
12000〜12345 の間に、つまり、12100〜12199 の間に 100回現れる。

ということになっている。
なんで 0〜(12000-1) の間に、12000÷10 回現れるのかというと。
先頭にゼロを詰めて（つまり、3 のような数を 00003 のように表記する）と、0〜9 の数字がちょうど同じ回数だけ現れるから。

次に (b)。注目する数字は 3。

0〜(12000-1) の間に、12000÷10 回現れる。
12000〜12345 の間に、つまり、12300〜12345 の間に 46回現れる。

そして(c)。注目する数字は 5。

0〜(12000-1) の間に、12000÷10 回現れる。
12000〜12345 の間には現れない。

最後に (z)。注目する数字は 0。

0〜(100-1) の間には、現れない。
100〜(12000-1) の間に、(12000-100)÷10 回現れる。
12000〜12345 の間、つまり、12000〜12099 の間に 100回現れる。

と、それぞれバラバラの動きをする。 if 文で分岐してそれで済ますのももちろん正義だと思うけど、私はまとめてみた。

(z) と (a) はよく似ていて、元のソースにある「excess」の部分で差を吸収すればあとは同じ計算になる。
ややこしいのは 12000〜12345 の部分。

c ＜ 3 なら、100個。この 100 は、「x」そのもの。
c ＝ 3 なら、46個。この 46 は、「a%y-c*x+1」という式で表現できる。
c ＞ 3 なら、0個。

ということになる。
表にしてみると

c	x	a%y-c*x+1	ほしい値
0	100	346	100
1	100	246	100
3	100	46	46
5	100	-154	0

という具合になる。
表を眺めると「max( a%y-c*x+1, 0 ) で得られた値と 100 の小さい方」でほしい値が得られることがわかる。
というわけで、上に書いたようなソースコードになる。

ruby による実装例

最初の方のフィードバックには「rubyで」と書いたのに ruby がないのはよろしくないということで、ruby 版を以下に。

# 0〜a の数 の x で示される桁に c が何個現れるか。(a<0 なら 0 を返す )
def digit_count_at( a, c, x )
  y=x*10
  return 0 if a<x
  base = (a/y).floor*x # 普通に繰り返す分
  last = [ [a%y-c*x+1,0].max, x].min # 最後の方にある分
  excess = ( c==0 ? x : 0 ) # c==0 の時に数えすぎる分
  base + last - excess
end

# 0〜a の数に c が何個現れるか。(a<0 なら 0 を返す )
def digit_count(a,c)
  nof_places = a.to_s.size
  digits = nof_places.times.map{ |b| digit_count_at( a, c, 10**b ) }
  digits.inject(&:+) + (c==0 && 0<=a ? 1 : 0 )
end

# 問題を解く
def solve(src)
  a,b,c=src.split(",").map(&:to_i)
  digit_count(b,c)-digit_count(a-1,c)
end

C言語版とまったく同じ。手元では先にこれがあって、これを C言語に移植したのが上の方にあるもの。
floor が書いてあるけど、要らないかな。
ruby だと整数が大きくなることを気にしなくていいのが心地よい。
「nof_」は、「number of」という意味の接頭辞で私自身はよく使うけど一般的じゃないかも。

浮動小数点の話

浮動小数点の誤差を気にしていないコードが散見されたのが気になった。
ということを書き忘れていたことに気がついた。

ruby だと 10**10 のような形で 10 の 10 乗が計算できるんだけど、Cや Java にはそんな演算子はないので

  int x = (int)pow( 10, base );

や

  int x = (int) Math.pow( 10, base );

のようなことを書きたくなるが、これはよろしくない。

テストデータには「100000000000000000」が入っていて、これは 10 の 17 乗で、2進数で57桁ある。
pow は double を扱うものなので、(先頭の1を含めて)53bit しか扱えない。
桁数が足りないので、四捨五入すれば済むとか言う話ではない。もう全然無理なのである。
実際。
10の17乗より計算結果がちょっと小さい 35の11乗を例に取ると、

Math.round(Math.pow(35,11))==96549157373046880
35の11乗 == 96549157373046875

と、誤差が5。話にならない。

というわけで、浮動小数点の誤差にはくれぐれも注意しましょう。

なお。groovy と ruby は 35**11 で誤差なしの計算ができるので幸せである。

宿題：今回の課題では、pow や Math.pow を使っても正しい結果が得られた。この理由について考察せよ。
※ 宿題の正解は公開しない予定。

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。