Codeforces #637 Div1 C. Nastya and Unexpected Guest

文章が長いなぁ…。
https://codeforces.com/contest/1340/problem/C

問題

幅Nの道路がある。
両端と、あと途中でMか所の位置には安全地帯がある。

この道路を渡ることを考える。
信号が緑の間は、前か後ろに速度1で移動しなければならない(停止できない)。
また、安全地帯以外では移動方向を変更できない。
信号が赤の間は、安全地帯で待機しなければならない。

緑と赤の信号の変わる間隔G,Rがわかっているとき、道路を渡り切る最短時間はいくつか。

解法

赤信号の待機時間は最後に考慮するとして、まずはそれを除いて最短の道路を渡る時間Tを求めよう。
その後、floor((T-1)/G)回だけどこかで赤信号を待機しなければならないので、最後に答えにfloor((T-1)/G)*Rを加えればよい。

幸いGは小さいので、
f(n,g) := n番目の地点に到着する最短時刻のうち、mod Gを取ったときの値がgとなるもの
とするとこれは単純にDijkstra法で行ける。とはいえpriority_queueなど使うと重くてTLEするので、f(n,g)の値はそれほど大きくならないことを利用して、計算量からlogを外そう。

int N,M;
int D[101010];
int G,R;
int dp[10101][1010];
vector<short> ev[12020202];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) cin>>D[i];
	sort(D,D+M);
	cin>>G>>R;
	
	FOR(i,M) FOR(x,G+1) dp[i][x]=1<<30;
	dp[0][0]=0;
	priority_queue<pair<int,int>> Q;
	ev[0].push_back(0);
	ll ret=1LL<<30;
	int co;
	FOR(co,12010101) {
		FORR(cur,ev[co]) {
			if(cur>0) {
				ll nex=co+D[cur]-D[cur-1];
				if(co/G==(nex-1)/G) {
					if(dp[cur-1][nex%G]>nex) {
						dp[cur-1][nex%G]=nex;
						ev[nex].push_back(cur-1);
					}
				}
			}
			if(cur<M-1) {
				ll nex=co+D[cur+1]-D[cur];
				if(co/G==(nex-1)/G) {
					if(cur+1==M-1) {
						ret=min(ret,nex);
					}
					else if(dp[cur+1][nex%G]>nex) {
						dp[cur+1][nex%G]=nex;
						ev[nex].push_back(cur+1);
					}
				}
			}
		}
	}
	
	if(ret==1LL<<30) ret=-1;
	else {
		if(ret%G==0) {
			ret=(ret/G-1)*(G+R)+G;
		}
		else {
			ret=ret/G*(G+R)+ret%G;
		}
	}
	cout<<ret<<endl;
}

まとめ

TLEしてもったいない。