AtCoder ARC #105 : C - Camels and Bridge

苦手な感じの問題セット。
https://atcoder.jp/contests/arc105/tasks/arc105_c

問題

N体のラクダを1列に並べて橋を渡る。
ラクダ間の間隔は任意に指定でき、その間隔を維持したまま全体が移動するとする。
橋はM個のパーツが順に並んだ形状となっており、各パーツiの長さL[i]と耐荷重V[i]が与えられる。
パーツ上に耐荷重を超える総重量のラクダ群が通ると橋が崩落してしまう。

個々のラクダの重量W[i]が与えられているとき、橋が崩落しないようなラクダ列の先頭から末尾までの総長の最小値を求めよ。

解法

ラクダの並び順を総当たりしよう。
まず、パーツの条件を重さ順にソートしておき、ある総重量のラクダ列に対し最小でどの程度の長さが必要か求めておこう。
ラクダの部分列に対し、その総重量から上記パーツ列の条件を二分探索すると、その部分列の先頭から末尾までに必要な最小距離がわかる。

あとは、Warshall-Floyedの要領で個々のラクダ間の距離を求めよう。

int N,M;
int W[8];
int L[101010],V[101010];
int D[10][10];
pair<int,int> P[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>W[i];
	ll ma=*max_element(W,W+N);
	FOR(i,M) {
		cin>>L[i]>>V[i];
		if(V[i]<ma) return _P("-1\n");
		P[i]={V[i],L[i]};
	}
	sort(P,P+M);
	for(i=1;i<M;i++) {
		P[i].second=max(P[i].second,P[i-1].second);
	}
	
	int mi=1<<30;
	vector<int> A;
	FOR(i,N) A.push_back(i);
	
	do {
		ZERO(D);
		FOR(x,N) {
			int ls=0;
			for(y=x;y<N;y++) {
				ls+=W[A[y]];
				j=lower_bound(P,P+M,make_pair(ls,0))-P;
				if(j>0) {
					D[x][y]=max(D[x][y],P[j-1].second);
				}
				
				
			}
		}
		
		FOR(i,8) {
			FOR(x,N) for(int z=x+1;z<N;z++) for(y=z+1;y<N;y++) {
				D[x][y]=max(D[x][y],D[x][z]+D[z][y]);
			}
		}
		mi=min(mi,D[0][N-1]);
		
	} while(next_permutation(ALL(A)));
	
	cout<<mi<<endl;
}

まとめ

最初愚直に全パーツ探索したらTLEしてしまった。