SRM 516 250pt: NetworkXOneTimePad

TopCoder

問題概要

長さL(<50)のビット列を考える。平文がN(<50)個、暗号文がM(<50)個与えられる。暗号化の方法はワンタイムパッドで、任意の暗号文Cに対して平文Pが存在するような暗号鍵が何通り有るか求める問題。

考えたこと

  • ある暗号文と対応する平文を全通り試せば鍵の候補は全部出せる。
  • ん？何だこれ。実装するだけにしか見えない。
  • 書く。サンプル合わない。問題文の解釈間違いに気付いて微修正。通った。
  • 同じ鍵が複数有ったときに重複して数える人はいるはずなのでそういうテストケースを試してみる。
  • 平文の集合も暗号文の集合も重複は無いらしい。なんじゃそりゃ。これじゃ落ちようがないや。
  • チャレンジフェーズで、N*M通りのxorをセットに突っ込んでる青コーダーの方がいた。
  • それでサンプル通るのかよ。と思って改めて確認してみたらこのサンプルは実に弱い。
  • 適当に投げようとしたら答えは少なくとも一つはないとダメだと怒られた。修正して答えが唯一つに定まるようなのを投げたら無事落とせた。
  • まったく同じ間違いしてる人がもう一人いたので同じテストケース投げて落としておいた。
  • 今回は自明に間違ってるコードが中々落ちずに残ってたり、System Testで落ちてた人の多い撃墜力の低い部屋だった。

本番で通ったコード

計算量O(N*M*L*log M)。今見返したらalgorithmはincludeしなくても良い。

#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace  std;

struct NetworkXOneTimePad {

	int crack(vector <string> plaintexts, vector <string> ciphertexts) {
		set<string> ans;

		set<string> plains(plaintexts.begin(), plaintexts.end());

		for(int i=0; i<(int)plaintexts.size(); i++){
			string key = get_xor(plaintexts[i], ciphertexts[0]);

			bool ok = true;
			for(int j=0; j<(int)ciphertexts.size(); j++){
				ok &= (plains.find(get_xor(ciphertexts[j], key)) != plains.end());
			}

			if(ok){
				ans.insert(key);
			}
		}

		return ans.size();
	}

	string get_xor(const string& a, const string& b){
		string ret = a;
		for(int i=0; i<(int)a.length(); i++){
			ret[i] = ((a[i] ^ b[i])&1) + '0';
		}
		return ret;
	}
};

計算量を落とす

文字列をそのまま扱うのは計算量が増えるので最初に文字列を整数に変換する。
計算量O((N+M)*L + N*M*log N)。

#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>

typedef long long int64;
using namespace  std;

struct NetworkXOneTimePad {

	int crack(vector <string> plaintexts, vector <string> ciphertexts) {

		vector<int64> plains, ciphs;
		char *p;

		for(int i=0; i<(int)plaintexts.size(); i++){
			plains.push_back( strtoll(plaintexts[i].c_str(), &p, 2) );
		}
		sort(plains.begin(), plains.end());
		for(int i=0; i<(int)ciphertexts.size(); i++){
			ciphs.push_back( strtoll(ciphertexts[i].c_str(), &p, 2) );
		}

		int ret = 0;
		for(int i=0; i<(int)plains.size(); i++){
			int64 key = plains[i] ^ ciphs[0];

			bool ok = true;
			for(int j=0; j<(int)ciphs.size(); j++){
				ok &= (binary_search(plains.begin(), plains.end(), ciphs[j] ^ key));
			}

			if(ok){
				ret++;
			}
		}

		return ret;
	}

};