torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 653, Division 2, Level 2 : RockPaperScissorsMagicEasy

問題概要

 Alice と Bob が複数回に渡ってじゃんけんをする.各ラウンドで,相手に勝利したプレイヤーが 1 ポイントを得る.
 今,各ラウンドで Bob が出す手は分かっている.Bob の戦略の情報は配列 card で与えられ,card_ii 番目のラウンドで Bob が出す手を表す(0 -> グー, 1 -> チョキ,2 -> パー).
 Alice が合計 score ポイントを獲得するための手の出しかたは何通りあるか? 答えを X として,X \pmod{ 10^9+7 } を計算せよ.

解法

 |card|N と書きます.
 まず,score \leq N でなければ絶対に達成できないので,N < score のときの答えは 0 となります.
 次に,score ポイントを取得可能な場合について考えます.score ポイントを取得する場合というのを詳しく述べると,

  • score 回の勝ち
  • N - score 回の勝ち以外(あいこ or 負け)

となります.勝つラウンドが決まっているとすると,残りの N - score ラウンドで出せる手の組合せは,勝つ手以外の 2 通りを N - score 回選択することになるので,2^{ N - score } 通りです.また,勝つラウンドの選び方は,N 個のものから score 個を選択する組合せの数なので,二項係数 \begin{pmatrix} N \\ C \end{pmatrix} となります.勝つラウンドには手の選択肢が無いので,勝つラウンドが決まっていれば手の出し方は 1 通りに定まります.従って答えは (勝つラウンドの選び方)×(勝たないラウンドの手の出し方) を表す 2^{ N - score } \times \begin{pmatrix} N \\ C \end{pmatrix} です.
 二項係数をパスカルの三角形を DP する方法で求めるとすると,この部分が最も時間のかかる処理となり,全体のオーダーは O( N^2 ) 時間となります.
 二項係数と反復二乗法をライブラリにしていれば,かなり少ない実装量で解くことができます.

コード

#define SZ( v ) ( (int)( v ).size() )

// a^x を mod で求める
// 反復二乗法
long long mod_pow( long long a, long long x, long long mod );

// パスカルの三角形による nCr の計算
// 剰余系版
// 前処理 O( N^2 ), クエリ O( 1 )
class PascalTriangle;
// PascalTriangle( N )
// ()( n, r )

constexpr int MOD = 1000000007;
PascalTriangle nCr( 2000, MOD );

class RockPaperScissorsMagicEasy
{
public:
	int count( vector <int> card, int score )
	{
		const int N = SZ( card );

		return score <= N ? ( mod_pow( 2, N - score, MOD ) * nCr( N, score ) ) % MOD : 0;
	}
};