naoya_t@topcoder

SRM453

02:50 |

gdgd回。Matchの最中にTopCoderのサーバ落ちた！ノーゲーム。

250点: TheBasketballDivOne

• 書いた
• Arena復活したので投稿した
• 通った

#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 TheBasketballDivOne {
 public:
  int find(int n, int m) {
    int matches=n*(n-1); // [2-5][1-4] = [2-20]
    if (m > 2*(n-1)) return 0;

    int h = matches/2;
    int mx = (1 << h)-1, ma = (1 << matches)-1;
    int xx = (1 << h)|1;

    vector<vector<int> > ms(n,vector<int>(2));
    ms[0][0] = 0x04b & mx, ms[0][1] = 0x000 & mx; // 4+0
    ms[1][0] = 0x094 & mx, ms[1][1] = 0x001 & mx; // 3+1
    if (n>=3) {
      ms[2][0] = 0x120 & mx, ms[2][1] = 0x006 & mx; // 2+2
      if (n>=4) {
        ms[3][0] = 0x200 & mx, ms[3][1] = 0x038 & mx; // 1+3
        if (n>=5) {
          ms[4][0] = 0x000 & mx, ms[4][1] = 0x3c0 & mx; // 0+4
        }
      }
    }

    rep(i,n) rep(j,2) ms[i][j] *= xx;
    
    vector<int> win(n,0);
    set<vector<int> > s;
    for (int i=0;i<=ma;i++) {
      rep(j,n){
        win[j] = __builtin_popcount(i & ms[j][0])
               + __builtin_popcount((~i) & ms[j][1]);
      }
      sort(all(win));
      s.insert(win);
    }
    int cnt=0;
    tr(s,it){
      if ((*it)[n-1] == m) cnt++;
    }
    return cnt;
  }
};

500点: TheTournamentDivOne

• Failed System Test
• practice roomで調べようと思ったけど重くてできなかった（ので後回し）

1000点: TheSoccerDivOne

• 開いただけ