ICPC国内予選 - Problem F
ICPC国内予選にKiraKiraJKというチーム名で参加しました。kitayutaがA~C、enkがE、私がDを解いて結果は5完でした。
F、Gはコンテスト中は方針すら立ちませんでしたが、Fはあるさいころの状態から最終状態への移動が可能であるかをO(1)で判定する関数を見つけたら出来ると教えてもらったので書いてみました。
サンプルデータでは通りました。
ICPC国内予選問題↓
http://icpc.iisf.or.jp/2014-waseda/domestic/problems/
//ICPC2014-pre Problem F #include <iostream> #include <cstdio> #define rep(i,n) for(int i =0 ;i<n;i++) using namespace std; /* 0 1 2 3 5 4 */ void acpy(int to[],int from[]){//配列コピー rep(i,6){ to[i]=from[i]; } } void moveS(int arg[]){//南に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[4]+1; arg[1]=temp[0]; arg[2]=temp[2]; arg[3]=temp[1]; arg[4]=temp[3]; arg[5]=temp[5]; } void moveN(int arg[]){//北に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[1]+1; arg[1]=temp[3]; arg[2]=temp[2]; arg[3]=temp[4]; arg[4]=temp[0]; arg[5]=temp[5]; } void moveE(int arg[]){//東に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[5]+1; arg[1]=temp[1]; arg[2]=temp[0]; arg[3]=temp[2]; arg[4]=temp[4]; arg[5]=temp[3]; } void moveW(int arg[]){//西に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[2]+1; arg[1]=temp[1]; arg[2]=temp[3]; arg[3]=temp[5]; arg[4]=temp[4]; arg[5]=temp[0]; } bool check(int t[],int arg[]){//判定 int per[6]={0,1,2,3,4,5}; int tnow[6]; bool ans = 0; rep(i,720){ int flag = 1; rep(j,6){ tnow[j]=t[per[j]]-arg[j]; if(tnow[j]<0){ flag = 0; break;} } if(flag != 0) { int now = tnow[0]+tnow[3]; int ne1 = tnow[1]+tnow[4]; int ne2 = tnow[2]+tnow[5]; if(now<=ne1+ne2&&ne1-1 <=now+ne2&&ne2-1 <=now+ne1) //判定してる ans = 1; } if(ans == 1) break; next_permutation(per,per+6); } return ans; } int main(){ int now[6]; int prev[6]; char s[40000]; int t[6]; int sum; int p,q; int fs[6]={0,1,2,3,4,5}; while(1){ sum = 0; rep(i,6){ scanf("%d",t+i); sum += t[i]; } if(sum==0){ break; } scanf("%d %d",&p,&q); bool flag = 1; rep(i,6){ prev[i]=0; } int hoge = 1; rep(sz,sum){ acpy(now,prev); moveE(now); if(check(t,now)){ acpy(prev,now); s[sz]='E'; continue; } acpy(now,prev); moveN(now); if(check(t,now)){ acpy(prev,now); s[sz]='N'; continue; } acpy(now,prev); moveS(now); if(check(t,now)){ acpy(prev,now); s[sz]='S'; continue; } acpy(now,prev); moveW(now); if(check(t,now)){ acpy(prev,now); s[sz]='W'; continue; } hoge = 0; break; } if(hoge == 0){ printf("impossible\n"); }else{ for(int i = p-1;i < q;i++){ printf("%c",s[i]); } printf("\n"); } } }