線形探索, 二分探索, ダブルハッシュを使用したオープンアドレス法, 二分探索の応用問題

##[ALDS1_4_A](https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_A)
###線形探索
linearSearch内で配列の末尾にkeyを追加する。
番兵を用いた線形探索と言われる手法で終了判定を記載しなくて良いので、定数倍の高速化を行うことができます。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int S[10000];
int n, q, ans;

bool linearSearch(int s[], int n, int key){
    
    int i=0;
    s[n] = key;
    while(s[i] != key) i++;
    
    return i != n;
}

int main(int argc, const char * argv[]) {
    cin >> n;
    rep(i, n){
        cin >> S[i];
    }
    
    cin >> q;
    rep(i, q){
        int t;
        cin >> t;
        if(linearSearch(S, n, t)) ans++;
    }

    cout << ans << endl;
    return 0;
}
```

##[ALDS1_4_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B)
###二分探索
蟻本のくじ引きで出題された二分探索ですね。
AtCoderでも高速化の為にC〜D問題で出題されていました。
left, rightでmidを計算してkeyがどの範囲にあるか判定していきます。
keyは配列[mid]より小さいか判定し、right = mid, leftはmid + 1と覚えましょう。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int BinarySearch(int S[],int n, int key){
    
    int left = 0;
    int right = n;
    
    while(left < right){
        int mid = (right + left) / 2;
        
        if(S[mid] == key) return mid;
        else if(S[mid] > key) right = mid;
        else left = mid+1;
    }
    
    return -1;
}

int main(int argc, const char * argv[]) {
    int S[100000];
    int n, q, ans=0;
    
    cin >> n;
    rep(i, n){
        cin >> S[i];
    }
    
    cin >> q;
    rep(i, q){
        int t;
        cin >> t;
        if(BinarySearch(S, n, t) >= 0) ans++;
    }

    cout << ans << endl;
    return 0;
}
```

##[ALDS1_4_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_C)
###辞書

最初に考えた事は登録された単語をmapにキーとして保存。
キーが存在したらyesを返す。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    map<string, int> m;
    rep(i, N){
        string cmd, str;
        cin >> cmd >> str;
        
        if(cmd == "insert") m.insert(make_pair(str, 0));
        else if(cmd == "find"){
            if(m.find(str) == m.end()) cout << "no" << endl;
            else cout << "yes" << endl;
        }
    }
    
    return 0;
}
```

全てACを通してなんか違うなと感じました。
これだとmapの使い方でアルゴリズムじゃない。
言語解説に以下のプログラムが記載されていました。

```C++:C++
#include
#include

#define M /* your task*/
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return /* your task */; }
int h2(int key){ return /* your task */; }

int find(char str[]){

    /* your task */

}

