読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 516 DIV2

Programming Algorithm TopCoder

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:

読む時間なかった