AtCoder ABC #269 (UNICORNプログラミングコンテスト2022) : G - Reversible Cards 2

Gまでは割と順調だったんだけど。
https://atcoder.jp/contests/abc269/tasks/abc269_g

問題

N枚のカードがあり、それぞれ表面には非負整数A[i]、裏面には非負整数B[i]が書かれている。
表面で並べられたカードに対し、何枚か裏返して表面に来た値の総和をKとするようにしたい。
K=0....Mそれぞれに対し、裏返す必要な最小枚数を求めよ。(Mはカードの両面に書かれた整数値の総和とする)

解法

初期状態で総和をS=sum(A)とし、その後各カードを裏返すと差分B[i]-A[i]だけ総和が変化すると考える。
f(d) := 差分の和がdとなるような裏返し枚数の最小値(ただし達成不可なら無限大)
とする。f(d)を列挙できれば、Kに対し、f(K-S)を答えればよいことになる。

あとはf(d)を考えよう。
カードごとにDPを行ってしまうと、O(NM)かかってします。
そこで、差分が同じカードをまとめて扱うことにし、個数上限付きナップサックに似た要領で処理することにすると差分のバリエーションはO(√M)程度しかないのでO(M^1.5)で済む。

int N,M;
int A[202020],B[202020],C[404040];
int D[404040];
const int E=202020;
deque<pair<int,int>> Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	int S=0;
	
	FOR(i,N) {
		cin>>A[i]>>B[i];
		if(A[i]!=B[i]) C[B[i]-A[i]+E]++;
		S+=A[i];
	}
	FOR(i,404040) D[i]=1<<30;
	D[E]=0;
	FOR(i,404040) if(C[i]) {
		int d=i-E;
		int e=C[i];
		if(d>0) {
			FOR(j,d) {
				Q.clear();
				for(x=j;x<404040;x+=d) {
					if(D[x]<1<<30) {
						y=D[x];
						k=y-x/d;
						while(Q.size()&&Q.back().second>=k) Q.pop_back();
						Q.push_back({x,k});
					}
					if(Q.size()&&Q.front().first+e*d<x) Q.pop_front();
					if(Q.size()) D[x]=min(D[x],Q.front().second+x/d);
				}
			}
		}
		else {
			d=-d;
			FOR(j,d) {
				Q.clear();
				for(x=404040-1-j;x>=0;x-=d) {
					if(D[x]<1<<30) {
						y=D[x];
						k=y+x/d;
						while(Q.size()&&Q.back().second>=k) Q.pop_back();
						Q.push_back({x,k});
					}
					if(Q.size()&&Q.front().first-e*d>x) Q.pop_front();
					if(Q.size()) D[x]=min(D[x],Q.front().second-x/d);
				}
			}
		}
	}
	
	FOR(i,M+1) {
		int d=i-S;
		if(D[d+E]>=1<<30) {
			cout<<-1<<endl;
		}
		else {
			cout<<D[d+E]<<endl;
		}
	}
	
	
}

まとめ

これは解法もすんなり思いつけたね。