yukicoder : No.393 2本の竹

すんなり解けてよかった。
http://yukicoder.me/problems/no/393

問題

2本の竹があり、長さはN1,N2である。
ここから、長さがA[i]となる竹をできるだけ多くの数取りたい。
最大何本の竹を取れるか。

解法

短い順に取るのが良いのは当然なので、まずAを昇順ソートしよう。
短い順に竹を取るのであれば、元の2本の竹のうち片方の残りの長さが分かれば、もう片方も一意に定まる。

よって片方の竹の長さをもとに、そのような状態を作れるかDPで探索していこう。
どの状態からも竹を取れなくなったらそこで終了する。

以下のコードは無駄に片方の竹の長さに対し、もう片方の長さを変数に入れている。

int D;
int N1,N2;
int M,A[6060];
int from[101010];
int to[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D;
	while(D--) {
		cin>>N1>>N2>>M;
		FOR(i,M) cin>>A[i];
		sort(A,A+M);
		
		MINUS(from);
		from[N1]=N2;
		for(i=0;i<M;i++) {
			MINUS(to);
			int ok=0;
			for(x=0;x<=N1;x++) if(from[x]>=0) {
				if(x>=A[i]) to[x-A[i]] = max(to[x-A[i]],from[x]), ok++;
				if(from[x]>=A[i]) to[x]=max(to[x],from[x]-A[i]), ok++;
			}
			if(ok==0) {
				_P("%d\n",i);
				break;
			}
			swap(from,to);
		}
		if(i==M) _P("%d\n",M);
		
		
	}
}

まとめ

なんで今回24時間制だったんだろう？
選挙とかの時事ネタでもないし…。