SRM 256 DIV1 Hard ImageRepeat
問題
最大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; } };