Codeforces #638 Div2 E. Phoenix and Berries

Hackからリカバリした回。
https://codeforces.com/contest/1348/problem/E

問題

N個の木があり、それぞれA[i]個の赤い実とB[i]個の青い実がなっている。
今、K個の実が入るカゴにこれらを詰めていきたい。
ただし、

• 中身の実の色がすべて同じ
• 中身の実がすべて同じ木から採ったもの

の少なくとも片方は満たさなければならない。

K個の実が入ったカゴを何個作ることができるか。

解法

K個に満たないカゴに赤青両方の実を混ぜてしまうと以後他の木の実を追加できないので、余った実は色ごとに別々のカゴに入れておくとする。

f(i,a,b) := i番目の木まで考えたとき、赤い実がa個、青い実がb個残っているときのK個満たされたカゴの数
とし、i+1番目の木について、赤青何個余らせていくかを考えることができる。
ただしこれだとO(NK^4)かかりTLEする。

よく考えると、実の総数とaとK個満たされたカゴの数がわかればbは自明なので、bは明に状態を持たなくてもよい。
そうするとO(NK^2)まで計算量を落とせる。

int N,K;
int A,B;

ll from[505];
ll to[505];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	FOR(x,505) FOR(y,505) from[x]=-1LL<<60;
	from[0]=0;
	
	int sum=0;
	FOR(i,N) {
		cin>>A>>B;
		FOR(x,505) to[x]=-1LL<<60;
		FOR(x,K) {
			y=(sum-x)%K;
			if(y<0) y+=K;
			FOR(j,K) {
				if(j>A) continue;
				k=(A+B-j)%K;
				if(k>B) continue;
				int add=(A+B-j-k)/K;
				//cout<<x<<" "<<from[x]<<" "<<y<<" "<<j<<k<<" "<<add<<" "<<((x+j)>=K)<<" "<<((y+k)>=K)<<endl;
				to[(x+j)%K]=max(to[(x+j)%K],from[x]+add+((x+j)>=K)+((y+k)>=K));
			}
			
		}
		(sum+=A+B)%=K;
		swap(from,to);
		/*
		FOR(x,K) cout<<from[x]<<" ";
		cout<<endl;
		*/
	}
	
	ll ma=0;
	FOR(i,K) ma=max(ma,from[i]);
	cout<<ma<<endl;
}

まとめ

そんな変なカゴの詰め方の条件ある…？