TopCoder SRM 583 Div1 Easy TravelOnMars

Easyもかなり早く解けたし、Mediumもそこそこの速度で解けて良かった。
…と思ったらしょうもないミスでEasyを落とした。
Mediumを解けてたのでレートは微増したが、せっかく久々の100位以内に入るチャンスだったのにもったいない…。
http://community.topcoder.com/stat?c=problem_statement&pm=12608

問題

0～(N-1)番の駅が円形に並んでいる。
各i番の駅からは、円の両方向にR[i]個以内の駅まで直行便で移動できる。
ここで、開始する駅番号と目的の駅番号が与えられるとき、移動に必要な最少の直行便の数を答えよ。

解法

１手で移動できる駅がわかるので、あとはDijkstraでもFloydでも良いので最短経路するだけ。
今回引っ掛けなのはR[i]がNより大きい場合があること。
自分も含めこれに引っかかって配列をマイナスインデックスで参照した人が多数…。

Div1にしては簡単だったと思ったら、これが引っ掛け…？

class TravelOnMars {
	int N;
	int dp[60];
	public:
	int minTimes(vector <int> range, int startCity, int endCity) {
		int i,j,k,x,y;
		N=range.size();
		
		FOR(i,N) dp[i]=999;
		dp[startCity]=0;
		
		FOR(i,60) {
			FOR(x,N) {
				for(y=1;y<=range[x];y++) {
					int z=(x+y)%N;
					dp[z]=min(dp[z],dp[x]+1);
					z=(x-y+50*N)%N;
					dp[z]=min(dp[z],dp[x]+1);
				}
			}
		}
		
		return dp[endCity];
	}
};

まとめ

問題はちゃんと読もう。相変わらずの凡ミスでチャンスを逃してもったいない。