私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「羊の頭数を予想して！」（CodeIQ）を参照してください。
問題を引用します。
羊の肉はラムやマトンなどに分類されます。
羊の前歯は年に2本ずつ増えることが知られており、ラムはまだ前歯が生えていない、つまり1歳未満の羊だとわかります。
あなたは、4歳未満の羊の群れを見つけました。
（つまり、この群れにいる羊の歯の数は0本、2本、4本、6本のいずれかです。）
この群れにいるm頭の羊について、歯の数を数えたところ、全部でn本ありました。
標準入力からmとnが与えられたとき、ラムの頭数として考えられる最大と最小の数を標準出力に出力してください。
C言語で解答しています。
#include <stdio.h>
struct herd {
long long count[4]; // 各年齢の頭数
int AGE_TEETH[4]; // 年齢ごとの歯の数
int LIMIT; // 年齢上限
};
int calcMin(long long total, long long teeth){
// 1歳以上の羊の数が最大なのは1歳の羊だけの時
total -= teeth / 2;
// 1歳の羊の数が全頭数を超えた場合、1歳の羊の数を減らし、2歳以上の羊を増やして調整できる
// 羊の数×6 > 歯の数の場合はありえないが事前にエラーにしているのでここでは問題ない
if(total < 0){
total = 0;
}
return total;
}
int calcMax(long long total, long long teeth){
struct herd h = {0,0,0,0,0,2,4,6,3}; // 羊の頭数（最大）
int age = 0;
for(age = h.LIMIT; age > 0; age--){
h.count[age] = teeth / h.AGE_TEETH[age];
total -= h.count[age];
teeth -= h.AGE_TEETH[age] * h.count[age];
}
// 残った頭数は0歳(不要な処理だが0歳の頭数が構造体に入らないのは気持ち悪い)
h.count[0] = total;
return total;
}
int checkInput(long long total, long long teeth){
// 歯の数は必ず偶数
if(teeth%2){
return 0;
}
// 歯の数は0以上
if(teeth < 0){
return 0;
}
// 羊の数は0以上
if(total < 0){
return 0;
}
// 歯の数が6×羊より多いことはありえない
if(total * 6 < teeth){
return 0;
}
return 1;
}
int main(int argc, char* argv[]){
char str[1024] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
long long teeth = 0; // 入力された歯の数
long long total = 0; // 入力された羊の数
long long max = 0; // 0歳の最大数
long long min = 0; // 0歳の最小数
sscanf(str, "%lld %lld", &total, &teeth);
if(!checkInput(total, teeth)){
printf("error");
continue;
}
max = calcMax(total, teeth);
if(max < 0){
printf("error");
continue;
}
min = calcMin(total, teeth);
printf("%lld %lld", max, min);
}
return 0;
}
この問題は最大数と最小数の2つの結果を計算する必要があります。
それぞれについて説明します。
計算の前に入力値のエラーチェックについて説明します。
エラーチェックはcheckInput()関数で行っています。
まず、羊の葉の数は偶数なので念のため奇数が入力された時はエラーにします。同様に負数が入力された場合も念のためエラーにします。もう1点、羊の葉の数が羊の数×6を超えることはないのでこれもエラーで弾いています。
このプログラムでは速度を稼ぐため（実際にはあまり関係ありませんが）チェックを入力値取得直後に1回だけ行っていますが、実際の仕事で作るプログラムならcalcMax()、calcMin()の先頭でそれぞれ呼び出すようにすると思います。理由はチェックを忘れてcalcMax()、calcMin()を呼び出した時のフールプルーフのためです。
実際のコードでは最小数よりも難しい処理をしていますが、考え方はこちらの方が単純です。ラムの数を最大にするためには1歳以上の羊の数を可能なかぎり少なくすれば良いということは容易に分かります。そのためにはなるべく歳のいった羊で歯の数を減らせば良いということになります。
例えば5頭で歯が10本だったとします。
まず、3歳の羊の数を決定します。3歳の羊は6本歯があるので10/6の商である1になります。
続いて先の計算の余り（10/6の余り4）を2歳の羊の歯の数4で同様に処理します。
続いて先の計算の余り（4/4の余り0）を1歳の羊の歯の数2で同様に処理します。
ここまでで求まった羊の頭数を合計の頭数から引けばラムの数になります。
実際のプログラムのclacMax()は次のような処理になっています。
23行目でherd構造体を初期化しています。
この構造体は0〜3歳の羊の数count、定数である各年齢の羊の歯の数AGE_TEETH、年齢上限の定数LIMITを保持します。羊の数は0で、その他のパラメータは問題で決められた値で初期化します。
26〜30行目のforループで3〜1歳の羊の数を計算しています。処理手順は前述の通りですが、羊の頭数も1回のループごとに減算しています。
33行目の処理はコメントにあるように不要ですが0歳の羊の数をセットしています。
そして0歳の羊の数を返します。
実際の処理は非常に簡単です。全て1歳の羊と仮定した場合の数を全頭数から引いて、結果がマイナスになったら0にリセットして返しているだけです。
問題はこのロジックが成り立つ理由です。
私はプログラムを書き始める前、次のように考えました。
いざプログラムを書こうとして11行目を書いた時、前述の処理が不要であることに気づきました。前述の処理を行っても結果として0歳の羊の数が0であることには変わりがないのです！
例外はないでしょうか。それは全て3歳の羊としても全頭数に満たない場合ですが、これはエラーチェックで弾いています。
以上から実際のコードが成り立ちます。
私はこの問題に2回リジェクトされています(^^;)。理由はエラー時の出力を「Error」と先頭を大文字にしていたためです。それも、最初にリジェクトされた時に74行目だけ直してまたリジェクトされると言うしょうもないミスをしています。
この手のケアレスミスは何回かやらかしていますが気をつけなければいけませんね。