2012-10-31

SRM 559 Div1 250 HyperKnight

12:57 |

チェスのナイトの動きを一般化して (±A, ±B), (±B, ±A) の 8 通りに移動できるとする
盤面 NR x NC があるとして、1回の移動後も盤面にいるような選択肢の数が K 個であるような出発点の数を求める。
K in [0, 8]. NR,NC,A,B in [1, 10**9]

座標圧縮みたいにして 5x5 マスで考える
5x5 のサブエリア[x0, x1] x [y0, y1] (x0, x1, y0, y1 in [0, 4], x0 < x1, y0 < y1)のうち中心が含まれるものを全列挙して、
駒が K 個だったら実際の盤面でそのサブエリアに対応する置き方が何通りあるか数えて足す

/*
□駒□駒□
駒□□□駒
□□×□□
駒□□□駒
□駒□駒□

K=2 になるようなサブエリア例
□■■■□
□■■■□
□■■■□
□□□□□
□□□□□

K=2 になるようなサブエリア例
□□■■■
□□■■■
□□■■■
□□□□□
□□□□□

K=2 になるようなサブエリア例
□□■■□
□□■■□
□□■■□
□□■■□
□□■■□

*/

置き方はx軸y軸に分けて考える

ごりごり書いてたら Sample4 以外通ったけどそこ直したら Sample1 が通らなくなってとか繰り返してるうちに終了

（あとで）

圧縮してた座標と範囲を戻す
たとえばサブエリアが占める範囲の最小値は「左部分の幅の最小値 + 1(中央) + 右部分の幅の最小値」

(x0, x1) が (0, 4) のとき（両端で終わってるとき）はどこに置いてもいいしサブエリアの幅は1通りしかないので「幅 - サブエリアの幅 + 1」通り
そうじゃないときは左右どちらかまたは両方が壁に接していないといけないので置く場所は決まってて、有効なサブエリアの幅の範囲数通りになる
サブエリアの幅が盤面に入るかとかチェックもする

(何言ってるかわからなくなってきた)

↓あとで (accepted in practice)

class HyperKnight {
	public:
	long long countCells(int A, int B, int NR, int NC, int K) {
		VVI pat(5, VI(5, 0));
		int eX[] = {0,0,1,1,3,3,4,4};
		int eY[] = {1,3,0,4,0,4,1,3};
		REP(i, 8) pat[eY[i]][eX[i]]=1;
		//cout<<pat<<endl;
		if(B>A) swap(A, B);
		
		ll ans = 0;
		REP(y0, 5) {
			REP(x0, 5) {
				RANGE(y1, y0, 5) {
					RANGE(x1, x0, 5) {
						if(x1<2||2<x0||y1<2||2<y0) continue;
						int co=0;
						RANGE(y, y0, y1+1) RANGE(x, x0, x1+1) co+=pat[y][x];
						//cout<<x0<<" "<<y0<<"   "<<x1<<" "<<y1<<" ++ "<<co<<endl;
						if(co==K) {
							//cout<<x0<<" "<<y0<<"   "<<x1<<" "<<y1<<" --- "<<endl;
							int tb[] = {0, B, A, A+1};
							
							int a0=x0, a1=x1, N=NC;
							ll cc[2];
							int ok=1;
							REP(loop, 2) {
								int i0 = abs(a0-2);
								int i1 = abs(a1-2);
								ll cmin0 = tb[i0];
								ll cmin1 = tb[i1];
								ll cmax0 = tb[i0+1]-1;
								ll cmax1 = tb[i1+1]-1;
								// ながさ in [c0, c1]
								ll c0 = cmin0 + 1 + cmin1;
								ll c1 = cmax0 + 1 + cmax1;
								if(!(i0==2||i1==2)) {
									if(!(c0<=N&&N<=c1)) ok=0;
								}
								if(c0>N) ok=0;
								c1 = min((ll)N, c1);
								//cout<<c0<<" "<<c1<<endl;
								ll c = 0;
								if(i0==2&&i1==2) c = N-c0+1;
								else c = c1-c0+1;
								a0=y0, a1=y1, N=NR;
								cc[loop] = c;
							}
							
							if(ok) {
								ans += cc[0] * cc[1];
								//cout<<x0<<" "<<y0<<"   "<<x1<<" "<<y1<<" --- "<<cc[0]<<" "<<cc[1]<<endl;
							}
						}
					}
				}
			}
		}
		return ans;
	}
};

kojingharangの日記

2012-10-31

SRM 559 Div1 250 HyperKnight