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; }
コーナーケースに嵌りまくって辛かった.