SRM 475 300pt: RabbitStepping

TopCoder

問題概要

長さL(<=17)の1次元ボードがあり、各マスには色が塗ってある。各ターン毎にうさぎは色に応じて左右のマスに移動し、右のマスから順に削れていく。同じマスに同時にうさぎが飛び込んだら彼女らは取り除かれてどこかへいく。これをマスが2つになるまで繰り返す。初期盤面からRマスランダムに選んでうさぎを配置する。最後に残るうさぎが何匹か期待値を求める問題。

考えたこと

  • (当時はシミュレーションをひーひー言いながら通した記憶がある。その後editorialで綺麗な解答に感心した)
  • これは解き方覚えてる。偶奇のマスは干渉しないし、うさぎは2匹ずつ消えるので偶奇のマスにいるうさぎの数を数えて、それぞれ偶奇を見てやればよい。
  • 複雑なビット演算を使うまでもなく、間に合う限り愚直に書く。L個のうちからR個えらんだ部分集合全列挙とかやる必要はない。

practiceで通ったコード

計算量O(2^L * L)。真面目にやるとO( (L, R) )まで落ちる。

#include <string>
using namespace std;

struct RabbitStepping {

	double getExpected(string field, int r) {
		const int N = field.size();
		int cnt = 0, tot = 0;

		for(int bit=0; bit<(1<<N); bit++)if(__builtin_popcount(bit) == r){
			int rs[2] = {0};
			for(int i=0; i<N; i++){
				rs[i&1] += (bit>>i)&1;
			}
			cnt += rs[0]%2 + rs[1]%2;
			tot++;
		}

		return (double)cnt/tot;
	}

};