UTPC 2014 : D - ラボライブ タフグローバルフェスティバル

本番結構適当解法で通ってしまってびっくり。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_d

問題

M本の指を使ってある音ゲーを行う。
この音ゲーでは、2次元座標上に登場する音符に指を触れる。
音符が登場している間、そこにいずれかの指を置き続けなければならない。

音符はN個登場し、各音符は時間的に連続して登場する。
(同時に複数現れることはないし、音符の隙間に時間が空くことはない)
音符を押してない指は時間当たりマンハッタン距離で１移動できる。

指の初期位置及び音符の登場位置・時間が与えられたとき、全ての音符を押せるか答えよ。

解法

同じ場所に連続して音符が登場する場合、連結して1つの音符と見なしてしまってよい。
そうでない場合、時間的に連続する音符は場所が離れているので同じ指で押せない。

また、Nは1000個なので、先に音符同士を総当たりし、音符xのあと音符yへの移動が間に合うかを求めておくと良い。

あとはM本の指がそれぞれ直前どの音符を押していたか、をもとにDPで次の音符を押せるかを次々判定していく。
指は3本なので、一見直前に押していた位置はO(N^3)通りありそうである。
しかし、i番目の音符を押せるか判定する場合、1本は(i-1)番を押しており、1本は(i-2)番を押していたはずなので、実質的に直前にあり得る状態は残り1本がどこを押していただけのO(N)通り。

なので全体としてO(N^2)で解ける。

int N,M;
int X[1010],Y[1010],S[1010],T[1010];

int able[1010][1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) cin>>X[i]>>Y[i];
	cin>>N;
	FOR(i,N) {
		cin>>X[i+4]>>Y[i+4]>>S[i+4]>>T[i+4];
		if(i && X[i+4-1]==X[i+4] && Y[i+4-1]==Y[i+4]) {
			T[i+4-1]=T[i+4];
			i--;
			N--;
		}
	}
	FOR(y,N+5) FOR(x,y) able[x][y]=(S[y]-T[x])>=abs(Y[x]-Y[y])+abs(X[x]-X[y]);
	
	set<int> S,S2;
	if(M>=3) x+=1005*1005*2;
	S.insert(1005*(M>=2) + 1005*1005*2*(M>=3));
	FOR(i,N) {
		ITR(it,S) {
			int cur[3]={*it%1005,*it/1005%1005,*it/1005/1005};
			FOR(j,M) {
				if(able[cur[j]][i+4]) {
					int pre=cur[j];
					cur[j]=i+4;
					S2.insert(cur[0]+cur[1]*1005+cur[2]*1005*1005);
					cur[j]=pre;
				}
			}
		}
		swap(S,S2);
		S2.clear();
	}
	
	if(S.size()) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

まとめ

本番は、「状態数意外と少ないからsetでいいや」と無理やり通した。