AtCoder ARC #186 (AtCoder Japan Open -予選-) : A - Underclued

そこそこ良い結果で良かった。
https://atcoder.jp/contests/arc186/tasks/arc186_a

問題

2つのN次正方行列A,Bが似ているとは、各行の総和がAとBで等しく、各列の総和もAとBで等しいことを意味する。

また、01で構成されるN次正方行列Aの成分A(i,j)が固定されているとは、Aと似ているあらゆるBにおいてA(i,j)=B(i,j)であることを示す。

整数N,Kが与えられる。
01で構成されるN次正方行列Aのうち、固定されている要素がK個になるものが存在するか判定せよ。

解法

固定でない要素がN^2-K個とできるかを考える。
Aのうち幅2以上、高さ2以上の矩形領域を、固定でないようにすることができる。
例えば矩形内のある4要素について、以下のAとBは似ている、すなわちこの4要素は固定でないためである。

• A(r1,c1)=A(r2,c2)=0、A(r1,c2)=A(r2,c1)=1
• B(r1,c1)=B(r2,c2)=1、B(r1,c2)=B(r2,c1)=0

反対の、この矩形領域の存在により、他の部分の固定/非固定が変わらないようにしたい。
そこで、矩形領域をいくつか選び、角を共有するように斜めに並べて、左上端から右下端までつないだと考える。
この時、矩形領域群の下を1、上を0で埋めれば、矩形領域内以外の要素は値を変更できない。

ここまで決まると、後はDPで斜めに並べられる矩形領域の面積の総和がN^2-Kにできるか判定すればよい。

int N,Q;
int ret[9090];

int dp[31][31][959];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	
	dp[0][0][0]=1;
	for(int h=0;h<=N;h++) for(int w=0;w<=N;w++) for(int s=0;s<=h*w;s++) if(dp[h][w][s]) {
		ret[s]=1;
		for(int y2=2;h+y2<=N;y2++) for(int x2=2;w+x2<=N;x2++) dp[h+y2][w+x2][s+y2*x2]=1;
		
	}
	
	
	while(Q--) {
		cin>>x;
		if(ret[N*N-x]) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
		
}

まとめ

ちょっと手間取ったけどまぁ1発で解けて良かったか。