TopCoder SRM 516 DIV2
Rating: 1026(緑)→1061(緑)
250、500共に不要な悩み方をして相当時間をかけてしまい、当初500位台だったので爆死を覚悟したが、System Testが大荒れになってくれたおかげで100位台まで上がり救われた。
250: NetworkXZeroOne
#include <iostream> #include <sstream> #include <string> #include <vector> #include <algorithm> using namespace std; class NetworkXZeroOne { public: char getOpposite(char c) { if (c == 'o') return 'x'; if (c == 'x') return 'o'; return c; } string reconstruct(string message) { for (int h = 0; h < message.size(); ++h) { for (int i = 0; i < message.size(); ++i) if (message[i] == '?') { int idx; if (h % 2) idx = i + (i % 2 ? 1: -1); else idx = i + (i % 2 ? -1 : 1); if (0 <= idx && idx < message.size()) message[i] = getOpposite(message[idx]); } } return message; } };
最初頭から2つづつ区切っていき、同じ区切りの中のもう片方を見れば良いのでは?(それが「必ず1つに定まる答えがある」と同値だと錯覚した)とか考えて見事にサンプルケースが通らず死んだ。
実は未だにどうして通るのか理解していない。
とくにmessage.size()回繰り返せば全ての?を埋められるというあたりが理解できていない。
500: NetworkXOneTimePad
#include <iostream> #include <sstream> #include <string> #include <vector> #include <set> using namespace std; class NetworkXOneTimePad { public: inline string strxor(string x, string y) { string res; res.reserve(x.size()); for (int i = 0; i < x.size(); ++i) res += ((x[i] - '0') ^ (y[i] - '0')) + '0'; return res; } int crack(vector <string> plaintexts, vector <string> ciphertexts) { set<string> P; set<string> K; for (int i = 0; i < plaintexts.size(); ++i) P.insert(plaintexts[i]); for (int i = 0; i < ciphertexts.size(); ++i) for (int j = 0; j < plaintexts.size(); ++j) K.insert(strxor(ciphertexts[i], plaintexts[j])); set<string> res; for (set<string>::iterator it = K.begin(); it != K.end(); ++it) { int f = 1; for (int i = 0; i < ciphertexts.size(); ++i) { if (P.find(strxor(*it, ciphertexts[i])) == P.end()) { f = 0; break; } } if (f) res.insert(*it); } return res.size(); } };
これまたどうやって解くのか不要な悩み方をした。実際解き終えてみれば、たしかに500の難易度の問題である。しかし、問題文が複雑かつテストケースが弱かったので、斜め読みして落とした人は相当いたらしい。
1000:
読む時間なかった