問題はこちら
No.326 あみだますたー - yukicoder
{1,…,N}上の順序 "<" を i < j ⇔ Ai < Aj により定める
このとき、「あみだくじによって数列{Ai}を作ること」と「順序"<"によってバブルソートをすること」が対応する
（完成するあみだくじにおいて左にある数ほど"小さい"と考えるということ）
ということでバブルソートを実装するだけ
d[110],g[110],ans[6000];c,i,j,n,k,t,a,b; main(){ scanf("%d%d",&n,&k); for(i=1;i<=n;i++)d[i]=i; while(k--){ scanf("%d%d",&a,&b); d[a]^=d[b]^=d[a]^=d[b]; } for(i=1;i<=n;i++)scanf("%d",g+i); for(i=1;i<=n;i++)for(j=1;j<=n-i;j++)if(g[d[j]]>g[d[j+1]]){//ここのif文の条件が普通のバブルソートと違う ans[c++]=j; d[j]^=d[j+1]^=d[j]^=d[j+1]; } printf("%d\n",c); for(i=0;i<c;i++)printf("%d %d\n",ans[i],ans[i]+1); }
さてこれを縮めよう
この問題はスペシャルジャッジなので、出力を全て空白区切りで行っても大丈夫であることを利用してprintfを1つにまとめることができる
また大量にある変数たちもぐっと睨むことでいくつか減らすことが出来る
とりあえずこう
d[110],g[110],s[6000];c,i,j; main(n,k,a,b){ for(scanf("%d%d",&n,&k);i++<n;)d[i]=i; for(;k--;d[a]^=d[b]^=d[a]^=d[b])scanf("%d%d",&a,&b); for(;~scanf("%d",++j+g);); for(;n--;)for(i=0;i++<n;)g[d[i]]>g[d[i+1]]?d[s[c++]=i]^=d[i+1]^=d[i]^=d[i+1]:0; for(;k<c*2;k++)printf("%d ",~k?s[k/2]+k%2:c);//kは-1から }
for文をまとめていく
前の方に出てくる変数を後ろの方でうっかりいじらないように注意する
また、3つ目のfor文に出てくるjのincを上手く使って、それ以降のループを調整する
//1つ目+2つ目 for(scanf("%d%d",&n,&k);i++<n;)d[i]=i;for(;k--;d[a]^=d[b]^=d[a]^=d[b])scanf("%d%d",&a,&b); for(scanf("%d%d",&n,&k);i++<n?d[i]=i:k--?scanf("%d%d",&a,&b),d[a]^=d[b]^=d[a]^=d[b]:0;); for(;i++<105?d[i]=i:k--?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):0;); //scanfを1つにできた（ただし初期値としてk≠0,n=0が必要） //+3つ目 for(;i++<105?d[i]=i:k--?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):0;);for(;~scanf("%d",++j+g);); for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g);); //4つ目のネストを1重に for(;n--;)for(i=0;i++<n;)g[d[i]]>g[d[i+1]]?d[s[c++]=i]^=d[i+1]^=d[i]^=d[i+1]:0; for(;j++<n?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--);); //+4つ目 for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g););for(;j++<n?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--);); for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--);); //+5つ目 for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:(j=0,n--););for(;k<c*2;k++)printf("%d ",~k?s[k/2]+k%2:c);//kは-1から for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:n?j=!n--,1:printf("%d ",j-1?s[j/2]+j%2:c)&&j-2*c-1;);//jは1から for(;i++<105?d[i]=i:k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a):~scanf("%d",++j+g)?:n/j?g[d[j]]>g[d[j+1]]?d[s[c++]=j]^=d[j+1]^=d[j]^=d[j+1]:1:n?j=!n--,1:j-2*c-!!printf("%d ",j-1?s[j/2]+j%2:c););
というわけで完成したものがこれ
d[110],g[110],s[6000];c,i,j,n; main(k,a,b){ for(;i++<105?d[i]=i://1つ目 k-->0?scanf("%d%d",&a,&b),n?d[a]^=d[b]^=d[a]^=d[b]:(k=b,n=a)://2つ目 ~scanf("%d",++j+g)?://3つ目 n/j?g[d[j]]>g[d[j+1]]?d[s[++c]=j]^=d[j+1]^=d[j]^=d[j+1]:1://4つ目の内側 n?j=!n--,1://4つ目の外側 j-2*c-!!printf("%d ",j-1?s[j/2]+j%2:c);//5つ目 ); }
254B
