AtCoder ABC #290 (Toyota Programming Contest 2023 Spring Qual B) : Ex - Bow Meow Optimization

実装は軽いんだけどね。
https://atcoder.jp/contests/abc290/tasks/abc290_h

問題

N匹の犬とM匹の猫がおり、それぞれのパラメータが与えられる。
これらの犬と猫を合わせて横1列に並べたとする。

• 各犬の不満度は、左右にいる猫の数の差の絶対値に、自身のパラメータを掛けた値
• 各猫の不満度は、左右にいる犬の数の差の絶対値に、自身のパラメータを掛けた値

となるとき、適切な並べ方をしたときの不満度の総和の最小値を求めよ。

解法

犬猫合わせて、パラメータの小さい順に列の左右いずれか外側から埋めて行くとよい。
今まで見た中で、左側に埋めた犬・猫の数が何匹か、を状態とし、DPしていこう。

int N,M;
ll A[303],B[303];

ll from[155][155];
ll to[155][155];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	FOR(i,M) cin>>B[i];
	sort(A,A+N);
	sort(B,B+M);
	
	ll ret=0;
	if(N%2==1) {
		if(M%2==1) ret+=A[N-1];
		FOR(i,M) ret+=B[i];
		N--;
	}
	if(M%2==1) {
		FOR(i,N) ret+=A[i];
		M--;
	}
	vector<pair<int,int>> cand;
	FOR(i,N) cand.push_back({A[i],0});
	FOR(i,M) cand.push_back({B[i],1});
	sort(ALL(cand));
	FOR(x,152) FOR(y,152) from[x][y]=1LL<<60;
	from[0][0]=0;
	int D=0,C=0;
	FORR2(v,i,cand) {
		FOR(x,152) FOR(y,152) to[x][y]=1LL<<60;
		FOR(x,152) FOR(y,152) {
			if(i==0) {
				//前半
				chmin(to[x+1][y],from[x][y]+1LL*v*(M-2*y));
				//後半
				chmin(to[x][y],from[x][y]+1LL*v*(M-2*(C-y)));
			}
			else {
				//前半
				chmin(to[x][y+1],from[x][y]+1LL*v*(N-2*x));
				//後半
				chmin(to[x][y],from[x][y]+1LL*v*(N-2*(D-x)));
			}
		}
		if(i==0) D++;
		else C++;
		swap(from,to);
	}
	
	
	cout<<ret+from[N/2][M/2]<<endl;
	
}

まとめ

結果だけ聞くと簡単な考察だけど、これを本番中自信をもって通すのは難しそう。