Hatena::Grouptopcoder

cou929のTopCoder日記

2009-04-25

SRM418 div2 (過去問)

15:10

Level one - Towers

ターン性シミュレーションゲームみたいな問題。敵味方のhp、攻撃力や数が与えられて、何ターンで敵を倒せるか、倒せなければ-1を返すというもの。特に難しいところはなかった。

Level two - TwoLotteryGames

lottery gameというゲームで勝つ確率を求める問題。ルールは、プレイヤーと胴元はそれぞれ、1~nの整数の中から別々のm個を選択する。k個以上一致する数字を選んでいたら、プレイヤーの勝利というもの。問題では、n, m, kの値が与えられ、プレイヤーが勝利する確率を返す。

定式化さえできれば問題なく解けるなと思いましたが、定式化がうまくできない。しばらく悩んだ末、解説と解答をみました。

プレイヤー視点で考える。胴元が選んだm個の整数と、ちょうどi個一致している確率は、(胴元が選んだm個の数字からi個選択する組み合わせ) * (胴元が選んでいないn-m個の数字からm-i個の数字を選択する組み合わせ) / (n個の数字からm個選択する組み合わせ) と考えることができる。よって、binom(m, i) * binom(n-m, m-i) / binom(n, m) となる。あとはiをkからnまで計算すればok。

そりゃそうだよなあ。そんなに難しくないよなあという解答でした。k個以上の全ての組み合わせをいっぺんに求めようとしたのが敗因でした。うーん。このくらいさっとできるようにならなきゃなあ。

これとは別に、もう一つ解答方針が示されていました。nの範囲が1から高々8までなので、すべてのとりうる組み合わせを列挙し、条件に合う組み合わせの数を数えるという方法です。brute-forceな考え方ですね。計算量はだいたいO(n!)なので、間に合うということ。なるほど。

この方針だと、全ての場合を生成する部分が難しいところだと思うので、その部分のみ実装してみました。まず、それぞれの組み合わせは、ベクターベクターvector <vector <int> >)で表現することにしました。計算はcombinationsというクラスが行います。calc()という関数にnとmの値を渡すと、r()という関数再帰的に呼び出し、結果を保存していきます。print()という関数で結果を表示します。ループでやろうとしたのですがうまく思いつかなかったので、再帰で実装しました。以下は、1から5の数字の中から、3個選ぶ組み合わせを求めています。

// srm418.cpp

#include <vector>
#include <iostream>

using namespace std;

class combinations {
private:
  vector <vector <int> > result;
  int n;
  int m;
public:
  combinations(){};
  int calc(int _n, int _m);
  void r(int l, int r, vector <int> v);
  int print();
};

void combinations::r(int l, int r, vector <int> v)
{
  for (int i=l; i<=r; i++)
    {
      v.push_back(i);

      if (r == n)
	result.push_back(v);
      else
	this->r(i+1, r+1, v);

      v.pop_back();
    }
}

int combinations::calc(int _n, int _m)
{
  n = _n;
  m = _m;
  vector <int> tmp;
  r(1, n-m+1, tmp);

  return 0;
}

int combinations::print()
{
  for (int i=0; i<result.size(); i++)
    {
      for (int j=0; j<result[i].size(); j++)
	cout << result[i][j] << " ";
      cout << endl;
    }

  return 0;
}

int main(void) 
{
  combinations *c = new combinations;

  c->calc(5, 3);  // n = 5, m = 3 を計算
  c->print();     // 結果を表示

  return 0;
}

実行結果は以下の通り、うまくいったようです。

% g++ -Wall srm418.cpp && ./a.out
srm418.cpp: In member function 'int combinations::print()':
srm418.cpp:45: warning: comparison between signed and unsigned integer expressions
srm418.cpp:47: warning: comparison between signed and unsigned integer expressions
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5