Hatena::Grouptopcoder

cou929のTopCoder日記

2010-07-08

SRM 475 div1

21:20

ひさびさのSRM. 一問も解けず rating は 1507 -> 1420.

Easy - RabbitStepping

うさぎがr羽いて, n (r <= n) マスの一直線のセルがある. うさぎをセル上に配置する. セルは3色に色分けされていて, それぞれ動作が異なる. セルの色に応じてうさぎを移動させ, ひとつのセルに2羽うさぎが乗るとその2羽は取り除かれる. また毎ターンごとにセルの右端が除かれる. のこり2セルになるまでこの操作を繰り返したときの, のこったうさぎの数の期待値を求めよ.

うさぎの配置の仕方は, セル数nからうさぎの数rを選ぶ場合の数 nCr となります. セル数の上限が17なので, 17 C 8 = 24310 がうさぎの配置パターンの最大数です. それぞれについて最大で17ステップの処理が行われます. このオーダーならばうさぎの配置パターンについてシミュレーションをして期待値を求めればよさそうです.

うさぎの配置パターンの列挙方法ですが, いま冷静になると next_permutation 一択なんですが, 本番では再帰でがんばってました. で, その部分がおそらく原因で, ローカルでは大丈夫だったんですがサーバでは謎の例外が出て, システムテストに落ちてしまいました. 以下は next_permutation を使った修正版です.

うさぎのシミュレーションをしているのはcalc()という関数. ふつうに愚直にやっています. もうすこし綺麗に書きたい(特にうさぎを移動させている部分)ものですが, これをバグ無く一発でかけたのは少し嬉しかったです.

class RabbitStepping {
public:
  string field;

  int calc(vector <int> &_rabbits) {
    vector <int> rabbits = _rabbits;
    int ret = 0;
    int i, j;
    int n = field.size();
    string f = field;
    vector <int> before(n, -1);

    for (i=0; i<n-2; i++) {
      vector <int> tmp = rabbits;
      vector <int> tmp_before(n, -1);

      for (j=0; j<f.size(); j++) {
        if (rabbits[j] == 1) {
          if (j == 0) {
            tmp[j]--;
            tmp[j+1]++;
            tmp_before[j+1] = j;
          } else if (j >= f.size() - 2) {
            tmp[j]--;
            tmp[j-1]++;
            tmp_before[j-1] = j;
          } else {
            if (f[j] == 'W') {
              tmp[j]--;
              tmp[j-1]++;
              tmp_before[j-1] = j;
            } else if (f[j] == 'B') {
              tmp[j]--;
              tmp[j+1]++;
              tmp_before[j+1] = j;
            } else if (f[j] == 'R') {
              if (i == 0) {
                tmp[j]--;
                tmp[j-1]++;
                tmp_before[j-1] = j;
              } else {
                tmp[j]--;
                tmp[before[j]]++;
                tmp_before[before[j]] = j;
              }
            }
          }
        }
      }

      for (j=0; j<f.size(); j++)
        if (tmp[j] > 1) {
          tmp[j] = 0;
          tmp_before[j] = -1;
        }
      rabbits = tmp;
      before = tmp_before;

      f = f.substr(0, f.size()- 1);
    }

    for (i=0; i<rabbits.size(); i++)
      ret += rabbits[i];

    return ret;
  }

  double getExpected(string _field, int r) {
    field = _field;
    int counter = 0, rabbitnum = 0;
    vector <int> v(field.size(), 1);
    int i;

    for (i=0; i<field.size()-r; i++)
      v[i] = 0;

    do {
      counter++;
      rabbitnum += calc(v);
    } while (next_permutation(v.begin(), v.end()));

    return (double)rabbitnum / (double)counter;
  }
};

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/cou929/20100708