http://community.topcoder.com/stat?c=round_overview&er=5&rd=15491
250に21分。チャレンジ1回成功。220.76点。レートは1335から1440へ。Room 39。
Problem | Status | Points | |
---|---|---|---|
250 | FoxAndMp3 | System Test Passed | 170.76 |
500 | MagicMolecule | Opened | 0.00 |
1000 | CandyOnDisk | Unopened |
http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491
21分。
以下は提出した実装(システムテストをパス)。
class FoxAndMp3 { public: std::vector<std::string> playList(int n) { std::set<int> set; for (int i = 1; i <= n; i *= 10) for (int j = 0; j < 50; j ++) if (i + j <= n) set.insert(i + j); std::vector<std::string> filenames; EACH (it, set) filenames.push_back(filename(*it)); std::sort(ALL(filenames)); if (filenames.size() > 50) filenames.resize(50); return filenames; }; private: std::string filename(int i) const { std::ostringstream os; // XXX os << i << ".mp3"; return os.str(); }; };
これを参考にした実装は以下(システムテスト済)。
class FoxAndMp3 { public: std::vector<std::string> playList(int n) { std::vector<std::string> filenames; for (int i = 1; i < 100; i ++) if (i <= n) filenames.push_back(filename(i)); for (long long i = 100; i <= n; i *= 10) for (int j = 0; j < 50; j ++) if (i + j <= n) filenames.push_back(filename(i + j)); std::sort(ALL(filenames)); if (filenames.size() > 50) filenames.resize(50); return filenames; }; private: std::string filename(int i) const { std::ostringstream os; os << i << ".mp3"; return os.str(); }; };
これを参考にした実装は以下(システムテスト済)。
class FoxAndMp3 { public: std::vector<std::string> playList(int n) { std::vector<std::string> filenames; for (long long i = 1; i <= n; i *= 10) for (int j = i; j < std::min(i + 50, i * 10); j ++) if (j <= n) filenames.push_back(filename(j)); std::sort(ALL(filenames)); if (filenames.size() > 50) filenames.resize(50); return filenames; }; private: std::string filename(int i) const { std::ostringstream os; os << i << ".mp3"; return os.str(); }; };
30分ほど方向性を誤った実装を行い、未提出に終わった。
以下はシステムテストを通らない実装。
class MagicMolecule { public: int maxMagicPower(std::vector<int> magicPower, std::vector<std::string> magicBond) { magicPower_ = magicPower; n_ = magicPower.size(); m_ = (2 * n_ + 2) / 3; adj_.assign(n_, 0); for (int i = 0; i < n_; i ++) for (int j = 0; j < n_; j ++) if (i == j || magicBond[i][j] == 'Y') adj_[i] |= 1LL << j; return dfs(0, (1LL << n_) - 1); }; private: int dfs(int i, long long bits) { if (i == n_) return -1; if (bitcount(bits) < m_) return -1; if (cliques_are_valid(bits)) return sum(bits); if (bits & (1LL << i)) { return std::max(dfs(i + 1, bits & adj_[i]), dfs(i + 1, bits - (1LL << i))); } else { return dfs(i + 1, bits); } }; int bitcount(long long bits) const { int c = 0; for (int i = 0; i < n_; i ++) if (bits & (1LL << i)) c ++; return c; }; int sum(long long bits) const { int s = 0; for (int i = 0; i < n_; i ++) if (bits & (1LL << i)) s += magicPower_[i]; return s; }; bool cliques_are_valid(long long bits) const { for (int i = 0; i < n_; i ++) if (bits & (1LL << i)) if ((bits & adj_[i]) != bits) return false; return true; }; private: std::vector<int> magicPower_; std::vector<long long> adj_; int n_; int m_; };
ここまでを元に実装した結果は以下(システムテストをパス)。
class MagicMolecule { public: int maxMagicPower(std::vector<int> magicPower, std::vector<std::string> magicBond) { magicPower_ = magicPower; n_ = magicPower.size(); m_ = (2 * n_ + 2) / 3; adj_.assign(n_, 0); for (int i = 0; i < n_; i ++) for (int j = 0; j < n_; j ++) if (i == j || magicBond[i][j] == 'Y') adj_[i] |= 1LL << j; return dfs(0, (1LL << n_) - 1); }; private: int dfs(int i, long long bits) { if (i == n_) return -1; int r = 0; if (bitcount(bits) < m_) return r = -1; for (int j = i; j < n_; j ++) if (bits & (1LL << j)) if ((bits & adj_[j]) != bits) return r = std::max(dfs(j + 1, bits & adj_[j]), dfs(j + 1, bits - (1LL << j))); return sum(bits); }; int bitcount(long long bits) const { int c = 0; for (int i = 0; i < n_; i ++) if (bits & (1LL << i)) c ++; return c; }; int sum(long long bits) const { int s = 0; for (int i = 0; i < n_; i ++) if (bits & (1LL << i)) s += magicPower_[i]; return s; }; private: std::vector<int> magicPower_; std::vector<long long> adj_; int n_; int m_; };