mayoko’s diary

プロコンとかいろいろ。

SRM 542 div1 easy: PatrolRoute

問題

TopCoder Statistics - Problem Statement

点(x1, y1) から点(x2, y2) への距離を |x2-x1|+|y2-y1| と定義する。

0 <= x < X, 0 <= y < Y を満たす長方形の中から, 以下を満たす 3 点 A, B, C を選びたい。

  • A, B, C の x の値は異なる。
  • A, B, C の y の値は異なる。
  • A -> B -> C -> A と一周する長さは minT 以上, maxT 以下でなければならない。

これを満たす (A, B, C) の選び方は何通りあるか。

解法

何個か A -> B -> C -> A のルートを書いてみると, 長方形的なルートばっかりであることに気づきます。長方形にならないルートであっても, 結局 辺を適当に辺を移動させると長方形の周りの長さに一致するようになります。

つまり,
dx = (A, B, C のうち 最大の x 座標) - (A, B, C のうち 最小の x 座標)
dy = (A, B, C のうち 最大の y 座標) - (A, B, C のうち 最小の y 座標)
とすれば, 一周する長さは必ず (dx+dy)*2 となります。

これに気づけば簡単で, dx と dy の長さを X*Y 通りの場合で考えて, それぞれの場合に置いて,

  • x 座標最大, 最小, 真ん中の点の選び方
  • y 座標最大, 最小, 真ん中の点の選び方
  • A, B, C の並べ方

を考慮すれば良いです。

const int MOD = 1e9+7;

class PatrolRoute {
public:
    int countRoutes(int X, int Y, int minT, int maxT) {
        ll ans = 0;
        for (int h = 2; h < Y; h++) {
            for (int w = 2; w < X; w++) {
                if ((h+w)*2 < minT || (h+w)*2 > maxT) continue;
                ll cnt = 6*(X-w)*(Y-h);
                (cnt *= h-1) %= MOD;
                (cnt *= w-1) %= MOD;
                ans += cnt;
            }
        }
        return (int)(ans%MOD);
    }
};