PCK2014予選「バトンリレーゲーム」
Nが非常に大きいこと、クエリ操作が必要なことから高度なデータ構造の問題のように思えるが、交換回数が非常に小さい事に着目すれば実際は尺取法であることに気付く。
M (5 ≤ M < 200000)
ai (1 ≤ ai ≤ 100)
文中の操作とまったく同じ操作を行えるデータ構造を用意すれば
O(M*ai)により余裕をもって間に合う。
またこのような操作を実現するデータ構造を双方向連結リストというらしい(別名Deque)
#include <iostream> #include <algorithm> using namespace std; #define FOR(I,N) for(int I = 0; I < (int)(N); I++) #define FIN(V) cout<<V<<endl #define pb push_back #define INF 1 << 30 #define SIZE 1000000 typedef pair<int, int> P; int deque[SIZE]; int bi,ai; void clearDeque(){ fill_n(deque,SIZE,-1); bi = SIZE/3; ai = bi-1; } void addDeque(int value){ ai++; deque[ai] = value; } void query1(){ ai++; if(ai==SIZE)ai = 0; deque[ai] = deque[bi]; deque[bi] = -1; bi++; if(bi==SIZE)bi = 0; } void query2(){ bi--; if(bi==-1)bi = SIZE-1; deque[bi] = deque[ai]; deque[ai] = -1; ai--; if(ai==-1)ai = SIZE-1; } bool flag[200001]; int main(){ int i,j; int n,m,q,a; cin>>n>>m>>q; clearDeque(); FOR(i,n){ addDeque(i); } fill_n(flag,200001,1); FOR(i,m){ cin>>a; FOR(j,a){ if(a%2==0)query1(); else query2(); } ///cout<<deque[bi]<<endl; flag[deque[bi]] = 0; deque[bi] = -1; bi++; } FOR(i,q){ cin>>a; cout<<flag[a]<<endl; } return 0; }
単純に配列を使ってこのデータ構造を実現しようとすると、操作回数はM*ai=20000000にも及ぶのでメモリオーバーを起こしてしまう。
なので、先頭が-1(index)に到達したら
ai--; if(ai==-1)ai = SIZE-1;
このように先頭を配列の一番後ろに飛ばしてしまうとよい。