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

解説スライドを見て，回答．

問題文
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_d

解法
まず，同じ位置で連続している区間をマージする．
そうすると，隣り合う区間の点の位置が必ず異なる．
指が1つ以上の場合は，マージ後の区間が1つかつこの区間の開始時刻に間に合う．
指が2つ以上の場合は，どちらの指から始めるか，交互に押せるかを調べる．
指が3つの場合は，dp[時刻i][時刻iでも時刻i-1でも使われていない指の時刻]をする．

計算量はO(N^2)

ソースコードは以下の通り

int m,n;
int rx[3],ry[3];
int px[1010],py[1010],s[1010],t[1010];

inline int dist(int x1,int y1,int x2,int y2){ return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);}

bool dp[1010][1010]; // i, i-1でもない

bool solve(){
	rep(i,m) if(dist(px[0],py[0],rx[i],ry[i])<=s[0]*s[0]&&n==1) return true;

	if(m>=2){
		int finger[3]={0,1,2};
		do{
			bool ok=true;
			if(m==finger[0]||m==finger[1]) continue;
			rep(i,n){
				if(i<=1){
					if(dist(px[i],py[i],rx[finger[i]],ry[finger[i]])>s[i]*s[i]) ok=false;
				}else{
					int ts=s[i]-t[i-2];
					if(dist(px[i],py[i],px[i-2],py[i-2])>ts*ts) ok=false;
				}
			}
			if(ok) return true;
		}while(next_permutation(finger,finger+3));
	}
	if(m==3){
		int finger[3]={0,1,2};
		for(int i=n-1;i>=0;--i) px[i+3]=px[i],py[i+3]=py[i],s[i+3]=s[i],t[i+3]=t[i];
		n+=3;
		do{
			rep(i,3) px[i]=rx[finger[i]],py[i]=ry[finger[i]],s[i]=t[i]=0;
			rep(i,1010)rep(j,1010) dp[i][j]=false;
			dp[2][0]=true;
			rep(i,n)rep(j,n-2){
				if(i<=1) continue;
				if(dp[i][j]){
					int ts=s[i+1]-t[i-1];
					if(dist(px[i+1],py[i+1],px[i-1],py[i-1])<=ts*ts) dp[i+1][j]=true;
					int ts2=s[i+1]-t[j];
					if(dist(px[i+1],py[i+1],px[j],py[j])<=ts2*ts2) dp[i+1][i-1]=true;
				}
			}
			rep(i,1010) if(dp[n][i]) return true;
		}while(next_permutation(finger,finger+3));
	}

	return false;
}

int main(void){
	cin >> m;
	rep(i,m) cin >> rx[i] >> ry[i];
	cin >> n;
	rep(i,n) cin >> px[i] >> py[i] >> s[i] >> t[i];
	bool ok=false;
	//  merge
	rep(i,n-1){
		while(px[i]==px[i+1]&&py[i]==py[i+1]&&t[i]==s[i+1]){
			t[i]=t[i+1];
			for(int j=i+1;j<n;++j) px[j]=px[j+1],py[j]=py[j+1],s[j]=s[j+1],t[j]=t[j+1];
			n--;
		}
	}
	ok=solve();
	if(ok)
		puts("YES");
	else
		puts("NO");
	return 0;
}

コーナーケースに嵌りまくって辛かった．