兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

5.4 ハッシュ(時間切れ版)

まずは「ハッシュ」という言葉をスルーしてそのまま書いた場合。これは時間切れになります。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;

  vector<string> dictionary;
  dictionary.reserve(1000000);
  string command, str;
  for (int i = 0; i < n; i++) {
    cin >> command >> str;
    if (command[0] == 'i') {
      dictionary.push_back(str);
    } else {
      const bool found = (dictionary.end() != find(dictionary.begin(), dictionary.end(), str));
      cout << (found ? "yes" : "no") << endl;
    }
  }

 return 0;
}

先頭文字で辞書を分けてみたのがこれ。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

static vector<string> dicA, dicC, dicG, dicT;

static inline vector<string>& getDictionary(char first) {
  switch (first) {
  case 'A':
    return dicA;
  case 'C':
    return dicC;
  case 'G':
    return dicG;
  case 'T':
  default:
    return dicT;
  }
}

int main() {
  int n;
  cin >> n;

  string command, str;
  for (int i = 0; i < n; i++) {
    cin >> command >> str;
    auto& dic = getDictionary(str[0]);
    if (command[0] == 'i') {
      dic.push_back(str);
    } else {
      const bool found = (dic.end() != find(dic.begin(), dic.end(), str));
      cout << (found ? "yes" : "no") << endl;
    }
  }

 return 0;
}

数秒ほど早くなりましたが、やはり最後は時間切れになります。文字列の比較とかやってるので当たり前という気はします。