TopCoder SRM144 DIV1 (550)

次の550点問題は、組合せの問題です。
・いろいろな種類の数当てゲームがある。ゲームのルールのリストが入力されるので、それを「当てやすい順」に並べ替えて返せ。
・ゲームのルールは、「使用する数の範囲（１から10〜100）」「当てる数の個数（1〜8組）」「必ず昇順で現れるとするか」「同じ数値が2度以上現れるか」の4組のパラメータで与えられる。
ということで、各ルールのパターンごとに数値の組合せの数を計算すればいいようです。「必ず昇順」のルールがない場合は簡単で、そのままべき乗と順列です。
しかし、「必ず昇順で現れる」の場合がわからなくて困りました。「同じ数値が2度以上現れる」と組み合わさった場合だと、どこも降順にならなければいいので、同じ数値の連続も入れて考える必要があります。
で、しばらく悩んだ結果、「当てる数」を順に決定していくとして、b番目に使用する数がcであるような場合の数をとすると、


という風に1つ前の数を決める場合の数で表せるので、これを「当てる数の個数」まで繰り返し計算し、最後に合計をとることで求めました。
こうすると、「必ず昇順」かつ「同じ数値は現れない」場合はこの変形で、


として同様に計算できます。
結果、作成したのがこのコード：

#include <iostream>

#include <vector>
#include <algorithm>
#include <string>

#define NUMBER_OF_ARRAY(array) (sizeof(array)/(sizeof(array[0])))

using namespace std;

class Lottery {
	class LessPtnrsRule;

	class Rule {
		string m_name;
		int m_choice, m_blanks;
		bool m_sorted, m_unique;

		bool read_from_str(const char* in_str) {
			unsigned char c1, c2;

			if (! in_str) return false;
			const char* pos_sep = strchr(in_str, ':');
			if (pos_sep && in_str < pos_sep) {
				m_name = string(in_str, pos_sep - in_str);
				if (sscanf(pos_sep, ": %d %d %c %c", &m_choice, &m_blanks, &c1, &c2) == 4) {
					m_sorted = c1 == 'T' ? true : false;
					m_unique = c2 == 'T' ? true : false;
					return true;
				}
				else {
					return false;
				}
			}
			else {
				return false;
			}
		}

	public:
		//typedef unsigned long counter_t;
		typedef unsigned long long counter_t;

		Rule(const char* in_str = NULL) : m_choice(), m_blanks() { read_from_str(in_str); }
		Rule(string& in_str) : m_choice(), m_blanks() { read_from_str(in_str.c_str()); }

		int GetChoice() const { return m_choice; }
		int GetBlanks() const { return m_blanks; }
		bool IsSorted() const { return m_sorted; }
		bool IsUnique() const { return m_unique; }
		const char* GetName() const { return m_name.c_str(); }

		counter_t num_of_patterns() const {
			counter_t num_ptrns = 0;

			if (m_choice < 10 || 100 < m_choice) return 0;
			if (m_blanks < 1 || 8 < m_blanks) return 0;

			if (! m_sorted) {
				num_ptrns = m_choice;

				counter_t n_choice = m_choice;
				for (int i = 1; i < m_blanks; ++i) {
					if (m_unique) --n_choice;
					num_ptrns *= n_choice;
				}
				return num_ptrns;
			}
			else { // m_sorted is true
				vector<counter_t> path_cnt_prev(m_choice, 1);
				vector<counter_t> path_cnt(m_choice, 1);

				for (int i = 1; i < m_blanks; ++i) {
					for (int i = 0; i < path_cnt.size(); ++i) path_cnt[i] = 0;
					
					for (int c = 1; c <= m_choice; ++c) {
						if (! m_unique) {
							for (int k = 1; k <= c; ++k) {
								path_cnt[c - 1] += path_cnt_prev[k - 1];
							}
						}
						else {
							for (int k = 1; k <= c - 1; ++k) {
								path_cnt[c - 1] += path_cnt_prev[k - 1];
							}
						}
					}
					path_cnt_prev.assign(path_cnt.begin(), path_cnt.end());
				}

				for (int i = 0; i < path_cnt.size(); ++i) {
					num_ptrns += path_cnt[i];
				}

				return num_ptrns;			
			}
		}

		friend class Lottery;
		friend class Lottery::LessPtnrsRule;
	};

	struct LessPtnrsRule {
		bool operator() (const Rule* lhs, const Rule* rhs) const {
			Rule::counter_t lhs_ptrn = lhs->num_of_patterns();
			Rule::counter_t rhs_ptrn = rhs->num_of_patterns();

			if (lhs_ptrn == rhs_ptrn) {
				return lhs->m_name < rhs->m_name;
			}
			else {
				return lhs_ptrn < rhs_ptrn;
			}
		}
	};

public:
	vector<string> sortByOdds(vector<string> rules) {
		vector<Rule*> ptrn_list(rules.size());

		for (int i = 0; i < rules.size(); ++i) {
			ptrn_list[i] = new Rule(rules[i]);
		}
		sort(ptrn_list.begin(), ptrn_list.end(), LessPtnrsRule());

		vector<string> result_list(rules.size());
		for (int i = 0; i < rules.size(); ++i) {
			result_list[i] = ptrn_list[i]->GetName();
		}

		return result_list;
	}
};

submit後に気付いたこと：

• 「必ず昇順」かつ「同じ数値は現れない」場合は、ただのコンビネーション()になることに、他の人のコードを見て気付いた。
• Practiceでは、メニューからすぐにシステムテストを走らせることができる（メイン画面のPractice Options→Run System Test）。やってみたら、1カ所初期値を間違えていて「当てる数の個数」が1個のときに間違った答えになっていた...（上のコードは直したもの）

これを時間制限付きでやるのはなかなかしんどそうです。また今度トライしてみよう。