問題はこちら
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
