kojingharangの日記

SRM 542 - 250 PatrolRoute

21:36 |

• ２次元整数座標の範囲(x, y) ただし x in [0, X), y in [0, Y) から x または y が異なる３点を選ぶ。３点をマンハッタン距離で巡回するときの合計距離が [minT, maxT] に収まるような選び方は何通りあるか。

• DP? と思ったけど、範囲が１増えて新しいとこから点を選ぶと距離とか変わっちゃうし、なんかうまくいかなさそう
• ３点のbounding box(minX, minY)-(maxX, maxY)について幅 W 高さ H とすると、合計距離は 2(W+H) になることに気づく（ここがポイントだった）
• bounding box (以下BB)の大きささえ決まってしまえば合計距離が決まる。それが minT～maxT かはわかる
• BB は (0, 0)-(X-1, Y-1) の範囲には (X-W)(Y-H) 通りずらして置ける
• BB 内での点の置き方は...
• 対角線に２つ置いてあとはその中 (W-1)(H-1) に置くパターンが180度回転で一致するので２通り
• 左上の点と、右の辺(H-1)と下の辺(W-1)に１こずつ置くパターンが回転すると４通り
• というわけで BB の幅高さ全通りに対して, minT～maxT なら 6(X-W)(Y-H)(W-1)(H-1) の合計が答え

#define MOD ((ll)1000000007)

class PatrolRoute {
	public:
	int countRoutes(int X, int Y, int minT, int maxT) {
		ll ans = 0;
		for(int W=2;W<X;W++) {
			for(int H=2;H<Y;H++) {
				if( minT <= 2*(W+H) && 2*(W+H) <= maxT ) {
					ll a = (X-W) * (Y-H);
					ll b = (W-1)*(H-1)*6;
					ll lans = a*b;
					//cout<<W<<" "<<H<<" "<<a<<" "<<b+c<<endl;
					ans = (ans + lans) % MOD;
				}
			}
		}
		return ans;
	}
};

ツイートする