またジャンケン。
https://code.google.com/codejam/contest/11264486/dashboard#s=p2
問題
N人からなるトーナメント表に基づいて試合を行い、優勝者を決めたい。
各人は、決められたジャンケンの手を出し続ける。
同じ手を出す人同士の対戦では、表中で先にいる人が勝利となる。
最終的な勝者は表中何番目の人か答えよ。
解法
ノードは最大100である。
トーナメント表を64ブロックに分割して、各ノードでブロック毎の優勝者を求め、最後にマスターノードで各ブロックの優勝者同士のトーナメント戦を行えばよい。
int TN,MY; ll N; const int D=6; int winright(char a,char b) { if(a==b) return 0; if(a=='R' && b=='S') return 0; if(a=='S' && b=='P') return 0; if(a=='P' && b=='R') return 0; return 1; } vector<pair<int,char>> go(vector<pair<int,char>> V) { int i; while(V.size()>1) { vector<pair<int,char>> VV; FOR(i,V.size()/2) VV.push_back(V[i*2+winright(V[i*2].second,V[i*2+1].second)]); swap(V,VV); } return V; } void solve(){ int i,j,k,l,r,x,y; string s; vector<pair<int,char>> V; N=GetN(); if(N<=D) { if(MY!=0) return; FOR(i,1<<N) V.push_back({i,GetFavoriteMove(i)}); V=go(V); cout<<V[0].first<<endl; } else { if(MY>=1<<D) return; FOR(i,1<<(N-D)) V.push_back({(MY<<(N-D)) + i,GetFavoriteMove((MY<<(N-D)) + i)}); V=go(V); PutInt(0,V[0].first); PutInt(0,V[0].second); Send(0); if(MY==0) { for(i=1;i<1<<D;i++) { Receive(i); x=GetInt(i); y=GetInt(i); V.push_back({x,y}); } V=go(V); cout<<V[0].first<<endl; } } }
まとめ
昨年のRound1よりは簡単だね。GCJ Round2参加者向け相当だからかな。