cafelier@SRM

SRM442 550

あとで | 12:59 |

とりあえず通るには通ったけど、こんなもの*絶*対*に*ミスなく書けるわけがないし、解けたとはいえない…。どうしたものかな。x方向の分割とy方向の分割を分離して3分割を2段みたいな書き方をしたら少しはマシになるだろうか。

typedef long long LL;

class BedroomFloor { public:
  long long numberOfSticks(int x1, int y1, int x2, int y2) 
  {
    #define F(x) ((x)/5*5) // floor
    #define C(x)  F((x)+4) // ceil

    LL b[6] = {};
    if( F(x1)==F(x2) )
      if( F(y1)==F(y2) )
      {
        count_s(x1, x2, y1, y2, b);
      }
      else
      {
        count_s (x1, x2,   y1,  C(y1), b);
        count_my(x1, x2, C(y1), F(y2), b);
        count_s (x1, x2, F(y2),   y2 , b);
      }
    else
      if( F(y1)==F(y2) )
      {
        count_s(x1, C(x1), y1, y2, b);
        //
        count_mx(C(x1), F(x2), y1, y2, b);
        //
        count_s(F(x2), x2, y1, y2, b);
      }
      else
      {
        count_s (  x1 , C(x1),   y1,  C(y1), b);
        count_my(  x1 , C(x1), C(y1), F(y2), b);
        count_s (  x1 , C(x1), F(y2),   y2 , b);
        //
        count_mx(C(x1), F(x2),   y1,  C(y1), b);
        count_l (C(x1), F(x2), C(y1), F(y2), b);
        count_mx(C(x1), F(x2), F(y2),   y2 , b);
        //
        count_s (F(x2),   x2 ,   y1 , C(y1), b);
        count_my(F(x2),   x2 , C(y1), F(y2), b);
        count_s (F(x2),   x2 , F(y2),   y2 , b);
      }
    return optimize(b[1], b[2], b[3], b[4], b[5]);
  }

  bool is_horizontal(LL x, LL y)
  {
    return x/5%2 == y/5%2;
  }

  void count_s(LL x1, LL x2, LL y1, LL y2, LL b[])
  {
    if( is_horizontal(x1, y1) )
      b[x2-x1] += y2-y1;
    else
      b[y2-y1] += x2-x1;
  }

  void count_my(LL x1, LL x2, LL y1, LL y2, LL b[])
  {
    LL n=(y2-y1)/5, n1=n/2,  n2=(n+1)/2;
    b[x2-x1] +=       5 * (is_horizontal(x1,y1) ? n2 : n1);
    b[5]     += (x2-x1) * (is_horizontal(x1,y1) ? n1 : n2);
  }

  void count_mx(LL x1, LL x2, LL y1, LL y2, LL b[])
  {
    LL n=(x2-x1)/5, n1=n/2,  n2=(n+1)/2;
    b[y2-y1] +=       5 * (is_horizontal(x1,y1) ? n1 : n2);
    b[5]     += (y2-y1) * (is_horizontal(x1,y1) ? n2 : n1);
  }

  void count_l(LL x1, LL x2, LL y1, LL y2, LL b[])
  {
    b[5] += ((x2-x1)/5) * ((y2-y1)/5) * 5;
  }

  LL optimize( LL b1, LL b2, LL b3, LL b4, LL b5 )
  {
    LL total = 0;
    for(int k=6*6*6*6*6; --k>0; )
    {
      int k1 = k%6;
      int k2 = k/6%6;
      int k3 = k/6/6%6;
      int k4 = k/6/6/6%6;
      int k5 = k/6/6/6/6%6;
      if( 1*k1 + 2*k2 + 3*k3 + 4*k4 + 5*k5 <= 5 )
      {
        LL n = 1LL<<62;
        if(k1) n = min(n, b1/k1);
        if(k2) n = min(n, b2/k2);
        if(k3) n = min(n, b3/k3);
        if(k4) n = min(n, b4/k4);
        if(k5) n = min(n, b5/k5);
        total += n;
        b1 -= n*k1;
        b2 -= n*k2;
        b3 -= n*k3;
        b4 -= n*k4;
        b5 -= n*k5;
      }
    }
    assert( b1==0 && b2==0 && b3==0 && b4==0 && b5==0 );
    return total;
  }
};

再々挑戦。

(x1,y1)-(x2,y2)が同じ5x5に収まるまで分解し尽くすようにしてみた。こんなもんかなあ。

class BedroomFloor { public:
  LL b[6];

  long long numberOfSticks(int x1, int y1, int x2, int y2) 
  {
    b[1] = b[2] = b[3] = b[4] = b[5] = 0;

    devideX_and_count(x1, x2, y1, y2);
    return optimize();
  }

  // utils
  LL FLOOR(LL x) { return x/5*5; }
  LL CEIL (LL x) { return FLOOR(x+4); }

  // counting routines
  void devideX_and_count(LL x1, LL x2, LL y1, LL y2)
  {
    if( FLOOR(x1) == FLOOR(x2) )
      devideY_and_count(x1, x2, y1, y2, 1);
    else
      devideY_and_count(         x1,    CEIL(x1), y1, y2, 1 ),
      devideY_and_count(   CEIL(x1),  CEIL(x1)+5, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+1)/2 ),
      devideY_and_count( CEIL(x1)+5, CEIL(x1)+10, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+0)/2 ),
      devideY_and_count(  FLOOR(x2),          x2, y1, y2, 1 );
  }

  void devideY_and_count(LL x1, LL x2, LL y1, LL y2, LL rep)
  {
    if( FLOOR(y1) == FLOOR(y2) )
      count(x1, x2, y1, y2, rep);
    else
      count(x1, x2,         y1,    CEIL(y1), rep),
      count(x1, x2,   CEIL(y1),  CEIL(y1)+5, rep*(((FLOOR(y2)-CEIL(y1))/5+1)/2) ),
      count(x1, x2, CEIL(y1)+5, CEIL(y1)+10, rep*(((FLOOR(y2)-CEIL(y1))/5+0)/2) ),
      count(x1, x2,  FLOOR(y2),         y2 , rep);
  }

  void count(LL x1, LL x2, LL y1, LL y2, LL rep)
  {
    if( x1/5%2 == y1/5%2 ) // is_horizontal
      b[x2-x1] += rep*(y2-y1);
    else
      b[y2-y1] += rep*(x2-x1);
  }

  // compute minimum number of 1x5 blocks required (by greedily removing larger blocks)
  LL optimize()
  {
    LL total = 0;
    for(int K=6*6*6*6*6; --K>0; )
    {
      int k[] = {-1, K%6, K/6%6, K/6/6%6, K/6/6/6%6, K/6/6/6/6%6};
      if( 1*k[1] + 2*k[2] + 3*k[3] + 4*k[4] + 5*k[5] <= 5 )
      {
        LL n = 1LL<<62;
        for(int i=1; i<=5; ++i)
          if( k[i] )
            n = min(n, b[i]/k[i]);
        for(int i=1; i<=5; ++i)
          b[i] -= n*k[i];
        total += n;
      }
    }
    return total;
  }
};