問題はこちら
No.508 超ゆとり教育 - yukicoder
正確な値は√(N/π)だが、√(N/π)≦√N≦10^6なので、誤差制約から1～10^6の何を出力しても正解になることがわかる。
むしろ真面目に√(N/π)を計算してしまうとN≦3のときに0となってWAの原因になる。
main(){puts("1");}
18B
そういえばreturn 0;をしなくて良くなったので、
a;main(){a=!puts("1");}
とする必要があったときに比べて5B短くて済むようになったのだなあ
問題はこちら
No.507 ゲーム大会(チーム決め) - yukicoder
K君以外の人のスコアを昇順にソートしておく
何点の人と組めばよいかを二分探索で求める。
X点の組がM位タイ以内に入れるというのは、X点より真に大きな点の組がM組未満であることと同値
これは尺取法によりO(N)で求まる。
二分探索が収束するまでO(logN)回やるので全体としてはO(NlogN)
a[1<<17];n,M,l,r,m,ll,rr,k; c(int*p,int*q){return*p-*q;} main(){ scanf("%d%d",&n,&M); for(int i=0;i<n;i++)scanf("%d",a+i); qsort(a+1,n-1,4,c); l=0;r=n; while(r-l>1){ //半開区間(l,r]での二分探索 //（rは解なしのときと対応） m=(l+r)/2; ll=1;rr=n-1;k=0; while(ll<rr){ //尺取法 //得点が高い人は、できるだけ低い点の人と組む if(ll==m)ll++; else if(rr==m)rr--; else if(a[ll]+a[rr]>a[0]+a[m])k++,ll++,rr--; else ll++; } if(k<M)r=m; else l=m; } printf("%d",r==n?-1:a[r]); }
まずはこの部分を縮める
if(ll==m)ll++; else if(rr==m)rr--; else if(a[ll]+a[rr]>a[0]+a[m])k++,ll++,rr--; else ll++; rr==m?rr--: ll==m?ll--: a[ll]+a[rr]>a[0]+a[m]?k++,ll++,rr--:ll++; rr==m?rr--: (ll!=m&&a[ll]+a[rr]>a[0]+a[m]?k++,rr--:0,ll++); rr-m?ll-m&&a[ll]+a[rr]>a[0]+a[m]?k++,rr--:0,ll++:rr--;
読み込みを全部aにまとめる。indexのズレに気をつけながら縮めると
a[1<<17],p,q,l,r,m; c(int*p,int*q){m=*p-*q;} main(k){ for(l=2;~scanf("%d",a+r);r++); for(qsort(a+3,r-3,4,c);r-l>1;k<a[1]?r=m:(l=m)) for(m=l+r>>1,p=3,q=*a+1,k=0;p<q;q-m?p-m&&a[p]+a[q]>a[2]+a[m]?q--,k++:0,p++:q--); printf("%d",a[r]?:-1); }
ぐっと睨んで、一番短くなるようにindexをずらす
a[1<<17],p,q,l,r,m;c(int*p,int*q){m=*p-*q;}main(k){for(l=2;~scanf("%d",a+r);r++);for(qsort(a+3,r-3,4,c);r-l>1;k<a[1]?r=m:(l=m))for(m=l+r>>1,p=3,q=*a+1,k=0;p<q;q-m?p-m&&a[p]+a[q]>a[2]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);} a[1<<17],p,q,k,r,m;c(int*p,int*q){m=*p-*q;}main(l){for(;~scanf("%d",a-1+r);r++);for(qsort(a+2,r-3,4,c);r-l>1;k<*a?r=m:(l=m))for(m=l+r>>1,p=2,q=a[-1],k=0;p<q;q-m?p-m&&a[p]+a[q]>a[1]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);} a[1<<17],p,q,l,r,m;c(int*p,int*q){m=*p-*q;}main(k){for(;~scanf("%d",a-2+r);r++);for(qsort(a+1,r-3,4,c);r-l>1;k<a[-1]?r=m:(l=m))for(m=l+r>>1,p=1,q=a[-2],k=0;p<q;q-m?p-m&&a[p]+a[q]>*a+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);} a[1<<17],p,q,k,r,m;c(int*p,int*q){m=*p-*q;}main(l){for(;~scanf("%d",a-3+r);r++);for(qsort(a,r-3,4,c);r+l>1;k<a[-2]?r=m:(l=-m))for(m=r-l>>1,q=a[-3],p=k=0;p<q;q-m?p-m&&a[p]+a[q]>a[-1]+a[m]?q--,k++:0,p++:q--);printf("%d",a[r]?:-1);}
ということで結局一番短くなるのは上から2番目の
a[1<<17],p,q,k,r,m; c(int*p,int*q){m=*p-*q;} main(l){ for(;~scanf("%d",a-1+r);r++); for(qsort(a+2,r-3,4,c);r-l>1;k<*a?r=m:(l=m)) for(m=l+r>>1,p=2,q=a[-1],k=0;p<q;q-m?p-m&&a[p]+a[q]>a[1]+a[m]?q--,k++:0,p++:q--); printf("%d",a[r]?:-1); }
228B
問題はこちら
No.504 ゲーム大会(ランキング) - yukicoder
最初は1位で、自分より真に大きなスコアがでたら順位が1つ下がる。
n,s,t,rank;
main(){
scanf("%d%d",&n,&s);
rank=1;
puts("1");
for(int i=1;i<n;i++){
scanf("%d",&t);
if(t>s)rank++;
printf("%d\n",rank);
}
}
1番目,2番目の値に対してのみ特殊な処理が必要なので、その辺をmain第一引数を使っていい感じにする
n,s,t;main(i){for(;~scanf("%d",&n);i&&printf("%d\n",s))i--?s+=n>t:(t=n);}
73B
2017/08/01追記
よく考えたらまとめられる
1番目の値を読み込んだときに1を出力し、2番目の値を読み込んだときに何も出力しない
n,s,t;main(i){for(;~scanf("%d",&n);)i--?printf("%d\n",s+=n>t):(t=n);}
69B
問題はこちら
No.501 穴と文字列 - yukicoder
できるだけ多くAを使えば良い
また穴が2個,0個の文字が必要なときは、それぞれB,Cを使えば良い（辞書順最小なので）。
・D≧Nのとき
Aだけでは穴が足りないので末尾にBを増やす必要がある。
Aを1つBに取り替える毎に穴は1つ増えるので、Aを2*N-D個、BをD-N個にすればよい
・D≦Nのとき
Aだけでは穴が多いので末尾にCを増やす必要がある。
Aを1つCに取り替える毎に穴は1つ減るので、AをD個、CをN-D個にすればよい
i,n,d;
main(){
scanf("%d%d",&n,&d);
if(d>n){
for(i=0;i<n+n-d;i++)putchar('A');
for(;i<n;i++)putchar('B');
}else{
for(i=0;i<d;i++)putchar('A');
for(;i<n;i++)putchar('C');
}
}
ぐっと睨むと、Aの個数がmin(D,2*N-D)であることがわかるので、分岐をまとめることができ
#define min(p,q)(p<q?p:q) i,n,d; main(){ scanf("%d%d",&n,&d); for(i=0;i<min(d,2*n-d);i++)putchar('A'); for(;i<n;i++)putchar(d>n?'B':'C'); }
さらに2つのfor文もまとめて
#define min(p,q)(p<q?p:q) i,n,d; main(){ scanf("%d%d",&n,&d); for(i=0;i<n;i++)putchar(i<min(d,2*n-d)?'A':d>n?'B':'C'); }
分岐を逆にするなど適当に縮めて
i;main(n,c){for(scanf("%d%d",&n,&c);i++<n;putchar(i>c|i>n+n-c?66|c<n:65));}
75B
問題はこちら
No.500 階乗電卓 - yukicoder
N≧50以上のとき、N!は2,5の素因数をそれぞれ12個以上もつのでN! mod 10^12=0
それ以下のときだけ計算すれば良い
14!<10^12<15!なので、Nが15以上のときには先頭を0埋めする
long s=1,n; main(){ scanf("%ld",&n); if(n>=50){ puts("000000000000"); }else{ for(int i=1;i<=n;i++)s=s*i%1000000000000; printf(n>=15?"%012ld":"%ld",s); } }
条件分岐の順番をちょっと考えていい感じにまとめる
long s=1,n,M=1e12; main(i){ for(scanf("%ld",&n);n%51/i;s=s*i++%M); printf(n<15?"%ld":"%012ld",i<n?0:s); }
101B
2017/07/28追記
だいぶ頭が悪かったみたいですね
long s=1,n,M=1e12; main(i){ for(scanf("%ld",&n);n/i*50/i;s=s*i++%M); printf(n<15?"%ld":"%012ld",s); }
97B
