読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.87 Advent Calendar Problem

問題はこちら
No.87 Advent Calendar Problem - yukicoder

Nが大きいので毎年曜日をチェックしていると間に合わない
うるう年は400年周期だが400年間は365*400+97=146097日であり、これは7の倍数なので
結局400年周期でカレンダーは完全に一致する
よって400年ごとにまとめてチェックできる

int main(){
	long n;
	int a[400],b,i,t;
	t=0;b=1;
	//2014年の曜日を0としておく
	//a[i]にi年後の曜日を、bに400年の内2014年と同じ曜日だった年の数を保存
	for(i=2015;i<2014+400;i++){
	//最初の400年間の曜日を調べる
		t=(t+(i%4?1:i%100?2:i%400?1:2))%7;
		//365日は52週+1日なので、ある年の7月の曜日は、その年がうるう年でなければ前の年+1、うるう年なら前の年+2となる
		a[i-2014]=t;
		if(t==0)b++;
	}
	scanf("%ld",&n);
	t=(n-2014)/400*b;
	//未来側から400年ずつまとめて処理
	for(n=(n-2014)%400;n;n--)if(a[n]==0)t++;
	//余ったところを1年ずつ調べる
	printf("%d",t);
	return 0;
}

上のプログラム中でbとした値は57なのでこれはそのまま書く
また、曜日は(n+n/4-n/100+n/400)%7で判定できる
(nが1ずつ増加していくことを考えると、カッコ内は、通常は+1、nが4の倍数になった時は+2、ただし100の倍数になった時は+1、400の倍数になった時は+2となっている)
さらに、2014年スタートではなく1年スタートにして、1~2014年までの分を引くことにして終了条件を簡略化
この時点で頭にあったのは次のような2パターン

long n;main(s){for(scanf("%ld",&n);n;)s+=n>=400?n-=400,57:(n+n/4-n/100+n--/400)%7==3;n=!printf("%d",s-289);}
//↑nが400以上か以下かでやることを場合分け
long n;main(s){scanf("%ld",&n);for(s=n/400*57;n%400;)s+=(n+n/4-n/100+n--/400)%7==3;n=!printf("%d",s-288);}
//↑nが400以上の部分はまとめて処理

ここで前者のパターンに対して圧倒的閃き
三項演算子の後半はn<400でしか実行されないんだから、n/400の項はいらなくね?!

long n;main(s){for(scanf("%ld",&n);n;s+=n>=400?n-=400,57:(n+n/4-n--/100)%7==3);n=!printf("%d",s-289);}
//とりあえず消した
long n;main(s){for(scanf("%ld",&n);n;s+=n>400?n-=400,57:(n+n/4-n--/100)%7==3);n=!printf("%d",s-289);}
//nが400のとき(n+n/4-n/100+n/400)%7は0でありsの加算に寄与しないので不等号をごまかした
long n;main(s){for(scanf("%ld",&n),s=n/400*57;n%=400;s+=(n+n/4-n--/100)%7==3);n=!printf("%d",s-288);}
//ちなみに後者のパターンでも同じ長さが達成できる

101B