naoya_t@topcoder

SRM442 Div1 Medium: BedroomFloor

過去問, 練習 | 04:15 |

• Easyを解いた後50分ちょい（＝12分オーバー）でサンプルケース全部通った
• Practice Roomへの３度目のsubmitでpassed
• 作戦は間違ってないけど…落ち着いてれば気づく（ないしテストケース増設で検出できる）範囲のミス３つ
• 10x10単位のalignmentで区切って、10x10フルで取れる領域（取れない場合もある）と端数部分最大８つで最大９分割
• 10x10につきサイズ5x20枚
• そうでない最大８つの領域についてはとりあえずサイズ1〜5のタイルが何枚必要か数える。20枚のタイルそれぞれについて交差領域の面積。
• サイズ1〜5のタイルの必要枚数がわかったらあとはgreedyにまとめるだけ

#include <vector>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class BedroomFloor {
 public:
  int cross(int x1,int y1,int x2,int y2, int x3,int y3,int x4,int y4){
    int x5=max(x1,x3), y5=max(y1,y3);
    int x6=min(x2,x4), y6=min(y2,y4);
    return (x5<x6 && y5<y6)? (x6-x5)*(y6-y5) :0;
  }
  void check(vector<long long>&cnt, int x1,int y1,int x2,int y2, int rep=1){ /// 【３】繰り返し回数を忘れてた
    if (x1==x2 || y1==y2) return;
    vector<long long> mycnt(6,0);
    rep(i,5){
      mycnt[cross(x1,y1,x2,y2, 0,i,5,i+1)]++;
      mycnt[cross(x1,y1,x2,y2, 5,5+i,10,6+i)]++;
      mycnt[cross(x1,y1,x2,y2, 5+i,0,6+i,5)]++;
      mycnt[cross(x1,y1,x2,y2, i,5,i+1,10)]++;
    }
    mycnt[0]=0;
    for(int i=1;i<=5;i++) cnt[i]+=mycnt[i]*rep;
  }
  long long numberOfSticks(int x1, int y1, int x2, int y2) {
    vector<long long> cnt(6,0);
    int xa=(x1%10)?(x1-(x1%10)+10):x1, xb=x2-(x2%10);
    int ya=(y1%10)?(y1-(y1%10)+10):y1, yb=y2-(y2%10);
    if (xa<xb && ya<yb) cnt[5] = 1LL*(xb-xa)*(yb-ya)/5;
    if (xa>xb) {
      if (ya>yb) {
        check(cnt, x1%10,y1%10, x2%10,y2%10);
      } else {
        if(y1<ya) check(cnt, x1%10,y1%10, x2%10,10);
        check(cnt, x1%10,0, x2%10,y2%10);
      }
    } else {
      if (ya>yb) {
        if(x1<xa) check(cnt, x1%10,y1%10, 10,y2%10);
        check(cnt, 0,y1%10, x2%10,y2%10);
      } else {
        if(x1<xa && y1<ya) check(cnt, x1%10,y1%10, 10,10);
        if(x1<xa) check(cnt, x1%10,0, 10,y2%10);
        if(y1<ya) check(cnt, 0,y1%10, x2%10,10);
        check(cnt, 0,0, x2%10,y2%10); /// 【２】%10忘れ
      }
    }

    if (xa<xb) {
      if (ya>yb) {
        check(cnt, 0,y1%10, 10,y2%10, (xb-xa)/10);
      } else {
        if(y1<ya) check(cnt, 0,y1%10, 10,10, (xb-xa)/10);
        check(cnt, 0,0, 10,y2%10, (xb-xa)/10);
      }
    }
    if (ya<yb) {
      if (xa>xb) {
        check(cnt, x1%10,0, x2%10,10, (yb-ya)/10);
      } else {
        if(x1<xa) check(cnt, x1%10,0, 10,10, (yb-ya)/10);
        check(cnt, 0,0, x2%10,10, (yb-ya)/10);
      }
    }
    
    long long total=cnt[1]+cnt[2]+cnt[3]+cnt[4]+cnt[5], last;
    while(1){
      // 4
      int c41=min(cnt[4],cnt[1]);
      cnt[1]-=c41; cnt[4]-=c41; cnt[5]+=c41;
      cnt[5]+=cnt[4]; cnt[4]=0;
      // 3
      int c32=min(cnt[3],cnt[2]);
      cnt[2]-=c32; cnt[3]-=c32; cnt[5]+=c32;
      int c311=min(cnt[3],(cnt[1]+1)/2);
      cnt[3]-=c311; cnt[1]-=c311*2; if(cnt[1]<0)cnt[1]=0; cnt[5]+=c311;
      // 2
      int c22=cnt[2]/2;
      cnt[4]+=c22; cnt[2]-=c22*2;
      int c21=min(cnt[2],cnt[1]);
      cnt[2]-=c21; cnt[1]-=c21; cnt[3]+=c21;

      last=total; total=cnt[1]+cnt[2]+cnt[3]+cnt[4]+cnt[5];
      if(total==last) break;
    }
    cnt[5] += cnt[1]/5; cnt[1] %= 5;
    int c1=cnt[1]; if(c1>1){ cnt[c1]++; cnt[1]=0; } /// 【１】if(c1>1)が無かった。これだと1が1つ余ったときに消えてしまう
    total=cnt[1]+cnt[2]+cnt[3]+cnt[4]+cnt[5];
    return total;
  }
};

こういうのちゃんと取れるようになりたいなー

追記：気がつく人は気がつくと思うけどrepという名前をforのマクロとcheck()の最後の引数で使ってて見事に衝突しない件。人間obfuscatorに一歩近づいた気がしたが、TopCoderでこういうコードを書くのは問題ないのかな