SRM 516 Div 1 - Problem 250 NetworkXOneTimePad
お久しぶりです.
問題
SRM 516 Div 1 - Problem 250 NetworkXOneTimePad
TopCoder Statistics - Problem Statement
使用言語
C++
問題概要
N個のビット列のplaintextsがある.各plaintextsにXORすると全てのciphertextsになるkeyが存在する.その数を求める.
方針
・全てのN個のビット列についてplaintextsにXORしてciphertextsの全てになるか調べる
→時間がかかる(最大2ˆ50)のでダメ
・XORであれば,plaintextsとciphertextsから変換に用いられたkeyの候補をXORで導ける.ciphertextsから全てのplaintextsについてXORするとkeyの候補がある.このkeyの候補は実際のkeyの集合を含む集合である.この候補が全てのciphertextから導かれる場合は,それはkeyである.
・出てきた回数はmapで管理
ex)
{"000", "111", "010", "101", "110", "001"}
{"011", "100"}
→011: 011, 100, 001, 110, 101, 010
100: 100, 011, 110, 001, 010, 101
両方のkeyの候補に含まれている.
所感
・諸事情で長時間プログラミングしていなかったので,さらに能力が落ちました.
・結論,mapは便利
コード
int N, lp, lc, ans = 0; map<string, int> mp; string myXOR (string p, string c) { string tmp(N, '0'); REP(i,N) tmp[i] = p[i] == c[i] ? '0' : '1'; return tmp; } class NetworkXOneTimePad { public: int crack(vector<string> plaintexts, vector<string> ciphertexts) { N = plaintexts[0].length(); lp = plaintexts.size(); lc = ciphertexts.size(); REP(i,lp){ REP(j,lc){ string key_tmp = myXOR(plaintexts[i], ciphertexts[j]); if (mp.find(key_tmp) == mp.end()) { mp[key_tmp] = 1; } else { mp[key_tmp]++; } } } for (auto itr = mp.begin(); itr != mp.end(); ++itr) { if (itr->second == lc) ans++; } return ans; } };