kmjp's blog

競技プログラミング参加記です

Codeforces #705 Div2 : F. Enchanted Matrix

考え方はそこまで難しくない。
https://codeforces.com/contest/1493/problem/F

問題

N*Mのグリッドがあり、各セルに整数値が書かれている。
ここで、2つの同じサイズでoverlapしない矩形範囲を指定し、中身の整数値が一致するかを判定するクエリを一定回数利用できるとする。

N*Mのグリッドを、同じサイズの複数のグリッドに分割したとき、分割後の全グリッドが同じ整数値の並びとなるようにしたい。
そのようなグリッドのサイズは何通りか。

解法

条件を満たす最小のグリッドを求めれば、縦横それぞれそのグリッドの倍数かつN・Mの約数である大きさはすべて条件を満たす。
よって条件を満たす最小のグリッドを求めよう。

これは縦横それぞれ行うことができる。
例えば縦幅について、2・3・4…と小さい順に分割してみて、同じ内容のグリッドに分割できるか見て行けばよい。
同様に横幅についても分割していく。

int H,W;

int ask(int h,int w,int y1,int x1,int y2,int x2) {
	cout<<"? "<<h<<" "<<w<<" "<<(y1+1)<<" "<<(x1+1)<<" "<<(y2+1)<<" "<<(x2+1)<<endl;
	cin>>h;
	return h;
}

int sph(int th,int step) {
	int cur=1;
	while(cur<step){
		int add=min(cur,step-cur);
		if(ask(add*th,W,0,0,cur*th,0)==0) return 0;
		cur+=add;
	}
	return 1;
}
int spw(int tw,int step) {
	int cur=1;
	while(cur<step){
		int add=min(cur,step-cur);
		if(ask(H,add*tw,0,0,0,cur*tw)==0) return 0;
		cur+=add;
	}
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	int c=H;
	int GH=H,GW=W;
	for(i=2;i<=H;i++) {
		int ok=1;
		int num=i;
		while(c%i==0) {
			if(ok&&sph(H/num,i)) GH=__gcd(GH,H/num);
			else ok=0;
			
			num*=i;
			c/=i;
		}
	}
	c=W;
	for(i=2;i<=W;i++) {
		int ok=1;
		int num=i;
		while(c%i==0) {
			if(ok&&spw(W/num,i)) GW=__gcd(GW,W/num);
			else ok=0;
			num*=i;
			c/=i;
		}
	}
	
	x=y=0;
	for(i=1;i<=H;i++) if(i%GH==0&&H%i==0) x++;
	for(i=1;i<=W;i++) if(i%GW==0&&W%i==0) y++;
	
	cout<<"! "<<(x*y)<<endl;
	
	
}

まとめ

クエリ回数にlogがついてるけど、想定解法は二分探索ではないんだよな。