６．２ 全検索

再帰と計算結果をうまく組み合わる、この発想がなかなか出てきません。

#include <iostream>
#include <vector>

using namespace std;

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

static inline bool solve(int A[], int i, int n, int m) {
  if (m == 0) {
    return true;
  }
  
  if (i < n && m > 0) {
    return solve(A, i + 1, n, m) || solve(A, i + 1, n, m - A[i]);
  } else {
    return false;
  }
}

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

  vector<int> A(n);
  inputArray(&A[0], n);

  int q;
  cin >> q;

  int m;
  bool ans;
  for (int i = 0; i < q; i++) {
    cin >> m;
    ans = solve(&A[0], 0, n, m);
    cout << (ans ? "yes" : "no") << endl;
  }
  
  return 0;
}

solve の途中で m がマイナス値になったら打ち切る判定を一応入れてみました。

５．６ 探索の応用（バイナリサーチ版）

ということで、バイナリサーチを使う版です。積載量の絞り込みをバイナリサーチで行っていくのですね。数が大きくなると劇的な効果が出ますね。検索回数は log2(1000000000) = 約 30 回でした。

#include <iostream>
#include <vector>

//#include <cstdio>

using namespace std;

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

static inline int f(int A[], int num, uint64_t P, int k) {
    int i = 0, v = 0;
    for (uint64_t total = 0; (v < k) && (i < num); i++) {
      total += A[i];
      if (total > P) {
        total = 0;
        i--;
        v++;
      }
    }
    return i;
}

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

  vector<int> w(n);
  inputArray(&w[0], n);

  uint64_t left = 0;
  uint64_t right = 100000 * 10000;
  uint64_t mid;
  int v = 0;
  while (1 < right - left) {
    mid = (left + right) / 2;
    v = f(&w[0], n, mid, k);
    if (v < n) {
      left = mid;
    } else {
      right = mid;
    }
  }

  cout << right << endl;

  return 0;
}

５．６ 探索の応用（時間切れ版）

解説そのままやってみて、時間切れのパターン。ここまでは様式美です。ここからバイナリサーチをどう使うのだろう？

現時点でひとつだけ工夫したところは、入力時の最大値を覚えておいて、そこから P を増やしていく部分です。最大値が入らない積載量の探索は意味がないですからね。

#include <iostream>
#include <vector>

using namespace std;

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

static inline int f(int A[], int num, int P, int k) {
    int i = 0, v = 0;
    for (int total = 0; (v < k) && (i < num); i++) {
      total += A[i];
      if (total > P) {
        total = 0;
        i--;
        v++;
      }
    }
    return i;
}

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

  vector<int> w(n);
  int P = inputArray(&w[0], n);
  
  for (int v = 0; v < n; P++) {
    v = f(&w[0], n, P, k);
  }

  cout << (P - 1) << endl;

  return 0;
}

５．４ ハッシュ（解説版）

解説（というか答え）の写経版です。ハッシュ関数は、自力では思いつかないので、研究している人たちにおまかせするしかない感じです。

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

using namespace std;

static inline int charToInt(char c) {
  switch(c) {
  case 'A':
    return 1;
  case 'C':
    return 2;
  case 'G':
    return 3;
  case 'T':
    return 4;
  default:
    return 0;
  }  
}

static inline uint64_t getKey(const string& str) {
  uint64_t total = 0, p = 1;
  for (int i = 0; i < str.length(); i++) {
    total += p * (charToInt(str[i]));
    p *= 5;
  }  
  return total;
}

static const int M = 1046527;
static const int NUL = -1;
static const int L = 14;

static inline int h1(int key) {
  return key % M;
}

static inline int h2(int key) {
  return 1 + (key % (M - 1));
}

static vector<string> H(M);

static inline bool find(const string& str) {
  uint64_t key, h;
  key = getKey(str);
  for (int i = 0;; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if (H[h] == str) {
      return true;
    } else if (H[h].size() == 0) {
      return false;
    }
  }
  return false;
}

static inline bool insert(const string& str) {
  uint64_t key, h;
  key = getKey(str);
  for (int i = 0;; i++) {
    h = (h1(key) + i * h2(key)) % M;
    if (H[h] == str) {
      return true;
    } else if (H[h].size() == 0) {
      H[h] = str;
      return false;
    }
  }
  return false;
}

int main() {
  int n, h;

  cin >> n;

  string str, com;
  for (int i = 0; i < n; i++) {
    cin >> com >> str;
    if (com[0] == 'i') {
      insert(str);
    } else {
      cout << (find(str) ? "yes" : "no") << endl;
    }
  }
  return 0;
}

５．４ ハッシュ（自力版）

「ハッシュ」という言葉と、問題の図を参考に、自分なりに考えたのがこちら。「文字の種類は４つ」ということで、文字列を４進数とみなして、全部の組み合わせ分の bool 配列を持ち、insert 時に組み合わせを int 値にして、配列の index に読み替えてそこを true にする、という形式にしています。このあと解説を読みます。

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

static inline int charToInt(char c) {
  switch(c) {
  case 'A':
    return 0;
  case 'C':
    return 1;
  case 'G':
    return 2;
  case 'T':
    return 3;
  default:
    return -1;
  }  
}

static inline int strToInt(const string& str) {
  int total = charToInt(str[0]);
  int cur;
  for (int i = 1; i < str.length(); i++) {
    cur = charToInt(str[i]);
    total += pow(4, i) * (1 + cur);
  }  
  return total;
}

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

  vector<bool> dictionary(static_cast<size_t>(pow(4, 12)) + 4, false);
  string command, str;

  for (int i = 0; i < n; i++) {
    cin >> command >> str;
    if (command[0] == 'i') {
      dictionary[strToInt(str)] = true;
    } else {
        cout << (dictionary[strToInt(str)] ? "yes" : "no") << endl;
    }
  }
  return 0;
}

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

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

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