Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-20

SRM360 Div1 Easy: SumOfSelectedCells

| 00:21 | SRM360 Div1 Easy: SumOfSelectedCells - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM360 Div1 Easy: SumOfSelectedCells - naoya_t@topcoder SRM360 Div1 Easy: SumOfSelectedCells - naoya_t@topcoder のブックマークコメント

これは難しい。むしろ撃墜レースと考えるべき問題。実際Div1でも通過率34%と、500点問題を下回っている。

  • DP的に解こうとしている
  • 数回のsubmit/systestの末、とりあえず以下のコードまで来た
  • まだCase#37がTLE
  • 後で上手な人のコードを見るとしよう
class SumOfSelectedCells {
 public:
  string hypothesis(vector<string> table) {
    int h=sz(table);
    vector<vector<int> > t(h);
    rep(i,h) t[i]=map_atoi(split(table[i]));
    int w=sz(t[0]);
    if(w>h){
      vector<vector<int> > t_(w);
      rep(i,w) t_[i].resize(h);
      rep(i,w) rep(j,h) t_[i][j]=t[j][i];
      t=t_;
      swap(w,h);
    }
    // w<=h

    map<int,int> memo;
    int mmax=1<<h;

    if(w==1){
      int z=t[0][0];
      for(int i=1;i<h;i++) if(z!=t[i][0]) goto incorrect;
      goto correct; //oops
    }
    if(h==2){
      if (t[0][0]+t[1][1] == t[1][0]+t[0][1])
        goto correct;
      else
        goto incorrect;
    }
    // nC2
    rep(x,h) {
      rep(i,h) {
        if(i==x) continue;
        rep(j,h) {
          if(j==x||i>=j) continue; //j>i
          int s_ij=t[i][0]+t[j][1],
              s_ji=t[j][0]+t[i][1];
          if(s_ij!=s_ji) goto incorrect;
          int m=(1<<i)|(1<<j);
          memo[m|(2<<h)]=s_ij;
        }
      }
    }
    if(w==2){
      if(h>w){
        int s=-1;
        tr(memo,it){
          int s_=it->second;
          if(s<0)s=s_;
          else if(s!=s_) goto incorrect;
        }
      }
      goto correct;
    }

    for(int d=3;d<=w;d++){
      int b=d+(h-w);
      rep(m,mmax){
        if(__builtin_popcount(m)!=b) continue;
        int s=-1;
        rep(i,h){
          int x=1<<i;
          if((m&x)==0) continue;
          int m_=m-x;
          if(d==3 && b>3){
            for(int m2=3;m2<mmax;m2++){
              if(__builtin_popcount(m2)!=2) continue;
              if((m_&m2)==m2){ m_=m2; break; }
            }
          }
          int s_=t[i][d-1]+memo[m_|((d-1)<<h)];
          if(s<0) s=s_;
          else if(s!=s_) goto incorrect;
        }
        memo[m|(d<<h)]=s;
      }
    }

 correct:
    return "CORRECT";
 incorrect:
    return "INCORRECT";
  }
};

SRM361 Div1 Easy: WhiteHats

| 02:10 | SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder SRM361 Div1 Easy: WhiteHats - naoya_t@topcoder のブックマークコメント

ごめんなさい2度再挑戦しました

  • (白帽子数)≦(人数)

さっと書いて投稿したコードは

{7, 8, 7, 8, 8, 7, 8, 7, 8, 7, 8, 7, 7, 8, 7, 8} => 8

でコケた。

  • 白帽子の人自身はその白帽子を勘定に入れられないので、合計で(白帽子数)だけのカウント漏れが発生
  • 従って (投票数の合計) = (白帽子数)×(人数)-(白帽子数) = (白帽子数)×(人数 - 1)
  • ∴(投票数の合計)/(人数 - 1) = (白帽子数)

再投稿したコードは

{1, 1, 1, 1, 1, 1, 1, 1, 8} => -1

