TopCoder SRM144 DIV1 (300)
やっぱりちゃんと勉強しなきゃ、ということでTopCoder SRMに挑戦してみることにしました。でもまだ自信がないのでPracticeだけ。
登録の手順などは、こちらを参考にさせていただきました。→ http://d.hatena.ne.jp/gnarl/20080828/1219893152
まずは、Practice Rooms→SRMsで一番最初にある、SRM144 DIV1から。
300点問題の概要は:
- 文字列表記された2進数を暗号化する手順が定義されている。
- 手順は、「各桁ごとに、前後合わせた3桁分の数字を合計した数に置き換える」というもの。
- この暗号化された数値列(定義から0〜3が現れる)を入力として、元の2進数を復元して返す関数を書け。
とういもの。
親切なことに、実装すべきアルゴリズムが問題文中で実例付きで解説されています。基本的にはそれをそのままコードに落とせばよさそうなのですが...ループへのまとめ方とか、境界条件の取り方とか細かいところで迷って時間がかかってしまいました。
コンテストでは、プラグインをインストールして自前のエディタとの連携やテストコードの自動生成をやる人が多いようですが、まずは様子を見るつもりで単に横でMS Visual Studioを立ち上げ、コンソールアプリのプロジェクトを作ってそこにコードを切り貼りして試しました。
ということでこんなコード:
#include <iostream> #include <vector> #include <string> using namespace std; class BinaryCode { string decode_with_assume(int p0, string message) { string result_str; result_str.append(1, p0 + '0'); int pv = p0, ppv = 0, d = p0; for (size_t i = 0; i < message.size(); ++i) { int q = message[i] - '0'; int p = q - d; if (i == message.size() - 1) { if (q == d) return result_str; else return string("NONE"); } if (p == 0 || p == 1) result_str.append(1, p + '0'); else return string("NONE"); d += p; d -= ppv; ppv = pv; pv = p; } return result_str; } public: vector<string> decode(string message) { vector<string> result_cons; result_cons.push_back(decode_with_assume(0, message)); result_cons.push_back(decode_with_assume(1, message)); return result_cons; } };
TopCoder SRM144 DIV1 (550)
次の550点問題は、組合せの問題です。
・いろいろな種類の数当てゲームがある。ゲームのルールのリストが入力されるので、それを「当てやすい順」に並べ替えて返せ。
・ゲームのルールは、「使用する数の範囲(1から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個のときに間違った答えになっていた...(上のコードは直したもの)
これを時間制限付きでやるのはなかなかしんどそうです。また今度トライしてみよう。