TopCoderOpen 2013 Round1A Medium TheFrog

本番は計算量見積もりがいまいちで落とした問題。
周りの人の正答率も1/4以下と何気にみんな苦戦。
http://community.topcoder.com/stat?c=problem_statement&pm=12397

問題

１直線上に、いくつか池が与えられる。
原点から距離Xずつジャンプした際、どこの池にもはまらず池を渡りきれる最小のXを答える。

解法

最小となるからには、どこかのポイントで「池をギリギリわたりきる」ポイントがあるはずである。
そこで、各池の終端を整数で割った値が答えの候補になる。
後は、その候補のうち池にはまらず最後まで行ける最小値を探せばよい。

本番は、池をギリギリわたる点だけでなく、全部の格子点に対して検索を掛けてしまい時間切れしてしまった…。

class TheFrog {
	ll N;
	int NG[30002];
	public:
	double getMinimum(int D, vector <int> L, vector <int> R) {
		ll ml=0,i,l,j,MM=0;;
		N=L.size();
		ZERO(NG);
		
		FOR(i,N) {
			ml=max((int)ml,R[i]-L[i]);
			MM=max(MM,(ll)R[i]);
		}
		if(ml==1) return 1.0;
		FOR(i,N) {
			NG[L[i]]=1;
			for(l=L[i]+1;l<R[i];l++) NG[l]=2;
		}
		
		ll minu=MM,minl=1;
		
		FOR(j,2*N) {
			if(j<N) l=L[j];
			else l=R[j-N];
			if(l==0) continue;
			
			ll ng=0,c;
			for(c=l;c<MM;c+=l) {
				if(NG[c]==2) { ng=1; break; }
			}
			if(ng==1) continue;
			ll div=1;
			while(1) {
				if(l<div*ml) break;
				if(l*minl<div*minu) {
					ng=0;
					FOR(i,N) {
						if(L[i]*div/l != R[i]*div/l && (L[i]*div/l+1 != R[i]*div/l || R[i]*div%l!=0)) {
							ng=1;
							break;
						}
					}
					if(ng==0) {
						minu=l;
						minl=div;
					}
				}
				div++;
			}
			
			
		}
		return (double)minu/(double)minl;
	}

};

まとめ

結構長いコードになってしまった。
もう一度書き直したらだいぶ縮まりそう。

最近浮動小数点の誤差ミスが怖くて、できるだけ分数の形で保持するようになってしまった。