SRM516 Div1 Easy - NetworkXOneTimePad

問題

　ciphertextsにある任意の数字が、plaintextsのどれかの数字にxorしたものに等しくなるようなキーの数を求めよ。

解法

　各暗号化済みの数字と暗号化前の数字のxorを取るとキーとなり得る数字を求められる。それの登場回数をmapで数えておく。キーとなる数が暗号化済みの数字数と同じ数だけ出てきたらそれはすべてに対してキーになっているということなので計算量はでこの問題が解けた。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class NetworkXOneTimePad {
public:
    int crack(vector<string> plaintexts, vector<string> ciphertexts) {
        vector<ll> p(plaintexts.size()), c(ciphertexts.size());
        for (ll i = 0; i < plaintexts.size(); i++) {
            p[i] = toLL(plaintexts[i]);
        }

        map<ll, ll> num;
        for (ll i = 0; i < ciphertexts.size(); i++) {
            c[i] = toLL(ciphertexts[i]);
            for (ll j = 0; j < plaintexts.size(); j++) {
                num[c[i] ^ p[j]]++;
            }
        }

        ll ans = 0;
        for (auto p : num) {
            if (p.second == ciphertexts.size()) {
                ans++;
            }
        }

        return ans;
    }
private:
    ll toLL(string binary) {
        ll result = 0;
        for (ll i = 0; i < binary.size(); i++) {
            if (binary[i] == '1') {
                result |= (1LL << (binary.size() - i - 1));
            }
        }
        return result;
    }
};