Div2 550, Div1 300 - RabbitStepping

SRM

問題

左から順に [0],[1],[2],[3],…[N-1] と番号を付けられたマスがあり，r 羽のウサギが1羽ずつどこかに入っている．以下の動作を繰り返す時，最後まで残っているウサギの数の期待値はいくらか？

  1. 以下のルールでウサギが１ステップ動く
    1. [0]にいたら[1]に移動する
    2. [N-1]か[N-2]にいたら左へ１マス移動する．
    3. 白マスにいたら左へ，黒マスにいたら右へ移動する
    4. 赤マスにいたら，赤マスの直前にいたマスへ移動する．ただし１ステップ目は左へ．
  2. 同じマスに 2 羽以上居るウサギは消される．
  3. N＞2 であれば右端のマスが消えて，1 に戻る．
  4. 終了

考え方

Nの最大値は17なので全パターン(最大で 17C8＝24310 通り)試せばOK．プログラム的には

  1. そのパターンをどう作るか
  2. シミュレーションが間に合うのか

という点が気になるが，どっちも実は大したことないので下手の考え休むに似たり．ガシガシ書きましょう．ただ，シミュレーションの方では解析的に答えが出ます．

まずは N マス中の r マスにウサギを配置するパターンの作り方．C++的には 1 を r 個，0 を (N-r) 個というvectorを作って next_permutation を利用するとコードもそう難しくなく実現できる．その他一般的にはビットを数える popCount 関数を作り，0≦i＜2N の中から popCount(i)＝r となる i の場合だけチェックすればいい．2k を示すビットが立っていれば [k] にウサギが居る，という設定ね，一応．

あとはシミュレーション．これは素直に書かれている通りやっても問題ない．が，解析的なお話．

  • ウサギは毎回，[i] から [i-1] か [i+1] へ移動するので，[奇数] と [偶数] にいるウサギが干渉することは無い．
  • ウサギが消えるには 2 羽以上が必要だが，１ステップの移動で１マスへ 3 羽以上のウサギが移動してくるのは不可能なので，ウサギが減る数は必ず(初期位置が[奇数][偶数]であったそれぞれのグループ別に見ても)偶数．
  • 最後には 2 マスしか残らないので結局のところ初期位置が[奇数][偶数]だったグループからそれぞれ高々1羽しか残らない．

ということを考慮すると，初期位置の2グループそれぞれについて，奇数羽いたら 1 羽残り，偶数羽だったら残らない，ということになる．なのでシミュレーションなんて何のその．折角作った popCount を活用しよう．

コード

２パターン掲載．

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class RabbitStepping
{
  int survive(vector<int> r, string f)
  {
    int n = f.size();
    vector<int> pre(n, -1);
    for( int i = 1 ; i < n ; ++i ) pre[i] = i - 1;

    for( int m = n ; m >= 2 ; --m ) {
      f[m-1] = f[m-2] = 'W';
      f[0] = 'B';
      vector<int> nxt(m, 0), npre(m, -1);
      for( int i = 0 ; i < m ; ++i ) {
        if( r[i] == 0 ) continue;
        int dst = (f[i]=='W')?(i-1):(f[i]=='B')?(i+1):pre[i];
        ++nxt[dst];
        npre[dst] = i;
      }
      for( int i = 0 ; i < m ; ++i ) if( nxt[i] > 1 ) nxt[i] = 0;
      pre = npre;
      r = nxt;
    }
    return r[0] + r[1];
  }
public:
  double getExpected(string field, int r)
  {
    int n = field.size();

    vector<int> rab(n, 0);
    for( int i = 0 ; i < r ; ++i ) rab[n-1-i] = 1;

    int all = 0, cnt = 0;
    do {
      cnt += survive(rab, field);
      ++all;
    } while( next_permutation(rab.begin(), rab.end()) );
    return (double)cnt / all;
  }
};

#include <string>
using namespace std;
class RabbitStepping
{
  int popCount(int b)
  {
    b = ((b >> 1) & 0x55555) + (b & 0x55555);
    b = ((b >> 2) & 0x33333) + (b & 0x33333);
    b = ((b >> 4) & 0xf0f0f) + (b & 0xf0f0f);
    b = ((b >> 8) & 0xf00ff) + (b & 0xf00ff);
    return (b + (b >> 16)) & 0xffff;
  }
  int popOdd(int b)
  {
    b ^= b >> 16;
    b ^= b >> 8;
    b ^= b >> 4;
    b ^= b >> 2;
    return (b ^ (b >> 1)) & 1;
  }
public:
  double getExpected(string field, int r)
  {
    int cnt = 0, all = 0;
    for( int i = 0 ; i < (1 << field.size()) ; ++i ) {
      if( popCount(i) == r ) {
        cnt += popOdd(i & 0x55555) + popOdd(i & 0xaaaaa);
        ++all;
      }
    }
    return (double)cnt / all;
  }
};