naoya_t@topcoder

SRM475

21:57 |

リハビリ3

cos65535先生と同じ部屋

DIV	level	問題名	競技中	後で	System Test	通過率	備考	levenshtein
1	300	RabbitStepping	o	-	passed (135.54)	-	_	0
1	600	RabbitIncreasing	開いた	-	-	-	_	?
1	900	-	開いてない	-	-	-	_	?

Easy(300): RabbitStepping

• ぶるーとふぉーすでいいや（と思った時点で負け組！）
• 途中で接続が切れた。ノーゲーム？と思ったら家のネットが切れてた。再接続に5分ぐらいロス
• 合わない合わないと思ってたら分母が1<<Nのままだったとかで10分ぐらいロス
• passed; 135.54

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class RabbitStepping {
  string field_;
  int N,R,c;
  int game(int pat){
    vector<vector<vector<int> > > f(2,vector<vector<int> >(N,vector<int>()));
    for(int i=1,j=0;j<N;++j,i<<=1){
      if(pat&i) f[0][j].pb(-1);
    }
    rep(t,N-2){
      int t0=t%2, t1=(t+1)%2;
      int clen = N-t;
      f[t1].assign(clen-1,vector<int>());
      rep(i,N-t){
        if (i==0) {
          tr(f[t0][0],it) f[t1][1].pb(0);
        } else if (i==clen-1 || i==clen-2) {
          tr(f[t0][i],it) f[t1][i-1].pb(i);
        } else {
          switch(field_[i]){
            case 'W':
              tr(f[t0][i],it) f[t1][i-1].pb(i);
              break;
            case 'B':
              tr(f[t0][i],it) f[t1][i+1].pb(i);
              break;
            case 'R':
              tr(f[t0][i],it) {
                if (*it < 0) f[t1][i-1].pb(i);
                else f[t1][*it].pb(i);
              }
              break;
          }
        }
      }
      rep(i,N-t){
        if (sz(f[t1][i])>1) f[t1][i].clear();
      }
    }
    return f[N%2][0].size() + f[N%2][1].size();
  }
 public:
  double getExpected(string field, int r) {
    N=sz(field);//2-17
    R=r;
    field_=field;
    int x=1<<N,en=0;c=0;
    rep(p,x){if(__builtin_popcount(p)!=r)continue;
      en++;
      c+=game(p);
    }
    return 1.0 * c / en;
  }
};

Medium(600): RabbitIncreasing

• 残り30分弱
• とりあえずどんな感じに推移するのかTLEコードを書いてみる
• 書いてみた
• むぅ

Hard(900): 開いてない

Challenge Phase

• 落とさず落とされず
• 600が１つ落ちるだけの不活発なチャレンジタイム

System Test

• 赤の人の600が落ちてた

結果

135.54points

Room: 14/20

Div1: 281/598

1508→1525 微増

備考

• あ、そうか2匹以上はまとめてよかったのか(600)
• 2問解けるようになりたい