AOJ 2427: ほそながいところ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2427

全探索といえばこの問題だよね。

最初を除いたどの馬車も最小値をとりうる場合、次のうち二つの条件のうちどちらかを満たします。
1.終点or少し広いところで交わるほかの馬車が存在する。
2.1分前に出発した馬車が存在する。

なので最初の馬車から始めて、再帰的に全探索を行います。
ある時点ですでに見た馬車の集合Uに対して、Uに属さない馬車vを1つ選び、
Uに属する馬車と1or2の条件を満たすようにします。そしてUに属するほかの馬車とも矛盾が生じないか確認して、Uにvを追加します。これを繰り返せば馬車たちの出発時刻として成立し、最小値をとりうるするものをすべて列挙できます。
オーダーはよくわからないですがAOJで0.00sなので高速です。

ll dist; int N, M;
ll S[10], D[10];
ll ans;

vpl check(int v, const vl& b, vpl cross) {
	ll prev = 0;
	rep(i, 1, N) {
		if(b[i] == -1) continue;
		if(prev >= b[i]) return vpl();
		prev = b[i];
	}
	//cross
	rep(i, 0, N) {
		if(i == v || b[i] == -1) continue;
		ll s1 = S[v], s2 = S[i];
		ll b1 = b[v], b2 = b[i];
		if(v < i) { //b1 < b2
			if(s1 - s2 > 0 && b2 - b1 < dist * (s1 - s2)) {
				if((b2 - b1) % (s1 - s2) != 0) return vpl();
				ll d = (b2 - b1) / (s1 - s2);
				ll t = (s1 * b2 - s2 * b1) / (s1 - s2);
				//debug("check", b, d, res);
				bool ok = false;
				rep(j, 0, M) { 
					if(d == D[j]) {
						if(count(all(cross), pl(t, d))) return vpl();
						else {
							cross.pb(pl(t, d));
							ok = true; break;
						}
					}
				}
				if(!ok) return vpl();
			}
		}
		else { //b1 > b2
			if(s2 - s1 > 0 && b1 - b2 < dist * (s2 - s1)) {
				if((b1 - b2) % (s2 - s1) != 0) return vpl();
				ll d = (b1 - b2) / (s2 - s1);
				ll t = (s2 * b1 - s1 * b2) / (s2 - s1);
				//debug("check", b, d, res);
				bool ok = false;
				rep(j, 0, M) {
					if(d == D[j]) {
						if(count(all(cross), pl(t, d))) return vpl();
						else {
							cross.pb(pl(t, d));
							ok = true; break;
						}
					}
				}
				if(!ok) return vpl();
			}
		}
	}
	return cross;
}

void loop(vl b, vpl cross) { //b = {0, -1, -1, -1, -1} beginning
	bool found = false;
	//debug(b, cross);
	rep(v, 0, N) {
		if(b[v] == -1) {
			rep(j, 0, N) {
				if(b[j] == -1) continue;
				//start
				if(j + 1 == v) {
					b[v] = b[j] + 1;
					vpl newcross = check(v, b, cross);
					if(!newcross.empty()) loop(b, newcross);
					b[v] = -1;
				}
				//cross
				rep(k, 0, M) {
					ll t = D[k] * S[j] + b[j];
					ll tmp = t - D[k] * S[v];
					if(tmp > 0) {
						b[v] = tmp;
						vpl newcross = check(v, b, cross);
						if(!newcross.empty()) loop(b, newcross);
						b[v] = -1;
					}
				}
				//end
				ll t = dist * S[j] + b[j];
				ll tmp = t - dist * S[v];
				if(tmp > 0) {
					b[v] = tmp;
					vpl newcross = check(v, b, cross);
					if(!newcross.empty()) loop(b, newcross);
					b[v] = -1;
				}
			}
			found = true;
		}
	}
	if(!found) {
		ll tmp = 0;
		rep(i, 0, N) MAX(tmp, dist * S[i] + b[i]);
		MIN(ans, tmp);
	}

}

void solve() {
	cin >> dist;
	cin >> N;
	rep(i, 0, N) cin >> S[i];
	cin >> M;
	rep(i, 0, M) cin >> D[i];
	ans = linf;
	vl vec(N, -1); vec[0] = 0;
	loop(vec, vpl(1, pl(-1, -1)));
	cout << ans << "\n";
}

実践的プログラミング結構エグイね。