C-merのブログ

ザ・雑記

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;
    }
};