でコケた。うん、それ無理

  • 各人のカウントが (白帽子数) または (白帽子数-1) になっていることを確認。そうでなければ -1 を返す。
#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class WhiteHats {
 public:
  int whiteNumber(vector <int> count) {
    int n=sz(count);
    int w=0;
    tr(count,it){
      w+=*it;
    }
    if(w%(n-1)>0) return -1;
    int c=w/(n-1);
    if(c>n) return -1;
    tr(count,it){
      if(*it<c-1 || c<*it) return -1;
    }
    return c;
  }
};

SRM362 Div1 Easy: MaximizeSquares

| 01:49 | SRM362 Div1 Easy: MaximizeSquares - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM362 Div1 Easy: MaximizeSquares - naoya_t@topcoder SRM362 Div1 Easy: MaximizeSquares - naoya_t@topcoder のブックマークコメント

Failed System Test...

  • 使える点の数から、考えられる幅と高さについて全て試す法
  • 単純なミス(コメントアウトした箇所)
class MaximizeSquares {
 public:
  int squareCount(int N) {
    if(N<4) return 0;
    int wmin=(int)sqrt(N),wmax=N/2;
    int cmax=wmax-1;
    for(int w=wmin;w<=wmax;w++){
      int c=0;
      int h0=N/w;
      int w0=N-w*h0;
      if(w0==1) w0=0;
      int h=h0+((w0==0)?0:1);
      int rmax=min(w,h);
      for(int r=1;r<=rmax;r++){
//      if(w>=r && h0>=r) c += (w-r)*(h0-r);
//      if(w0>=r && h>=r) c += (w0-r);
        if(w-1>=r && h0-1>=r) c += (w-r)*(h0-r);
        if(w0-1>=r && h-1>=r) c += (w0-r);
      }
      cmax = max(cmax,c);
    }
    return cmax;
  }
};

所要時間←→得点の計算

00:56 | 所要時間←→得点の計算 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 所要時間←→得点の計算 - naoya_t@topcoder 所要時間←→得点の計算 - naoya_t@topcoder のブックマークコメント

Competing in a Rated Algorithm Competition, 12 Determining Score

以下Schemeですが

(define TT 75)

(define (point MP time)
  (* MP (+ 0.3 (/ (* 0.7 TT TT) (+ (* 10 time time) (* TT TT))))))

(define (taken-time MP pt)
  (* TT (sqrt (/ (- (/ 0.7 (- (/ pt MP) 0.3)) 1) 10))))

(define (minsec min)
  (let* ([m (floor->exact min)]
         [s (floor->exact (* (- min m) 60))])
	(format #t "~d'~d''\n" m s)))

所要時間(分)から得点を得る:

(point 250 3)
=> 247.24409448818895

得点から所要時間(分)を得る:

(taken-time 250 203.42)
=> 14.283829997874937

(minsec (taken-time 250 203.42))
=> 14'17''

SRM363 Div1 Easy: HandsShaking

| 00:51 | SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder のブックマークコメント

ちょっと悩んだ。203.42点(=14'17")

  • DP。最初の1人が誰と手をつなぐか。その線の右側と左側の小グループについて考える分割統治。
  • 最初の1人は、右側と左側の小グループにそれぞれ偶数人が属するように相手を選んで手をつなぐ。というか、隣りの人から始めて1人おきに回り、反対側の隣りの人で終わる。
typedef long long ll;
#define found(s,e)  ((s).find(e)!=(s).end())

class HandsShaking {
  map<int,ll> memo;
 public:
  long long countPerfect(int n) {
    if(n==0) return 0LL;
    if(n==2) return 1LL;
    if(found(memo,n)) return memo[n];
    ll sum=0;
    for(int i=1;i<n;i+=2){
      int a=i-1, b=n-i-1;
      if(a==0) sum+=countPerfect(b);
      else if(b==0) sum+=countPerfect(a);
      else sum+=countPerfect(a)*countPerfect(b);
    }
    return memo[n]=sum;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090120