naoya_t@topcoder

SRM432

23:04 |

01.06.2009 (今年最初)

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	LampsGrid	◎				110.63点
1	500	GroupedWord	間に合わず
1	1000

250点問題: LampsGrid

rowを減らすDPを書こうとしていて頭真っ白になった

colを減らしていけば良い

時間かかりすぎ。System Testは通ったのでほっとする。

同じ部屋のmhueさんのコードがものすごく短い件。こんな感じ：

#define REPS(i,x) for(int i=0;i<(int)((x).size());++i)

template<class T> inline T checkmax(T &a,T b){if(b>a)a=b;return a;}

class LampsGrid {
public:
  int mostLit(vector <string> initial, int K) {
    int res=0;
    REPS(i,initial){
      int c=0,cc=0;
      REPS(j,initial) if(initial[j]==initial[i]) c++;

      REPS(k,initial[i]) if(initial[i][k]=='0') cc++;
      if(cc==K|| (K>=cc & K%2==cc%2)) checkmax(res,c);
    }
    return res;
  }
};

どういうことだw

自分のはこんな感じ（長文注意）：

class LampsGrid {
 public:
  int sub(vector<long long> mat, int coln, int k){
    int rown=sz(mat);
    if(rown==0) return 0;
    if(coln==1) {
      int cnt=0;
      rep(r,rown) if(mat[r]) cnt++;
      return (k&1)? rown-cnt : cnt;
    }
    if(k==0){
      long long m = (1LL << coln) - 1;
      int cnt=0;
      rep(r,rown){if(mat[r]==m) cnt++;}
      return cnt;
    }
    vector<long long> ons,offs;
    rep(r,rown){
      if(mat[r]&1) {
        ons.pb(mat[r]>>1);
      } else {
        offs.pb(mat[r]>>1);
      }
    }
    return max(sub(ons,coln-1,k), sub(offs,coln-1,k-1));
  }
  int mostLit(vector<string> initial, int K) {
    int rown=sz(initial);
    int coln=initial[0].length();
    vector<long long> mat(rown);
    rep(r,rown){
      long long bp=0LL;
      rep(c,coln){
        bp<<=1LL;
        if(initial[r][c]=='1') bp+=1LL;
      }
      mat[r] = bp;
    }
    if(K==0){
      long long m = (1LL << coln) - 1;
      int cnt=0;
      rep(r,rown){if(mat[r]==m) cnt++;}
      return cnt;
    }
    return sub(mat,coln,K);
  }
};

...

えーっと。違うシーケンスは絶対に同時にはつけられない

niha SRM

srd

class LampsGrid {
 public:
  int mostLit(vector<string> il, int K) {
    map<string,int> ss;
    tr(il,it){
      if(found(ss,*it)) ss[*it]++;
      else ss[*it]=1;
    }
    int l=il[0].length();
    int maxc=0;
    tr(ss,it){
      string st=it->first;
      int cnt=it->second;
      int c=K; rep(i,l) if(st[i]=='0') c--;
      if(c>=0 && c%2==0) maxc=max(maxc,cnt);
    }
    return maxc;
  }
};

500点問題: GroupedWord

時間足りず

同じ時間をかけるなら、こっちの方が点になりそうな問題・・・とか思ったけどかなりの数が撃墜ないしFailed System Testの模様。

1000点問題:

開いてない

結果：110.63点で368/580位。

1577→1537。かろうじてイエロー防衛。

SRM380 Div1 Easy: LameKnight

過去問, 練習 | 20:58 |

SRM432前の準備運動（その２）

SRM開始まであと13分・・・

Test Caseは全部通ったのでsubmitしたけどSystem Test落ち

class LameKnight {
 public:
  int maxCells(int height, int width) {
    if(height==1||width==1) return 1;
    if(width==5) return 4;
    if(height==2) return 1+(width-1)/2;
    if(width<5) return width;
    if(height>3) return width-2;
    return width-3;
  }
};

これは適当すぎると思うので、あとで見直そう。

→見直した。ちゃんとノートに書いて場合分けしたら簡単だった件

class LameKnight {
 public:
  int maxCells(int height, int width) {
    if(height==1 || width==1) return 1;
    if(height==2) return min(1+(width-1)/2, 4);
    if(height>=3 && width<7) return min(width,4);
    return width-2;
  }
};

SRM381 Div1 Easy: TheDiceGame

過去問, 練習 | 20:41 |

SRM432前の準備運動に

class TheDiceGame {
 public:
  double expectedThrows(int candies) {
    int n=candies+6;
    vector<double> t(n,0.0),r(n,0.0);
    t[1]=t[2]=t[3]=t[4]=t[5]=t[6]=1.0;
    r[1]=r[2]=r[3]=r[4]=r[5]=r[6]=1.0/6;
    for(int i=1;i<candies;i++){
      double t_=t[i]+1, r_=r[i]/6;
      for(int j=1;j<=6;j++){
        double tj=t[i+j], rj=r[i+j];
        r[i+j]=r_+rj;
        t[i+j]=(t_*r_ + tj*rj)/r[i+j];
      }
    }
    double t_=0, r_=0;
    rep(i,6){
      int c=candies+i;
      t_ += t[c]*r[c]; r_ += r[c];
    }
    return t_/r_;
  }
};