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。かろうじてイエロー防衛。