TopCoder SRM 767 : Div1 Medium MahdiJumping

作問側のつめが甘い回。
https://community.topcoder.com/stat?c=problem_statement&pm=15618

問題

正整数N,A,B,a,bが与えられる。以下の問いに答えよ。
0～(N-1)の数値が書かれたマスがある。
初期状態では0のマスにコマが置かれている。

現在いるコマの数値をxとする。

• x+1に移動するコストはa
• (A*x+B) mod Nに移動するコストはb

とするとき、(N-1)番のマスに到達する最短コストを求めよ。

解法

この問題、なんと愚直にダイクストラ法を実行しても2.8sぐらいで間に合ってしまう。

一応O(N)解も紹介。
移動する際にかかるコストはa,bの2つしかない。
そこで、priority_queueの代わりにqueueを2個使いダイクストラ法を行う。
両キューは、最後どちらの移動を行ったかによって入り先が異なる。
そうすると、両キュー内では必ず到達コストが昇順となっている。

あとは、両キューの先頭のうち到達コストが小さい方を取り出し、ダイクストラ法を行っていけばよい。
ただこれ、O(N)ではあるけど1.0sぐらいはかかるのよね。

ll D[5050505];

class MahdiJumping {
	public:
	long long minDis(int n, int A, int B, int a, int b) {
		int i;
		FOR(i,n+1) D[i]=1LL<<60;
		D[0]=0;
		queue<int> Q1,Q2;
		Q1.push(0);
		while(Q1.size() || Q2.size()) {
			int cur;
			if(Q2.empty() || (Q1.size() && D[Q1.front()]<=D[Q2.front()])) {
				cur=Q1.front();
				Q1.pop();
			}
			else {
				cur=Q2.front();
				Q2.pop();
			}
			
			int na=cur+1;
			int nb=(1LL*A*cur+B)%n;
			if(na<n && D[na]>D[cur]+a) {
				D[na]=D[cur]+a;
				Q1.push(na);
			}
			if(D[nb]>D[cur]+b) {
				D[nb]=D[cur]+b;
				Q2.push(nb);
			}
		}
		return D[n-1];
	}
}

まとめ

ダイクストラ法でTLEしないか確認しなかったのかな。