ICPC国内予選参加記 2017

参加まで

忙しいし出なくて良いかーと思っていたのですが*1，先輩の後押しで参加することに．
今年で3回目の参加だったので，登録まではバタバタせずにすみました．（監督・コーチありがとうございました！）

メンバーは去年と同じ同期のメンバーが1人と研究室の後輩1人引き連れて参加しました．
締切ギリギリで参加を決めたので，一度だけ通し練習をして本番へ．

当日

プリンタの不調で問題が10分ぐらい印刷できず，テンパる（ちゃんと印刷確認しましょう）

落ち着いた後は，後輩にA,同期にBを任せて，自分はCを取り組む．

Cは去年，一昨年と面倒くさい実装だったのですが，今年は簡単で余裕があったので，Aのバグ取りを一緒してました．

CよりBの問題の方がパッと見て面倒臭そうだったので，先にPCを使うことに．
バグらせながらゆるゆるとAC．

Bを任せるのが結構不安だったので，問題を読みながらペアプロ．
想定よりだいぶ早く解けて（自分が解いてたら焦ってやばかったかも），この時点ではかなり良い順位に．

Dをフローとかじゃん？しばらくやった後，Gも外壁の近くを良い感じに辿るだけでいけそうと思って実装していました．
Gの実装をバグらせてる間にタイムアップ．

69位でした．国内予選落ちです．

感想

3年もやってて4問解けないの情けなさすぎて泣いてました．
Dの場合分けに気づけないの本当に悔しかったです．

Gの実装も上手く行けばワンチャンあったかもしれないのに，それも間に合わなかったので，完全に練習不足でした．

僕は今年で引退ですが，後輩が引き続き参加して，うちの大学も常連校ぐらいまで成長してほしいと思っています．
とりあえず，宣伝・指導をしないと来年から消えそうなので頑張ります．

反省

D問題解きました．Gもそのうち解きます．

#include <bits/stdc++.h>
using namespace std;

// n(<=23)が小さいとき，全探索
int nsmall(int n,int m,const vector<bitset<501>>& bits){
  int ret = 0;  
  for(int i=0;i<(1<<n);i++) {
    bitset<501> used;
    int cnt = 0;
    for(int j=0;j<n;j++){
      if((i>>j) & 1) {
        used = used ^ bits[j];
        cnt++;
      }
    }
    if(used.none()){
      ret = max(ret,cnt);
    }
  }
  return ret;
}
// mが小さいとき，レシピの状態でDP
vector<vector<int>> dp;
int msmall(int n,const int N,int used,const vector<int>& b){
  if(n == N){
    if(used == 0)return 0;
    else return -1e9;
  }
  if(dp[n][used] != -1)
    return dp[n][used];

  return dp[n][used] = max(msmall(n+1, N, used ^ b[n], b) + 1,
             msmall(n+1, N, used, b));
}

bool solve(){
  int n,m;
  cin >> n >> m;
  if(n == 0 && m == 0)
    return false;
  vector<string> vs(n);
  for(int i=0;i<n;i++){
    cin >> vs[i];
  }
  vector<bitset<501>> bits(n);
  vector<int> b(n);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(vs[i][j] == '1'){
        bits[i].set(j);
        b[i] |= (1<<j);
      }
    }
  }
  if(n <= 23){
    cerr << "n:" << n << endl;
    cout << nsmall(n,m,bits) << endl;
  }else{
    cerr << "m:" << m << endl;
    dp = vector<vector<int>>(n,vector<int>((1<<m),-1));
    cout << msmall(0,n,0,b) << endl;
  }
  return true;
}

int main(void) {
  while(solve()){}
  return 0;
}