読者です 読者をやめる 読者になる 読者になる

SRM 542 Div2 Medium PatrolRoute

TopCoder Statistics - Problem Statement

問題

X*Yのエリアからなる王国がある.王国上の地点(x1, y1), (x2, y2)について(0 <= x1, x2 <= X, 0 <= y1, y2 <= Y),(x1, y1)から(x2, y2)に移動するには|x1-x2|+|y1-y2|時間がかかる.王国の安全維持のため次の制約からなる3地点A, B, Cをパトロールする.

  • A, B, Cのx座標はすべて異なる.
  • A, B, Cのy座標はすべて異なる.
  • TをAからB, BからC, CからAを移動する時間とすると,TはminT以上maxT以下.

制約を満たす異なるパトロールのルート数を答えよ.
但し,ルートは3地点のいずれかが異なる時,異なるとする.

解答

X, Y<=4000なので全探索をすることが出来ずなかなかに難しい,だがきれいな解き方があり,理解できるとすっきりする.
まず,3地点がわかった時のTの計算について改めて考えよう.3地点のx座標の最小値最大値をxmin, xmax,y座標の最長値最大値をymin, ymaxとするとTは2*(xmax-xmin)+2*(ymax-ymin)で表される.これは(xmin, ymin), (xmax, ymax)を対角にとる四角形の外周に相当する.
2地点を四角形の対角に取った時,条件1,2より3つ目の地点は四角形の内部(xmax-xmin-1)*(ymax-ymin-1)に限定される.上記の条件を満たす3地点がいくつあるのかを考える.3つのx座標とy座標をx1, x2, x3, y1, y2, y3とし組み合わせ数を考えると,x1についてy1, y2,y3の中から3通り,x2について残りの2通り,x3は残りの1通りで計6通りが考えられる.
四角形の縦の長さをa, 横の長さをbとすると四角形の配置の仕方は(Y-a+1)*(X-a+1)通りある.よって条件に合う四角形の縦横の長さを前通り考えて足しあわせれば答えを求めることが出来る.

条件1,2があることでうまい具合に求めることが出来良くできた問題だなと感心する.すごい.

class PatrolRoute
{
public:
  int countRoutes(int X, int Y, int minT, int maxT)
    {
      long long i, j;
      long long mod = 1000000007;
      long long ret = 0;
      for(i = 3; i <= X; i++){
        for(j = 3; j <= Y; j++){
          if (!(minT <= 2*(i-1)+2*(j-1) && 2*(i-1)+2*(j-1) <= maxT)) continue;
        // for(j = max(3ll, (minT-2*(i-1)+1)/2 + 1); j <= Y && 2*(i-1)+2*(j-1) <= maxT; j++){
          long long v = (6 * (i-2) * (j-2)) % mod;
          ret = (ret + v * (X-i+1) * (Y-j+1)) % mod;
        }
      }
      return ret;
    }
};