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; } };