問題はこちら
No.429 CupShuffle - yukicoder
上下からシミュレーションするだけ
上から順に??の直前までやり、下から順に??の直前までやれば、その前後で変化している場所が答えだとわかる
#define swap(x,y)(t=x,x=y,y=t)
int main(){
int a[100010],b[100010],cup1[100010],cup2[100010];
int i,n,k,x,t;
scanf("%d%d%d",&n,&k,&x);
for(i=1;i<=n;i++)cup1[i]=i;
for(i=1;i<=k;i++){
if(i==x)scanf("%*s%*s");
else scanf("%d%d",a+i,b+i);
}
for(i=1;i<=n;i++)scanf("%d",cup2+i);
for(i=1;i<x;i++)swap(cup1[a[i]],cup1[b[i]]);
for(i=k;i>x;i--)swap(cup2[a[i]],cup2[b[i]]);
for(i=1;i<=n;i++)if(cup1[i]!=cup2[i])printf("%d ",i);
return 0;
}
当然「下から」シミュレーションをしようとすると変数を保存するための配列が必要になる
適当な再帰関数でごまかすとしても、前半と後半でswapを2回書かなければならなくなるので短くするのは難しそう
どうにか上からできないかと考えたところ、つぎのような物ができた
#define swap(x,y)(t=x,x=y,y=t)
#define min(x,y)(x<y?x:y)
#define max(x,y)(x>y?x:y)
int main(){
int a,b,cup[100010],pos[100010],end[100010];
int i,n,k,x,t,ans1,ans2;
scanf("%d%d%d",&n,&k,&x);
for(i=1;i<=n;i++)cup[i]=pos[i]=i;
for(i=1;i<=k;i++){
if(i==x)scanf("%*s%*s");
else{
scanf("%d%d",&a,&b);
if(i<x)swap(cup[a],cup[b]);
else swap(pos[a],pos[b]);
}
}
for(i=1;i<=n;i++)scanf("%d",end+i);
t=0;
for(i=1;i<=n;i++)if(cup[pos[i]]!=end[i]){
t++?ans1=pos[i]:(ans2=pos[i]);
}
printf("%d %d",min(ans1,ans2),max(ans1,ans2));
return 0;
}
前半は今まで通り行い、後半は再び{1,2,…,N}という並びからswapを行う。
cup[i]は前半終了時にi番目の位置にいるカップの番号、
pos[i]は最後にi番目の位置にいるカップが、後半開始時に居た位置
を与えるので、??の部分でpos[i]番目の位置にあるカップが入れ替えられていない時かつその時に限り、cup[pos[i]]==end[i]が成立する
endを配列に読み込む必要はないので、この辺をひとまずざっくりとまとめる
i,j,a,p[1<<17],q[1<<17];
main(n,k,x,y,z){
for(scanf("%d%d%d ",&n,&k,&x);n/++i;)p[i]=q[i]=i;
for(;k--;)--x?scanf("%d%d ",&y,&z),x>0?p[y]^=p[z]^=p[y]^=p[z]:(q[y]^=q[z]^=q[y]^=q[z]):gets(&y);
for(;~scanf("%d",&x);x-p[i=q[++j]]?a?z=i:(a=i):0);
a=!printf("%d %d",a<z?a:z,a<z?z:a);
}
やはりswapを2回書くのは冗長。p,qをまとめてp[2][1<<17]にして短縮
i,j,a,p[2][1<<17],*q=p;
main(n,k,x,y,z){
for(scanf("%d%d%d ",&n,&k,&x);n/++i;)q[i]=p[1][i]=i;
for(;k--;)--x?scanf("%d%d ",&y,&z),i=x<0,p[i][y]^=p[i][z]^=p[i][y]^=p[i][z]:gets(&y);
for(;~scanf("%d",&x);x-q[i=p[1][++j]]?a?z=i:(a=i):0);
a=!printf("%d %d",a<z?a:z,a<z?z:a);
}
とりあえずぱぱっとfor文を圧縮してみよう
単純に圧縮すると毎回n/++iが評価されるようになるから、2つ目のループ内でiを一時変数に使うことはできない
手隙の変数がないかと睨んだら、とりあえずnが使える
for(scanf("%d%d%d ",&n,&k,&x);n/++i;)q[i]=p[1][i]=i;for(;k--;)--x?scanf("%d%d ",&y,&z),i=x<0,p[i][y]^=p[i][z]^=p[i][y]^=p[i][z]:gets(&y);
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k--?--x?scanf("%d%d ",&y,&z),n=x<0,p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):0;);
最後のも合体。一時変数はiのままでもよいが、他に影響のないyに取り替えておく
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k--?--x?scanf("%d%d ",&y,&z),n=x<0,p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):0;);for(;~scanf("%d",&x);x-q[i=p[1][++j]]?a?z=i:(a=i):0);
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k?--k,--x?scanf("%d%d ",&y,&z),n=x<0,p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):~scanf("%d",&x)?x-q[y=p[1][++j]]?a?z=y:(a=y):1:0;);
変数を減らしたい
一番多いのは2つめのループの部分で、ループ変数としてk,x、入力の読み込みにy,z、一時変数にnを使っている
3つめのループ変数と答えの保存用に、0になっている変数が2つ欲しい。x,y,zはそうできず、kは使いまわせない。
ぐっと睨むとループ変数にiが使えることが分かるが、答えの保存用にnを使うことはできないのでこれら以外の変数が必要
結局、消せるのはjだけ
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k?--k,--x?scanf("%d%d ",&y,&z),n=x<0,p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):~scanf("%d",&x)?x-q[y=p[1][++j]]?a?z=y:(a=y):1:0;);
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:k?--k,i=n=--x>0,x?scanf("%d%d ",&y,&z),p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):~scanf("%d",&x)?x-p[1][y=q[i]]?a?z=y:(a=y):1:0;);
全体では以下のようになる
i,a,p[2][1<<17],*q=p;
main(n,k,x,y,z){
for(scanf("%d%d%d ",&n,&k,&x);n/++i?q[i]=p[1][i]=i:
k?--k,i=n=--x>0,x?scanf("%d%d ",&y,&z),p[n][y]^=p[n][z]^=p[n][y]^=p[n][z]:gets(&y):
~scanf("%d",&x)?x-p[1][y=q[i]]?a?z=y:(a=y):1:
0;);
a=!printf("%d %d",a<z?a:z,a<z?z:a);
}
256B
