TopCoder SRM 442 Div1 Medium BedroomFloor

TopCoder 実装問題

問題

図のような床がある。
（1x5の板が縦に5枚並べた正方形Aと、横に5枚並べた並べた正方形がBが、平面上に
ABABAB
BABABA
ABABAB…
のように無限並んでいる）

この床のx1,y1,x2,y2の長方形の領域を作りたい。
1x5の板はいくつ必要か。


板は好きなように切断することができるが、重ねたり、接合することはできない。

制約条件

x1,y1,x2,y2≦1000000

方針

ひたすら場合分けして、1xXの板がそれぞれ何枚必要かを求める。
それが求まったら、1x5の板からそれらを切り出すには1x5の板が何枚必要かをgreedyに求める。
1x5の板はまるごと買う必要があり、
1x4の板は、1x1の板と出来るだけ組み合わせて買えば良く、
1x3の板はなるべく1x2の板と組み合わせて買ったあと、1x1の板とできるだけ組み合わせて買えばよく、
1x2の板はもう一枚の1x2と1x1とできるだけ組み合わせて買ったあと、1x1三枚と組み合わせて買う。
最後に残った1x1は、5で割って切り上げた枚数だけ1x5を買えば良い。


1xXの板が何枚必要かは、座標が5の倍数の部分と、そうでない部分にわけてそれぞれ求める。
座標が5の倍数の部分とそうでない部分に区切ると対称性から、場合分けが少し減るので楽。


更に、縦の1x5が並んでいる部分から切り出されるか、横の1x5が並んでいる部分から切り出されるかで場合分けする。

ソースコード

vi _(int a,int b){
  vi res;
  res.pb(a);
  if((a+4)/5*5<=b)res.pb((a+4)/5*5);
  if(b/5*5>=a)res.pb(b/5*5);
  res.pb(b);
  return res;
}
vector<ll> calc(int x1,int x2,int y1,int y2){
  if(x1>=x2||y1>=y2)return vector<ll>(5);
  int w=x2-x1, h=y2-y1,p=x1/5+y1/5&1;
  if(x1%5==0&&y1%5==0){
    vector<ll> res(5);
    if(w%5==0&&h%5==0){
      res[4]=w/5ll*h; return res;
    }
    if(w%5==0){
      int yoko=p?w/10:(w/5+1)/2,tate=w/5-yoko;
      res[h-1]=tate*5ll;
      res[4]=(ll)yoko*h;
      return res;
    }
    if(h%5==0){
      int yoko=p?h/10:(h/5+1)/2,tate=h/5-yoko;
      res[w-1]=yoko*5ll;
      res[4]=(ll)tate*w;
      return res;
    }
    if(p)res[h-1]=w;
    else res[w-1]=h;
    return res;
  }
  else if(x2%5==0&&y1%5==0)return calc(x2+5,x2+w+5,y1,y2);
  else if(x1%5==0&&y2%5==0)return calc(x1+5,x2+5,y2,y2+h);
  else if(x2%5==0&&y2%5==0)return calc(x2,x2+w,y2,y2+h);
  
  return p?calc(5,5+w,0,h):calc(0,w,0,h);
}

class BedroomFloor {
  public:
  long long numberOfSticks(int x1, int y1, int x2, int y2) {
    vi x=_(x1,x2), y=_(y1,y2);
    vector<ll> v(5);
    rep(i,x.size()-1)rep(j,y.size()-1){
      vector<ll> t=calc(x[i],x[i+1],y[j],y[j+1]);
      rep(k,5)v[k]+=t[k];
    }
    //rep(i,5)cerr<<v[i]<<(i==4?"\n":" ");
    
    ll ans=v[4]+v[3];
    v[0]=max(0ll,v[0]-v[3]);
    ans+=v[2];
    ll t=max(0ll,v[2]-v[1]);
    v[1]=max(0ll,v[1]-v[2]);
    v[0]=max(0ll,v[0]-2*t);
    ans+=v[1]/2;
    v[0]=max(0ll,v[0]-v[1]/2);
    ans+=v[1]%2;
    v[0]=max(0ll,v[0]-v[1]%2*3);
    ans+=(v[0]+4)/5;
    
    return ans;
  }
};