SRM 256 DIV1 Hard ImageRepeat

問題 Editorial

問題

最大50*50の画像が2つ(imageA, imageB)ある。
両方の画像で共通する正方形の最大サイズを求めよ

解答

(サイズ*Aの左上座標*Bの左上座標)全探索。
両方の領域が等しいかの判定にハッシュを使った。
O(n^5)だが、サイズ毎に座標の範囲が制限されるのと、最内の処理の軽さでわりと速い。
他にもDPしたり色々な解法があるようだ

コメント

ハッシュは初めて使ってみた。一回ハッシュの衝突でFailしてしまった。
ハッシュのサイズを64bitに変えたら通ったけれど、やり方はこれでいいのかわからない

コード

#include <string>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef vector<string> vs; typedef unsigned long long ull;
struct ImageRepeat {
	void calc_hash(vs a, ull h[55][55][55]) {
		int H = a.size(), W = a[0].size();
		h[0][0][0] = 0;
		rer(size, 1, 50) rer(y, 0, H-size) rer(x, 0, W-size) {
			ull t = h[size-1][y][x];
			rep(i, size) t = (t * 1234567891 + 9876543 + a[y+size-1][x+i]);
			rep(i, size) t = (t * 1234567891 + 9876543 + a[y+i][x+size-1]);
			h[size][y][x] = t;
		}
	}
	int largestSize(vector <string> imageA, vector <string> imageB) {
		static ull hashA[55][55][55], hashB[55][55][55];
		calc_hash(imageA, hashA); calc_hash(imageB, hashB);
		int hA = imageA.size(), wA = imageA[0].size();
		int hB = imageB.size(), wB = imageB[0].size();
		int N = min(min(hA, wA), min(hB, wB));
		int r = 0;
		rer(k, 1, N) {
			ull (*aA)[55] = hashA[k], (*aB)[55] = hashB[k];
			rer(yA, 0, hA-k) rer(xA, 0, wA-k)
			rer(yB, 0, hB-k) rer(xB, 0, wB-k) if(aA[yA][xA] == aB[yB][xB]) r = k;
		}
		return r;
	}
};