AtCoder ABC #298 (トヨタ自動車プログラミングコンテスト2023#1) : G - Strawberry War

解き方はすぐ思いついても実装が割とめんどい。
https://atcoder.jp/contests/abc298/tasks/abc298_g

問題

H*Wのグリッドからなる単一の長方形があり、それぞれ整数が書かれている。
長方形を1つ選び、グリッドの線に沿って2つに分割する、ということをT回行い、(T+1)個の長方形に分割することを考える。
この時、各長方形内の整数値の総和の最大値と最小値の差を最小化したい。
この値を求めよ。

解法

長方形内の整数値の総和の範囲を(多少枝刈りしながら)総当たりすることを考える。
範囲を定めたら、各矩形領域が条件を満たす何個の長方形に分割できるかをbitmaskで持ちながらメモ化再帰で求めて行けばよい。

int H,W,T;
ll A[10][10];
ll S[10][10];
ll memo[11][11][11][11];
ll TL,TR;

ll dfs(int U,int L,int D,int R) {
	if(memo[U][L][D][R]!=-1) return memo[U][L][D][R];
	ll ret=0;
	
	ll sum=S[D][R]-S[D][L]-S[U][R]+S[U][L];
	if(sum>=TL&&sum<=TR) ret|=2;
	for(int y=U+1;y<D;y++) {
		ll a=dfs(U,L,y,R);
		ll b=dfs(y,L,D,R);
		int i;
		FOR(i,37) if(a&(1LL<<i)) ret|=b<<i;
	}
	for(int x=L+1;x<R;x++) {
		ll a=dfs(U,L,D,x);
		ll b=dfs(U,x,D,R);
		int i;
		FOR(i,37) if(a&(1LL<<i)) ret|=b<<i;
	}
	return memo[U][L][D][R]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>T;
	FOR(y,H) FOR(x,W) {
		cin>>A[y][x];
		
		S[y+1][x+1]=S[y+1][x]+S[y][x+1]-S[y][x]+A[y][x];
	}
	vector<ll> cand;
	FOR(y,H) FOR(x,W) {
		for(int y1=1;y+y1<=H;y1++) {
			for(int x1=1;x+x1<=W;x1++) {
				ll sum=S[y+y1][x+x1]-S[y+y1][x]-S[y][x+x1]+S[y][x];
				cand.push_back(sum);
			}
		}
	}
	sort(ALL(cand));
	cand.erase(unique(ALL(cand)),cand.end());
	ll mi=1LL<<60;
	FORR(y,cand) FORR(x,cand) if(y>=x&&y-x<=mi) {
		TL=x;
		TR=y;
		MINUS(memo);
		ll a=dfs(0,0,H,W);

		if(a&(1LL<<(T+1))) {
			mi=min(mi,y-x);
		}
		else {
			break;
		}
	}
	cout<<mi<<endl;
	
	
}

まとめ

本番変数名を間違えて大幅にタイムロスしてしまった…。