kojingharangの日記

Facebook Hacker Cup Round1 C - Dead Pixels

19:32 |

• W * H ピクセルのモニターがあって N 個のピクセル (x[i], y[i]) が壊れている。P * Q の画像が正しく表示できるような位置は何個あるかを計算する問題。
• x[i], y[i] は次の漸化式で与えられる。x[0]=X, y[0]=Y, x[i]=(x[i-1] * A + y[i-1] * B + 1) % W, y[i]=(x[i-1] * C + y[i-1] * D + 1) % H (for 0 < i < N)
• 1≦W,H≦40000, 1≦P≦W, 1≦Q≦H, 1≦N≦min(10^6, W*H), 0≦X,Y＜W, 1≦A,B,C,D≦100

• パラメータ多いな

• 壊れたピクセルの位置に対して、画像が置けないような画像左上の座標セットが決まる。そこが重複する場合をなんとかすればよさそう
• 大きさ H の配列に、あと何ピクセル右までだめかを保持しておいて、x=0 から x=W+P-1 まで縦の走査線を横にずらしていく感じ。
• 壊れてるピクセルを x 座標でソートして、現在の走査線から始まるやつについて、だめな y の範囲に対して max(現状のだめ数, 横にあと何ピクセルだめか) で更新する
• 走査線が変わったら、だめ数を 1 ずつ減らす。
• だめ数＞0 ならそのピクセルはだめ
• メモリO(H) 時間 O(WH+NH) くらい
• 最大ケースを 20 個流して -O3 で 4 分くらいで終わることが確認できたので submit

• Accepted

// X in [x0, x1]
// Y in [y0, y1]
struct Rect {
	int x0, y0, x1, y1;
	bool operator<(const Rect& o) const {
		return x0<o.x0;
	}
};

ostream& operator<<(ostream& os, const Rect& r) {
	os<<"[Rect "<<r.x0<<" "<<r.y0<<" "<<r.x1<<" "<<r.y1<<" ]";
	return os;
}

int W, H, P, Q, N, X, Y, A, B, C, D;

int foo() {
	vector<Rect> rects(N);
	int x=X, y=Y;
	REP(i, N) {
		Rect r = (Rect){x-(P-1), y-(Q-1), x, y};
		r.x0 = max(r.x0, 0);
		r.y0 = max(r.y0, 0);
		r.x1 = min(r.x1, W-1);
		r.y1 = min(r.y1, H-1);
		rects[i] = r;
		int nx = (x * A + y * B + 1) % W;
		int ny = (x * C + y * D + 1) % H;
		x = nx; y = ny;
	}
	sort(ALL(rects));
//	cout<<rects<<endl;
	
	ll ng = 0;
	VI line(H);
	int ri=0;
	REP(scanx, W-P+1) {
		REP(y, H-Q+1) line[y] = max(line[y]-1, 0);
		for(;ri<N && rects[ri].x0==scanx;ri++) {
			int wi = rects[ri].x1 - rects[ri].x0 + 1;
			RANGE(y, rects[ri].y0, rects[ri].y1+1) {
				line[y] = max(line[y], wi);
			}
		}
		REP(y, H-Q+1) ng += line[y] ? 1 : 0;
	}
	int ans = (W-P+1)*(H-Q+1) - ng;
	return ans;
}

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		cin>>W>>H>>P>>Q>>N>>X>>Y>>A>>B>>C>>D;
		
		int r1 = foo();
		
		cout<<"Case #"<<ttt+1<<": "<<r1<<endl;
	}
	return 0;
}

ツイートする