私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「「7」の数を数えよう」（CodeIQ）を参照してください。
問題を引用します。
【問題】
1からnまで連続する正の整数があります。
それらの中に、「7」がいくつあるかを数えてください。
【例】
n = 99とすると、
（中略）
「7」を含む値は、
7 17 27 37 47 57 67 70 71 72 73 74 75 76 77 78 79 87 97
の19個ですが、77には「7」が2つ含まれています。
ですので、「7」の数は19個ではなく、20個と答えてください。なお、nは32bit整数に収まるものとします。
C言語で解答しています。
#include <stdio.h>
#include <string.h>
#include <math.h>
#define TO_CHECK 7
/*
* 素朴に数えると遅すぎるので計算で求めるバージョン
* ローカル環境とアップロード先で結果が変わる（途中までは同じ）ため、変数のサイズを上げてみた
* バージョン。
* max: 入力値
* place: 現在処理中の桁
*/
unsigned long countPlace(unsigned long long max, int place){
unsigned long long mask = pow(10, place); // 処理対象の桁で分割するため
unsigned long long now = (max / mask) % 10; // 現在の桁の値
unsigned long long left = max - max%(mask*10); // 現在よりも上の桁
// 7より小さい値の場合は、上位の桁の数に等しい7がある(ex:266 -> 26)
if(now < TO_CHECK){
return left/10;
}
// 7より大きい場合は7の時の分が全部加算される
else if(now > TO_CHECK){
return (left + (mask * 10))/10;
}
// 7の時は下の桁の数＋上の桁の数＋自身で+1
else{
return left/10 + (max % mask) + 1 ;
}
}
unsigned long count(unsigned long long max){
unsigned long i = 0;
unsigned long total = 0;
int range = 0; // 桁数
char num_str[256] = {0}; // 桁数を数えるための一時領域
sprintf(num_str, "%llu", max);
range = (unsigned long)strlen(num_str); // 入力が整数なのでlog10は使わない
// 桁ごとに数える
for(i=0; i<range; i++){
total += countPlace(max, i);
}
return total;
}
int main(int argc, char* argv[]){
unsigned long long max = 0;
char str[1024] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
sscanf(str, "%llu", &apm;max);
printf("%lu\n", count(max));
}
return 0;
}
この問題は単純にやると計算量が非常に多くなります。
私はこの問題の漸化式を求めるのにかなり苦労して一度諦めかけています。
最初の回答は次のようにごく単純に'7'が何回出現するかを数えるプログラムを投稿しました。
正しく数えられますが、全ての数字をチュックしているので非常に時間がかかります。当然のように時間切れでダメでした。
#include <stdio.h>
int count7(char* num){
int i = 0;
int c = 0;
for(i=0; num[i]; i++){
if(num[i] == '7'){
c += 1;
}
}
return c;
}
int count7Total(unsigned long max){
unsigned long i=0;
char buf[256] = {0};
int total = 0;
for(i=0; i<=max; i++){
sprintf(buf, "%ld", i);
total += count7(buf);
}
return total;
}
int main(int argc, char* argv[]){
unsigned long max = 0;
char str[1024] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
sscanf(str, "%lu", &max);
printf("%d\n", count7Total(max));
}
return 0;
}
上記のプログラムを改良して文字列ではなく、数値として7を数えるようにしてもダメそうな気がしたので漸化式を求めることにしました。これはノートに手書きでやっています。他の問題に関してもそうですが、考えをまとめる手段としては手を動かして紙に書いてみるのが一番なことは非常に多いです。
割とすぐに気付いたのは入力値の桁ごとに着目すればよさそうということでした。
プログラムのコメントにも書いてありますが、例えば入力値が266の場合、1の位に7は26回出現します。10の位に出現するのは入力値を1/10して同様に考えると2回出現します。着目している桁の値が7以上の場合はこの通りにはなりませんが、この考え方をベースに場合分けすればやれそうだったのでその方向で考えました。……(1)
現在注目している桁の値が7より大きい場合、例えば入力値が286で10の位に注目しているとすると(1)に加えて10個増えます。これも入力値を1/10しながら考えると同じようになって、10注目している桁-1だけ増加してゆきます。
最後に現在注目している桁の値が7の時です。この場合、(1)に加えて現在着目している桁より上の桁の数+1だけ7が増えます。例えば、267で1の位に着目している場合、26回は7が出現し、それに加えて最後の1回分だけ7が出現します。これも同様に一桁ずつ考えて行けば同様に処理できます。
上記の処理を実現しているのがcountPlace()で、一桁ずつ7がいくつか出現するかを計算します。それをcount()で全桁について処理し、結果を求めています。17行目の「unsigned long long now」は試行錯誤している時に作った変数で最終的に使わなかったのですが、消し忘れました。
この問題に正解する前にもう1箇所、ローカル環境とCodeIQの環境の違いでリジェクトされています。何の根拠もなしにCodeIQでコードをテストするマシンはLinuxだろうと思っていてlongは64bitあるだろうと想定していたのですが、2回目の結果出力で桁あふれしていました。CodeIQのコードをテストするマシンはWindowsなのかもしれません（Windowsはlongが32bit、long longが64bit）。
私はこの問題をループで処理していますが、再帰を使った方が綺麗に書けたと思います。再帰にすれば41行目でやっているような桁数を求める処理が不要ですし、呼び出しの度に10で割ってやれば良いので15行目でやっている現在の桁を求める処理とそれに関連する処理もしなくて良くなります。