Good Bye 2024: 2025 is NEAR : F. Earnest Matrix Complement

ようやくCodeforces2024年最後の回。
https://codeforces.com/contest/2053/problem/F

問題

N*Mの行列Aが与えられる。
各要素は1～Kの値を取るが、一部の値は未定である。
未定の場所に任意の整数を入れる場合、美しさの最大値を答えよ。
美しさとは、C(u,i)をi行目における値uの頻度としたとき、C(u,i)*C(u,i+1)の総和とする。

解法

各行において、未定の場所に埋める値はそろえるのが良い。
その際、1つ上または下に現れる値を入れるのがいいので、それらを総当たりし、美しさの増分の最大値を求めよう。

問題は、上の行からDPした時、1つ上の行には現れないが、2つ以上上の行から同じ値を埋めてくるケースの数え忘れである。
そのため、全行同じ値で埋めた場合の増分と合わせて数えて行くとよい。

int T;
int H,W,K;
vector<int> A[202020];
ll F[202020];
ll C[606060];
ll dp[606060];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>H>>W>>K;
		K+=2;
		FOR(i,K) {
			C[i]=dp[i]=0;
		}
		
		ll ret=0;
		FOR(y,H) {
			A[y].resize(W);
			F[y]=0;
			if(y) {
				FOR(x,W) C[A[y-1][x]]++;
			}
			FOR(x,W) {
				cin>>A[y][x];
				if(A[y][x]==-1) {
					A[y][x]=0;
					F[y]++;
				}
				else {
					ret+=C[A[y][x]];
				}
			}
			if(y) {
				FOR(x,W) C[A[y-1][x]]--;
			}
		}
		ll common=0;
		ll ma=0;
		FOR(y,H) {
			if(y) FOR(x,W) if(A[y-1][x]) C[A[y-1][x]]++;
			if(y+1<H) FOR(x,W) if(A[y+1][x]) C[A[y+1][x]]++;
			vector<int> cand={0};
			if(y) FOR(x,W) if(A[y-1][x]) cand.push_back(A[y-1][x]);
			if(y+1<H) FOR(x,W) if(A[y+1][x]) cand.push_back(A[y+1][x]);
			ll ncommon=0;
			if(y) ncommon=1LL*F[y-1]*F[y];
			ll nma=ma;
			FORR(a,cand) if(a==0||C[a]) {
				ll nv=C[a]*F[y];
				dp[a]=max({dp[a],dp[0],ma-ncommon})+nv;
				nma=max(nma,dp[a]);
				C[a]=0;
			}
			common+=ncommon;
			ma=nma;
			if(y) FOR(x,W) if(A[y-1][x]) C[A[y-1][x]]=0;
			if(y+1<H) FOR(x,W) if(A[y+1][x]) C[A[y+1][x]]=0;
		}
		ma=0;
		FOR(i,K) ma=max(ma,dp[i]);
		cout<<ret+ma+common<<endl;
	}
}

まとめ

ようやく2025年に入るか…。