SRM 653 Div2 Medium RockPaperScissorsMagicEasy

問題

SRM 653 - TopCoder Wiki

じゃんけんをして勝ったら1ポイント,負けかアイコだったら0ポイントを得る時, 各ステップiで相手がcard[i]を出した時トータルのスコアがscoreとなる時の手数を答える問題.

解答

相手の手順が何でも,こちらは任意の手を選ぶことができるので, 相手の手札の入力は何回じゃんけんをしたかぐらいの意味しかない.

コンビネーションを求めてもいいけど, dpで解いた.

class RockPaperScissorsMagicEasy
{
public:
  int count(vector <int> card, int score)
    {
      long long mod = 1000000007;
      int mid = 2002;
      int n = card.size();
      int m = 4004;
      // vector<vector<long long> > cur(4002, vector<long long>(, 0));
      vector<long long> cur(2004, 0);
      vector<long long> prev(2004, 0);
      // vector<vector<long long> > prev(4002, vector<long long>(score, 0));
      prev[0] = 1;
      for (int i = 0; i < n; i++) {
        cur = vector<long long>(m, 0);
        for (int j = 0; j < m; j++) {
          if (prev[j] > 0) {
            cur[j+1] = (cur[j+1] + prev[j]) % mod;
            cur[j % m] = (cur[j] + 2 * prev[j]) % mod;
          }
          // for (int k = 0; k <= 1; k++) {
          //   cur[(j+k) % m] = (cur[(j+k) % m] + prev[j]) % mod;
          // }
        }
        swap(cur, prev);
      }
      return prev[score];
    }
};