kmjp's blog

競技プログラミング参加記です

Coder-Strike 2014 Final - D. Cup Trick

本番あと15秒で間に合わなかった…。
http://codeforces.com/contest/420/problem/D

問題

初期状態で1~N番の番号が付いたN個のカップが1列に並んでいるが、その並び順は不明である。
これらのカップをM回シャッフルした。

各シャッフルではY[i]番目にあるカップを先頭に持ってくるという処理を行った。
その際、動かしたカップはX[i]番の番号がついていた。

初期状態であり得るカップの状態のうち、辞書順最小のものを求めよ。

解法

N,M <= 10^6なので、配列を1個ずつずらしたりすると間に合わない。
ここでは平方分割し、1000個のvectorに分けて管理した。

後は各vectorに初期状態の位置を書いた番号を入れて、シャッフル処理を再現すればよい。
その都度シャッフル対象のカップに番号X[i]を割り当て、1つのカップに2つの番号が割当たったり、2つのカップに同じ番号が割当たらないか調べていけばよい。

M回シャッフルして登場しない番号は、先頭から若い順に割り当てれば辞書順最小になる。
平方分割によりO(M√N)で処理可能。

int N,M;
int num[1000008];
int used[1000008];
vector<int> V[3000];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	
	FOR(i,N) V[i/1000].push_back(i);
	
	FOR(i,M) {
		cin>>x>>y;
		FOR(j,3000) {
			if(y<=V[j].size()) break;
			y-=V[j].size();
		}
		y--;
		k=V[j][y];
		if(num[k]!=0 && num[k]!=x) return _P("-1\n");
		if(num[k]==0 && used[x]) return _P("-1\n");
		num[k]=x;
		used[x]=1;
		
		V[j].erase(V[j].begin()+y);
		if(V[0].size()>1000) {
			for(j=2998;j>=0;j--) swap(V[j+1],V[j]);
			V[0].clear();
			V[0].push_back(k);
		}
		else {
			V[0].resize(V[0].size()+1);
			for(j=V[0].size()-1;j>=1;j--) V[0][j]=V[0][j-1];
			V[0][0]=k;
		}
	}
	
	x=1;
	FOR(i,N) {
		while(used[x]) x++;
		if(num[i]==0) num[i]=x++;
		_P("%d ",num[i]);
	}
	_P("\n");
}

まとめ

D問題とはいえ1500ptなので自力で解けるレベルだった。