Deltix Round Spring 2021 : F. Favorite Game

面倒ではあるけど、難しくはない。
https://codeforces.com/contest/1523/problem/F

問題

2次元座標上にN個の塔がある。
また、M個のイベントが起きる場所と時刻が与えられる。

プレイヤーは初期状態で任意の座標に降り立つことが出来、かつ以下の行動がとれる。

• 一度訪れた塔に瞬時にワープする
• 時間を1掛け、隣接する格子点に移動する。

プレイヤーを極力多くのイベントが起きる時間・場所に到達させたい。
最大何個のイベントに到達可能か。

解法

f(mask, num) := maskが訪れたことある塔の集合で、numが到達したことがあるイベント数であるとき、その状態に到達する最短時刻
g(mask, event) := maskが訪れたことある塔の集合で、最後にevent番のイベントに到達したことがあるとき、そこまでに到達したことがあるイベントの最大数

上記2つの状態を持ち、ダイクストラ法を行おう。

int N,M;
int X[200],Y[200],T[200];
int costm[1<<14][114];
int cost[114][114];


int ma[1<<14][114];
ll tim[1<<14][114];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,M) cin>>X[i+N]>>Y[i+N]>>T[i+N];
	FOR(x,N+M) FOR(y,N+M) cost[x][y]=abs(X[x]-X[y])+abs(Y[x]-Y[y]);
	int mask;
	FOR(mask,1<<N) {
		FOR(i,N+M) {
			costm[mask][i]=1<<30;
			FOR(x,N) if(mask&(1<<x)) costm[mask][i]=min(costm[mask][i],cost[x][i]);
		}
	}
	
	
	FOR(mask,1<<14) FOR(x,114) tim[mask][x]=1LL<<60;
	FOR(mask,1<<14) FOR(x,114) ma[mask][x]=-1<<30;
	priority_queue<pair<ll,int>> Q;
	FOR(i,N) tim[1<<i][0]=0, Q.push({0LL,(1<<i)*1000+0});
	FOR(i,M) {
		ma[0][i+N]=0;
		Q.push({-T[i+N],1000000000+i+N});
	}
	
	int ret=0;
	while(Q.size()) {
		ll ctim=-Q.top().first;
		int state=Q.top().second;
		Q.pop();
		if(state>=1000000000) {
			state-=1000000000;
			int cur=state%1000;
			
			FOR(mask,1<<N) {
				int num=++ma[mask][cur];
				if(num<=0) continue;
				
				ret=max(ret,num);
				// go space
				FOR(i,N) if((mask&(1<<i))==0) {
					int co=min(cost[cur][i],costm[mask][i]);
					if(tim[mask|(1<<i)][num]>T[cur]+co) {
						tim[mask|(1<<i)][num]=T[cur]+co;
						Q.push({-tim[mask|(1<<i)][num], (mask|(1<<i))*1000+num});
					}
				}
				// go next
				for(i=N;i<N+M;i++) if(T[i]>T[cur]) {
					int co=min(cost[cur][i],costm[mask][i]);
					if(T[i]>=T[cur]+co) ma[mask][i]=max(ma[mask][i],num);
				}
			}
		}
		else {
			mask=state/1000;
			int num=state%1000;
			if(ctim!=tim[mask][num]) continue;
			
			// go space
			FOR(i,N) if((mask&(1<<i))==0) {
				int co=costm[mask][i];
				if(tim[mask|(1<<i)][num]>ctim+co) {
					tim[mask|(1<<i)][num]=ctim+co;
					Q.push({-tim[mask|(1<<i)][num], (mask|(1<<i))*1000+num});
				}
			}
			// go next
			for(i=N;i<N+M;i++) {
				int co=costm[mask][i];
				if(T[i]>=ctim+co) {
					ma[mask][i]=max(ma[mask][i],num);
				}
			}
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

わかってしまえばシンプルだけど、本番さっと思いつくのは大変そう。