yukicoder : No.1668 Grayscale

これは特に悩まなかった。
https://yukicoder.me/problems/no/1668

問題

H*Wのグリッドがあり、そこに整数値が埋められている。
以下の条件を満たすよう値を変えた場合、登場する値の種類を最小化せよ。

• 同じ値を持つセルは、同じ値に書き換わる。
• 隣接セルが異なる値を持つ場合、変えた後も値は異なる。
• 変える前後で値の大小関係が逆転しない。A→X、B→Yと書き換えるとき、A＜BならX≦Yを満たす。

解法

値の小さい順に定めていく。
今、ある値Aを持つセルの値をどうするか考える。

• Aに隣接する、もともとA未満の値を持っていたセルの書き換え後の値より大きい
• A未満の値を書き換えたあとの値の最大値以上である。

int H,W,N;
int C[1010][1010];
int D[1010][1010];
vector<pair<int,int>> cand[1010101];
int pat[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>N;
	FOR(y,H) FOR(x,W) {
		cin>>C[y][x];
		cand[C[y][x]].push_back({y,x});
	}
	int ret=0;
	pat[0]=1;
	FOR(i,N+1) if(cand[i].size()) {
		int ma=pat[i-1];
		FORR2(y,x,cand[i]) {
			FOR(j,4) {
				int d[4]={0,1,0,-1};
				int ty=y+d[j];
				int tx=x+d[j^1];
				if(ty<0||ty>=H||tx<0||tx>=W) continue;
				if(C[ty][tx]>=C[y][x]) continue;
				ma=max(ma,D[ty][tx]+1);
			}
		}
		FORR2(y,x,cand[i]) D[y][x]=ma;
		pat[i]=ma;
		ret=max(ret,ma);
	}
	cout<<ret<<endl;
	
}

まとめ

特に悩むことなく、指示通りに行うだけなので、★2.5でもいいんじゃないかなとは思った。