５．４ ハッシュ（時間切れ版）

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

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

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

５．３ 二分探索

いわゆるバイナリサーチですね。知識で知っているのと自分で書くのとは大違いで大変です。

#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static int binarySearch(int S[], int n, int T[], int q) {
  int found = 0;
  for (int i = 0; i < q; i++) {
    int left = 0;
    int right = n;
    while (left < right) {
      int mid = (left + right) / 2;
      if (T[i] == S[mid]) {
        found++;
        left = right;
      } else if (T[i] < S[mid]) {
        left = left;
        right = mid;
      } else {
        left = mid + 1;
        right = right;
      }      
    }    
  }
  return found;
}

int main() {
  int n, q;
  array<int, 100000> S;
  array<int, 50000> T;

  cin >> n;
  inputArray(S.data(), n);

  cin >> q;
  inputArray(T.data(), q);

  int found = binarySearch(S.data(), n, T.data(), q) ;
  
  cout << found << endl;
  
  return 0;
}

解説のコードではサーチ部分を関数化してました。そちらのほうが見やすいので清書。

#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static bool binarySearch(int S[], int n, int search) {
  int left = 0;
  int right = n;
  int mid = 0;
  while (left < right) {
    mid = (left + right) / 2;
    if (search == S[mid]) {
      return true;
    } else if (search < S[mid]) {
      left = left;
      right = mid;
    } else {
      left = mid + 1;
      right = right;
    }      
  }
  return false;
}

int main() {
  int n, q;
  array<int, 100000> S;
  array<int, 50000> T;

  cin >> n;
  inputArray(S.data(), n);

  cin >> q;
  inputArray(T.data(), q);
  
  int found = 0;
  for (int i = 0; i < q; i++) {
    if (binarySearch(S.data(), n, T[i])) {
      found++;
    }
  }

  cout << found << endl;
  
  return 0;
}

５．２ 線形検索（番兵版）

番兵の説明があったのでそのまま入れてみます。

#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static int linearSearch(int A[], int sentinel) {
  int i = 0;
  for (; A[i] != sentinel; i++);
  return i;
}

int main() {
  array<int, 10000 + 1> N;
  array<int, 500> Q;
  int s, t;

  cin >> s;
  inputArray(&N[0], s);

  cin >> t;
  inputArray(&Q[0], t);

  int found = 0;
  for (int i = 0; i < t; i++) {
    // set a sentinel
    N[s] = Q[i];
    if (linearSearch(&N[0], Q[i]) != s) {
      found++; 
    }
  }
  cout << found << endl;  

  return 0;
}

判定が減って効率的とのことですが、実測してないのでどこまで速いのかはようわかりません。

５．２ 線形検索

まずはそのまま書いてみます。内側ループを抜ける条件が微妙ですが、関数化するのを忘れていたためです。もっと丁寧にやらないといけませんね。

#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

int main() {
  array<int, 10000> N;
  array<int, 500> Q;
  int s, t;

  cin >> s;
  inputArray(&N[0], s);

  cin >> t;
  inputArray(&Q[0], t);

  int found = 0;
  for (int i = 0; i < t; i++) {
    for (int j = 0; j < s; j++) {
      if (N[j] == Q[i]) {
        found++; 
        // exit loop
        j = N.size();
      }
    } 
  }
  cout << found << endl;  

  return 0;
}

４．６ データ構造の応用：面積計算

これは面積のマージ部分のロジックが全然思いつかなくてダメでした。。解説を読みつつ書いたものがコレ。

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

static const char DOWN = '\\';
static const char EVEN = '_';
static const char UP = '/';

struct AREA {
  int index;
  int area;
};

int main() {
  string data;
  cin >> data;

  stack<int> input;
  vector<AREA> answers;
  AREA current = {};
  int lastIndex = 0;
  int total = 0;
  for (int i = 0; i < data.length(); i++) {
    switch (data[i]) {
    case DOWN:
      input.push(i);
      break;
    case EVEN:
      break;
    case UP:
      if (input.empty()) {
        continue;
      }
      lastIndex = input.top();
      input.pop();
      current.area = i - lastIndex;
      current.index = lastIndex;
      total += current.area;
      while (answers.size() > 0 && answers.back().index > lastIndex) {
        current.area += answers.back().area;
        answers.pop_back();
      }
      answers.push_back(current);
      break;
    default:
      break;
    }
  }

  cout << total << endl;  
  cout << answers.size();
  for (AREA answer : answers) {
      cout << " " << answer.area;
  }  
  cout << endl;

  return 0;
}

面積のマージ条件に、標高の概念を採り入れてみたのですが、入力データと答えに相当する stack/vector を、ひとつの箱でやろうとして混乱してしまい、結局解けませんでした。一通り本書を終えた後にリベンジしたいところです。

４．４ 連結リスト（手動編）、 ４．５ 標準ライブラリのデータ構造

では、連結リストを手動で・・・と思いましたが、昔自分で作ったことがあるので割愛します。なお、一つ前の記事で「stdin 周りで苦労した」というのは、cin と fgets と scanf を混ぜて使ったら、改行コードの処理が想定しない動きをしてくれたので、仕方なく fgets で一気に読み取るように変更しました。

さて「４．５」は・・・なんと、ここで STL の解説がガッツリあったのですね。先に目次を読んでおけばよかったですね。。

４．４ 連結リスト

これは苦労しました。。主に stdin 周りで無駄に苦労しました。。かなり汚いコードですが清書は後日。

#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

enum COMMAND_TYPE {
  INSERT,
  DELETE,
  DELETE_FIRST,
  DELETE_LAST
};

static COMMAND_TYPE fetch(string& st) {
  const string CDF = "deleteFirst";
  const string CDL = "deleteLast";
  const string CD = "delete";
  const string CI = "insert";
  
  if (st.find(CI) != string::npos) {
    return INSERT;
  } else if (st.find(CDF) != string::npos) {
    return DELETE_FIRST;
  } else if (st.find(CDL) != string::npos) {
    return DELETE_LAST;
  } else {
    return DELETE;
  }
}

static void fetchCommand(list<int>& clist, int n) {
  COMMAND_TYPE type;
  string command;
  int number;
  list<int>::iterator p;
  char buf[50];
  for (int i = 0; i < n; i++) {
    memset(buf, sizeof buf, 0);
    fgets(buf, sizeof buf, stdin);
    command = buf;
    type = fetch(command);
    switch (type) {
      case INSERT:
        number = atoi(&buf[7]);
        clist.push_front(number);
        break;
      case DELETE:
        number = atoi(&buf[7]);
        p = find(clist.begin(), clist.end(), number);
        if (p != clist.end()) {
          clist.erase(p);
        }
        break;
      case DELETE_FIRST:
        clist.pop_front();
        break;
      case DELETE_LAST:
        clist.pop_back();
        break;
    }
   }
}

int main() {
  char buf[50] = {};
  fgets(buf, sizeof buf, stdin);
  int n = atoi(buf);

  list<int> commandList;
  fetchCommand(commandList, n);

  list<int>::iterator it = commandList.begin();
  bool first = true;
  while (it != commandList.end()) {
    if (first) {
      cout << *it;
      first = false;
    } else {
      cout << " " << *it;
    }
    it++;
  }
  cout << endl;  

  return 0;
}