Hatena::Grouptopcoder

tsubosakaの日記

2009-06-19

SRM 442 Div 1 Medium

| 06:44

ちょっと違うけど、大体規則的に並んだタイルの左上の座標と右下の座標が与えられた時に含まれるタイルの模様を求めよという問題。

基本的に真ん中の合計と四隅の合計をO(1)で求めて、残りの端の4箇所をループでまわして合計を求めればいい。ただし縦長と横長のときに場合分けを行ったり、mod 5が0のときに開始点を変えなければならないとか非常にめんどう。

さらに個数をちゃんと求められていても1*5のタイルが何個あるかを数え上げるルーチンを間違えると死亡する。

public class BedroomFloor {
  long num(long count[]) {
    long total = 0;
    total = count[5];
    total += count[4];
    count[1] -= count[4];
    total += count[3];
    if(count[2] >= count[3]){
      count[2] -= count[3];
    }else{
      count[1] -= 2 * (count[3] - count[2]);
      count[2] = 0;
    }    
    if(count[2] > 0){
      long n = (count[2] + 1) / 2;
      count[1] -= 5 * n - 2 * count[2];
      total += n;
    }    
    if(count[1] > 0){
      total += (count[1] + 4) / 5;
    }
    return total;
  }

  public long numberOfSticks(int x1, int y1, int x2, int y2) {
    long count[] = new long[6];
    long x1g = x1 / 5;
    long y1g = y1 / 5;
    long x2g = (x2 - 1) / 5;
    long y2g = (y2 - 1) / 5;
    if (x1g == x2g && y1g == y2g) {
      plus(x1, y1, x2, y2, count);
    } else if (x1g == x2g) {
      long ys = y1 % 5 == 0 ? y1 : (y1g + 1) * 5;
      long ye = y2 % 5 == 0 ? y2 : y2g * 5;
      for (long y = ys; y < ye; y += 5) {
        plus(x1, y, x2, y + 5, count);
      }
      plus(x1, y1, x2, ys, count);
      plus(x1, ye, x2, y2, count);
    } else if (y1g == y2g) {
      long xs = x1 % 5 == 0 ? x1 : (x1g + 1) * 5;
      long xe = x2 % 5 == 0 ? x2 : x2g * 5;
      for (long x = xs; x < xe; x += 5) {
        plus(x, y1, x + 5, y2, count);
      }
      plus(x1, y1, xs, y2, count);
      plus(xe, y1, x2, y2, count);
    } else {
      long xs = x1 % 5 == 0 ? x1 + 5 : (x1g + 1) * 5;
      long xe = x2 % 5 == 0 ? x2 - 5 : x2g * 5;
      long ys = y1 % 5 == 0 ? y1 + 5 : (y1g + 1) * 5;
      long ye = y2 % 5 == 0 ? y2 - 5 : y2g * 5;
      count[5] += (ye - ys) * (xe - xs) / 5;
      for (long x = xs; x < xe; x += 5) {
        plus(x, y1, x + 5, ys, count);
        plus(x, ye, x + 5, y2, count);
      }
      for (long y = ys; y < ye; y += 5) {
        plus(x1, y, xs, y + 5, count);
        plus(xe, y, x2, y + 5, count);
      }
      plus(x1, y1, xs, ys, count);
      plus(x1, ye, xs, y2, count);
      plus(xe, y1, x2, ys, count);
      plus(xe, ye, x2, y2, count);
    }
    return num(count);
  }

  void plus(long x1, long y1, long x2, long y2, long count[]) {
    if (x1 >= x2)
      return;
    if (y1 >= y2)
      return;
    long xs = x1 / 5;
    long ys = y1 / 5;
    int xd = (int) (x2 - x1);
    int yd = (int) (y2 - y1);
    if ((xs + ys) % 2 == 0) {
      count[xd] += yd;
    } else {
      count[yd] += xd;
    }
  }
}