SRM 601 Div2 Medium WinterAndCandies

問題

SRM 601 - TopCoder Wiki

数字のリストが与えられて,このカードからある制限の元カードを取り出す方法の数を答える問題. 制限とはK個の数字を取り出した時に,ちょうどその数字は1からKまでの連続の数字となっていること.

解答

公式の解説が一番わかりやすかったのでメモ. K個取り出す時の取り出し方の個数をc(K)とする. c(K)は(1の数字の個数) * (2の数字の個数) * ... * (Kの数字の個数) となる. そして全体の答えはc(1), c(2), ..., c(N)となる. (ここでNは1から連続する数で最大の数)

class WinterAndCandies
{
public:
  int getNumber(vector <int> type)
    {
      sort(type.begin(), type.end());
      int product = 1;
      int num_way = 0;
      int n = type.size();
      for(int i = 0; i < n;) {
        // std::cout << "type[" << i << "]=" << type[i]<< std::endl;
        if ((i == 0 && type[i] != 1)) break;
        if (i > 0 && type[i] != (type[i-1] + 1)) break;
        int num_same = 1;
        while(i + num_same < n && type[i] == type[i+num_same]) num_same++;
        // std::cout << "type=" << type[i] << " num=" << num_same << std::endl;
        num_way += product * num_same;
        product *= num_same;
        i += num_same;
      }
      return num_way;
    }
};