SRM516 Div1 Easy(250), Div2 Medium(500) NetworkXOneTimePad
鍵の候補は、cipher[0]^plain[0], cipher[0]^plain[1], cipher[0]^plain[2], ……。平文が全て異なるという問題の制約から、この鍵の候補も全て異なる。このなかで全ての暗号文に平文が存在するものを数える。
#include <string> #include <vector> #include <algorithm> using namespace std; long long tolong( string t ) { int n = (int)t.size(); long long r = 0; for ( int i=0; i<n; i++ ) if ( t[i]!='0' ) r |= 1ll<<(n-i-1); return r; } class NetworkXOneTimePad{public: int crack( vector <string> plaintexts, vector <string> ciphertexts ) { int pn = (int)plaintexts.size(); int cn = (int)ciphertexts.size(); vector<long long> plain(pn); for ( int i=0; i<pn; i++ ) plain[i] = tolong(plaintexts[i]); vector<long long> cipher(cn); for ( int i=0; i<cn; i++ ) cipher[i] = tolong(ciphertexts[i]); int ans = 0; for ( int i=0; i<pn; i++ ) { long long key = plain[i]^cipher[0]; bool f = true; for ( int j=0; j<cn; j++ ) if ( find(plain.begin(),plain.end(),cipher[j]^key) == plain.end() ) f = false; if ( f ) ans++; } return ans; }};