kmjp's blog

競技プログラミング参加記です

yukicoder : No.710 チーム戦

なかなか時間通りに参加することが難しいですね。
https://yukicoder.me/problems/no/710

問題

N個の問題を2人で解くことを考える。
1つの問題はいずれか1人しか解くことができない。
また、1人は同時に1つの問題しか解けない。

i問目を解く時間がそれぞれA[i]、B[i]かかる場合、最適な配分をしたときに全問解き終わる最短時間を求めよ。

解法

以下を考える。
f(i,x) := i問目までのうち何問かを1人目が解いた場合の合計時間がxである場合、残りを2人目が解いたときの最短時間
これをメモ化再帰なりDPなりで埋めていけばよい。
最終的にmax(f(N,x),x)の最小値が解。
状態としてはO(N^2*max(A,B))程度なので、何とか間に合う。

int N;
int A[101],B[101];

int from[101010];
int to[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,101000) from[i]=1<<30;
	from[0]=0;
	
	FOR(i,N) {
		cin>>A[i]>>B[i];
		FOR(j,101000) to[j]=1<<30;
		FOR(j,100001) {
			to[j+A[i]]=min(to[j+A[i]],from[j]);
			to[j]=min(to[j],from[j]+B[i]);
		}
		
		
		swap(from,to);
	}
	
	int mi=1<<30;
	FOR(i,101000) mi=min(mi,max(i,from[i]));
	cout<<mi<<endl;
	
}

まとめ

No.709の方が難しいかも?