SRM 542 250pt : PatrolRoute

TopCoder

問題概要

[0,X)*[0,Y)(X,Y<4000)から3点選んでA,B,Cとする。このとき、A,B,CのX座標、Y座標はそれぞれ互いに異なる。A->B->C->Aというルートで巡回する。ある地点からある地点まで移動するにはマンハッタン距離に比例した時間がかかる。時間が[minT, maxT]に収まるような3点の選び方は何通りあるか求める問題。

考えたことなど

  • (まず問題を下から眺める。数えゲーか)
  • 比較的読みやすい問題文だ。3点選ぶって順序は関係あるのか？
  • 順序関係ないって書いてあった。確かに三角形だからコストは順序に関係しないか。
  • 制約は4000か。N^2までなら行けるな。N^2*log Nを除外して考えてよいと言ってるようなもんだな。
  • マンハッタン距離だしXとY独立に考えてよさげ？行けそうだ。
  • Xの総移動時間とYの総移動時間をそれぞれ独立に計算して、片方を全探索しながらもう片方の区間和をとって掛け合わせればよさそう。BIT？いやいやオンライン性必要ないし累積和で十分。
  • 後は総移動時間を最初に数え上げるだけだな。まずは全探索がN^3。これは無理だけど計算量1個くらい簡単に落とせそう。
  • 絶対値ついてるから面倒だけど、上端と下端考えれば真ん中はどこにあっても関係ない。何かこれと似た問題前にも見たなー(後になって調べてみたらAlternatingLaneがそれで、しかもwriter同じ人だった)。
  • ということは上端と下端を全探索すればN^2で行けるなー。頑張れば線形で行けそうな気もするけど、N^2で十分なのでスルー。
  • よし書き始めるかー。
  • 書けた。実行。全然違う値が返ってくる。
  • 配列の領域外参照してた。修正。こんどはまともな値だけど足りてない。何で？
  • あ、XとYそれぞれ選んで点の作り方が3!通りあるのか。よし6倍しよう。もしかしてこれオーバーフローしませんかね。撃墜ポイント？
  • 修正。まだ足りない。何で？
  • あ、上端と下端選んだとき真ん中の選び方に自由度があるの忘れてた。
  • 修正。サンプル全部通ったので提出する。
  • 130点台で絶望的な気分になった。
  • そして6倍するところではオーバーフローしないらしいことを確認。最後のサンプル強そうだしこれ落ちようがないんじゃ…。

acceptされたコード

#include <algorithm>
using namespace std;

typedef long long int64;

const int64 MOD = (int64)(1e9 + 7);
const int MAX_A = 20000*2;

int64 as[2][MAX_A];
int64 accum[2][MAX_A + 1];

struct PatrolRoute {

	int countRoutes(int X, int Y, int minT, int maxT) {
		for(int i=0; i<X; ++i){
			for(int j=i+2; j<X; ++j){
				as[0][2*(j-i)] = ( as[0][2*(j-i)] + (j-i-1) ) % MOD;
			}
		}
		for(int i=0; i<Y; ++i){
			for(int j=i+2; j<Y; ++j){
				as[1][2*(j-i)] = ( as[1][2*(j-i)] + (j-i-1) ) % MOD;
			}
		}

		for(int k=0; k<2; ++k){
			for(int i=0; i<=MAX_A; ++i){
				accum[k][i+1] = (accum[k][i] + as[k][i]) % MOD;
			}
		}

		int64 ans = 0;

		for(int i=0; i<=maxT; ++i){
			ans += 6 * as[0][i] % MOD * (accum[1][maxT-i+1] - accum[1][max(minT-i, 0)]) % MOD;
			ans = (ans + MOD) % MOD;
		}

		return (int)ans;
	}

};