CodeIQ「中学入試から:数字の個数」
CodeIQ の鍋谷武典さん出題の問題。
問題と解説はこちら。
「中学入試から:数字の個数」の 解説・解題
プログラムは x 未満(x 自身を含まないのが自分でも混乱するけど、x 以下とやるより綺麗になるので)の数字を数える関数 count を作って、不定積分から定積分を求めるみたいに境界のとこの値を引き算するという方針。
count の中身は、一の位, 十の位, 百の位… と各桁ごとに数字の個数を足し上げていってる。
頭の 0 を含む(1 や 12 という整数の百の位は 0 と考えるということ)、 未満の非負整数に含まれる の位の数字 0 の個数は
になるから、数字 d の個数なら、この のところを に置き換える、つまり だけ平行移動してやればよい。
下のほうのコードが提出したもの。言語は Ruby。
データを付けてすぐに実行できるものを http://ideone.com/L6z2bQ に置いておいた。
フィードバックで、Kernel.p が常に見えているので、変数名に p を使うことは勧められないというアドバイスを頂いた。
まあ、これは自分でも気になっていた。
「点」とか「冪乗」とか「素数」とかの意味の変数だとつい p とかやりたくなって、でもそれだとメソッドのほうの p が隠れてしまって書いてる途中は不便だから、とりあえず pp とかいい加減な変数名にしておいて、後で p に置換するとか、今まで格好悪いことをしていた。今後気をつけよう。
p の他にも、何かの最大値の変数名を max とやって、更新するところで
max = [x, max].max
とかなったりするけど、また別の話か。
# 問題データは 'data.txt' から読み込む # 0 から x-1 までの整数に含まれる数字 d の個数 def count(x, d) q = 1 # ループカウンタが k のとき(1の位をを0桁目として) k 桁目の d の個数を加算 (0...x.to_s.size).inject(0) do |sum, k| p, q = q, q * 10 # p=10**k, q=10**(k+1) y = x - p * d c = y / q * p + [y % q, p].min # 下の3項演算子は頭の 0 を数えないようにする処理 sum + (d == 0 && k > 0 ? [c - p, 0].max : c) end end open('data.txt') do |file| file.each do |line| data = line.split(/[\t,]/) id = data[0] a, b, c, expected = data[1, 4].map(&:to_i) answer = count(b + 1, c) - count(a, c) # 計算した答が用意されたものと異なるとき、ID, 用意された答, 計算した答を出力 puts "#{id} #{expected} #{answer}" unless answer == expected end end