int insert(char str[]){

    /* your task */

}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){
	    insert(str);
	} else {
	    if (find(str)){
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}
```

どう見てもハッシュ法が関連した問題ですね。
何も分からないという事が分かった。

###アルゴリズム論　第５回会議([ハッシュ法](http://yamweb.comp.ae.keio.ac.jp/japanese/2011-A%E8%AB%96/5-before-20111028.pdf)の解説)
ハッシュとは？
「挿入・探索・削除がＯ（１）でできるデータの個数ｎに依存しない探索技法」
mapで解いた方法はdirect accessと呼ばれる手法ですね。
ハッシュに慣れる為に参考ページにある問題を解きましょう。

###P13.問題１
以下のハッシュ関数を用いて、表の各文字列に対応するハッシュ値を求めよ。

```C++:C++
int hash(char* s){
    int i=0;
    while(*s) i += *s++;
    return i % 11;
}
```

```C++:C++
int Hash(char* s){
    int i=0;
    while(*s) i += *s++;
    return i % 11;
}

int main(int argc, const char * argv[]) {    
    vector<int> v(6);
    rep(i, 6){
        char ch[20];
        cin >> ch;
        
        v[i] = Hash(&ch[0]);
    }
    
    rep(i, 6){
        cout << v[i] << endl;
    }

    return 0;
}
```

###回答
| 文字列      | ハッシュ値     |
|:-----------|------------:|
| fukuzaki   | 5           |
| watanabe   | 10          |
| oono       | 3           |
| kawashima  | 4           |
| nakano     | 5           |
| miura      | 3           |

###「fukuzaki」と「nakano」は同じハッシュ値
ハッシュ法はこのように同じ値になる語が出てきます。
その際の対応手法が、チェイン法とオープンアドレス法です。

###チェイン法
チェイン法は同じハッシュ値が出現した際に、データを連結リストに繋ぎます。
ハッシュ法は、連結リストの先頭を指すポインタの配列。
今回の解説プログラムの手法とは異なリますね。

###オープンアドレス法
ある一定の方法で，空セルを探して，そこに新たな項目を挿入する方法。
下記３種類の方法があります。

1. 線形探査
2. 平方探査
3. ダブルハッシュ

###ダブルハッシュ
キーに対して2度目のハッシュを行い，得られた結果をステップ幅として使う。

```C++:C++
int h1(int key){ return /* your task */; }
int h2(int key){ return /* your task */; }
```

解説プログラムの上記の箇所にハッシュ作成関数が２つあります。
ダブルハッシュを勉強していきましょう。

###P28.問題１
(1)の表に示した文字列を上から順番に、要素数11のハッ
シュ表に格納せよ。

オープンアドレス法はダブルハッシュ法。ダブルハッシュのハッシュ関数は以下のとおり。
ｈs（ｘ）＝（７ – （k % ７）） ％ １1
kはハッシュ関数hash()内の11で割った余りを求める直前の変数iの値

```C++:C++
int Hash2(char* s){
    int i=0;
    while(*s) i += *s++;
    return (7-(i%7)) % 11;
}

int Hash1(char* s){
    int i=0;
    while(*s) i += *s++;
    return i % 11;
}

int main(int argc, const char * argv[]) {
    char hash_table[11][20]={0};
    
    rep(i, 6){
        char ch[20];
        cin >> ch;
        
        int k=0;
        while(true){
            int hash_index = (Hash1(&ch[0]) + k * Hash2(&ch[0])) % 11;
            if(strcmp(hash_table[hash_index], ch) == 0) break;
            if(strlen(hash_table[hash_index]) == 0){
                strcpy(hash_table[hash_index], ch);
                break;
            }
            k++;
        }
    }
    
    rep(i, 11){
        cout << i << ' ' << hash_table[i] << endl;
    }

    return 0;
}
```

###回答
| ハッシュ値    |   文字列    |
|:-----------|------------:|
| 0          |             |
| 1          |             |
| 2          |             |
| 3          | oono        |
| 4          | kawashima   |
| 5          | fukuzaki    |
| 6          |             |
| 7          | miura       |
| 8          |             |
| 9          | nakano      |
| 10         | watanabe    |

ここまで理解したのでダブルハッシュを「ALDS1_4_C」にて使用しましょう。

###ダブルハッシュを使用したオープンアドレス法による解法
```C++:C++
#include <stdio.h>
#include <string.h>

using namespace std;
using ll =long long;

#define M 1000003
#define L 14

char H[M][L]; /* Hash Table */

int GetChar(char ch){
    if ( ch == 'A') return 1;
    else if ( ch == 'C') return 2;
    else if ( ch == 'G') return 3;
    else if ( ch == 'T') return 4;
    return 0;
}

ll GetKey(char str[]){
    ll sum=0, p=1, i;
    for (i=0; i<strlen(str); i++){
        sum += p*(GetChar(str[i]));
        p *= 5;
    }
    return sum;
}

int Hash1(ll key){ return key % M; }
int Hash2(ll key){ return (11-(key%11)) % M; }

int find(char str[]){
    ll key = GetKey(str);
    int k=0;
    while(true){
        int hash_index = (Hash1(key) + k*Hash2(key)) % M;
        if(strcmp(H[hash_index],str) == 0) return 1;
        if(strlen(H[hash_index]) == 0){
            return 0;
        }
        k++;
    }
    return 0;
}

int insert(char str[]){
    ll key = GetKey(str);
    int k=0;
    while(true){
        ll hash_index = (Hash1(key) + k*Hash2(key)) % M;
        if(strcmp(H[hash_index],str) == 0) return 1;
        if(strlen(H[hash_index]) == 0){
            strcpy(H[hash_index], str);
            return 1;
        }
        k++;
    }
    return 0;
}

int main(){
    int i, n;
    char str[L], com[9];
    for (i=0; i<M; i++) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for(i=0; i<n; i++){
        scanf("%s %s", com, str);
    
        if (com[0]=='i'){
            insert(str);
        }else{
            if(find(str)){
                printf("yes\n");
            }else{
                printf("no\n");
            }
        }
    }

    return 0;
}
```

__解けた!__

##[ALDS1_4_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_D)
###割り当て

二分法、二分探索の応用問題です。
積荷の採用値０から最大１０００００＊１００００の中央値を基準を出力。
各トラックへ積める荷物の数、重量をカウントして判定。
全てトラックへ積めたら中央値を最大値へ変更。
できなかった場合は、中央値を最小値へ変更。
最後のrightが「最大積載量Pの最小値」となります。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int BinarySearch(int n, int k, int s[], int p){
    int count = 0;
    rep(i, k){
        int sum=0;
        while(sum + s[count] <= p){
            sum += s[count];
            count++;
            if(n<=count) return n;
        }
    }
    return count;
}

void Solve(int n, int k, int s[]){
    int left=0;
    int right=100000*10000;
    while(right - left>1){
        int mid = (right+left)/2;
        int v = BinarySearch(n, k, s, mid);
        if(v>=n) right=mid;
        else left=mid;
    }
    cout << right << endl;
}

int main(int argc, const char * argv[]) {
    int n, k;
    cin >> n >> k;
    
    int s[100000]={0};
    rep(i, n){
        cin >> s[i];
    }
    
    Solve(n, k, s);
    
    return 0;
}
```