AOJ 0093 - Leap Year - 布の切れ端

ある期間内の閏年を出力する問題．
問題自体は簡単，この記事書くのに1時間．

#include <iostream>
#include <cstdio>
int main(){
	int a, b, d = 0;
	while(scanf("%d%d", &a, &b), a && b){
		if(d)puts("");
		else d = 1;
		int c = 0;
		for(;a<=b;a++){
			if(a % 4 == 0){
				if(a % 100 == 0){
					if(a % 400 == 0){c++, printf("%d\n", a);}
				}
				else c++, printf("%d\n", a);
			}
		}
		if(!c)puts("NA");
	}
}

ショートコーディング
194byte:

#include<cstdio>
main(){int a,b,d=0,c;while(scanf("%d%d",&a,&b),a){if(d++)puts("");c=0;for(;a<=b;a++)if(a%4<1)if(a%25)c++,printf("%d\n",a);else if(a%16<1)c++,printf("%d\n",a);if(!c)puts("NA");}}

166byte(C++最短):

#include<cstdio>
main(){int a,b,d=0,c;while(scanf("%d%d",&a,&b),a){if(d++)puts("");c=0;for(;a<=b;a++)if(a%4<1)if(a%25||a%16<1)c++,printf("%d\n",a);if(!c)puts("NA");}}

書いている間にいろいろな手法を思いつきました．
このコードにはそれが散りばめられています．
(1)割り切れる
普通：

a%4==0

今回：

a%4<1

aは自然数なので，a%4は0,1,2,3の４通りになります．
そのうち，a%4<1となるのは0のみなので2byteの削減ができます．

(2)AOJ独特のデータ間空行
普通：

if(d)puts("");
else d=1;

今回：

if(d++)puts("");

後置インクリメントを利用しました．

(3)終了条件
普通：

while(scanf("%d%d", &a, &b), a, b){
//処理
}

今回：

while(scanf("%d%d", &a, &b), a){
//処理
}

0 < a,b < 3000が保証されているので，aが0ならば，bは0です．

(4)閏年判定
普通：

if(a % 4 < 1){//(1)を利用
  if(a % 100)
    c++, printf("%d\n", a);
  else if(a % 400 < 1)//(1)を利用
    c++, printf("%d\n", a);
}

今回：

if(a % 4 < 1){
  if(a % 25)//(i)100で割り切れないかを判定
    c++, printf("%d\n", a);
  else if(a % 16)//(ii)400で割り切れるか判定
    c++, printf("%d\n", a);
}

少し複雑です．
(i)に来た時点でaは４で割り切れることがわかっています．
ここで２５で割り切れなければ４のみ，つまり閏年となります．
(ii)に来た時点でaは２５で割り切れます．((i)の反対)
１６で割り切れれば，aは１６，２５，つまり２００で割り切れ閏年となります．

(5)結合
前回(194byte)：

if(a % 4 < 1){
  if(a % 25)//(i)100で割り切れないかを判定
    c++, printf("%d\n", a);
  else if(a % 16)//(ii)400で割り切れるか判定
    c++, printf("%d\n", a);
}

今回(166byte)：

if(a % 4 < 1){
  if(a % 25 || a % 16 < 1)
    c++, printf("%d\n", a);
}

すごく複雑でした．
OR演算子を用いました．
194byteでの可能性
A,a % 25 = TRUE
100(25)で割り切れないので閏年です．
このとき，a % 16は関係ないです．
よって，
1,a % 25 = TRUE, a % 16 = TRUEのとき，閏年
2,a % 25 = TRUE, a % 16 = TRUEのとき，閏年
B,a % 25 = FALSE
100(25)で割り切れるのでa % 16 < 1を評価します．
a % 16 < 1がTRUEならば，400(16,25)で割り切れるので閏年，
FALSEならば，100(25)のみ割り切れるので閏年ではありません．
よって，
3,a % 25 = FALSE, a % 16 = TRUEのとき，閏年
4,a % 25 = FALSE, a % 16 = FALSEのとき，閏年ではない

166byteでの可能性
可能性としては４通りあります．(すべてaは4で割り切れます)
1,a % 25 = TRUE, a % 16 < 1 = TRUE
100(25)で割り切れないので，閏年
2,a % 25 = TRUE, a % 16 < 1 = FALSE
100(25)で割り切れないので，閏年
3,a % 25 = FALSE, a % 16 < 1 = TRUE
100(25)で割り切れ，400(16,25)で割り切れるので閏年
4,a % 25 = FALSE, a % 16 < 1 = FALSE
100(25)でしか割り切れないので閏年ではない

どちらにしても同じことが分かりました．

12/11/03の説明

a: year≡0 (mod 4)
b: year≡0 (mod 100)
c: year≡0 (mod 400)

とすると，カルノー図は次のようになります．

		bc
		00	01	11	10
a	0	0	0	0	0
a	1	1	1	1	0

図より真となる条件式は

となります．

これを用いた式を(5)でつかっているのです．