データ構造
単方向連結リストの操作
// 初期化
void initialize()
{
top = -1; // リストの先頭を-1に設定
counter = 0; // 使用中のインデックスカウンター
}
// 先頭に要素を挿入
void insert_at_top(int value)
{
elements[counter] = value; // 値をカレントノードに格納
next_pointers[counter] = top; // カレントノードの次を現在の先頭に
top = counter; // 新しい先頭をカレントノードに
counter++;
}
// 指定位置に要素を挿入
void insert_at_position(int value, int position)
{
elements[counter] = value;
next_pointers[counter] = next_pointers[position]; // カレントノードの次を位置の次に
next_pointers[position] = counter; // 位置の次をカレントノードに
counter++;
}
// 要素の削除
void remove_at_position(int position)
{
next_pointers[position] = next_pointers[next_pointers[position]];
}
双方向連結リストの操作
// next_pointers[]: 要素の次へのポインタ, prev_pointers[]: 要素の前へのポインタ
// 初期化
void initialize()
{
next_pointers[0] = 1; // 0番目の次は1番目
prev_pointers[1] = 0; // 1番目の前は0番目で双方向リストを形成
counter = 2; // 2つのノードを使用済み
}
// 指定位置の右に要素を挿入
void insert_at_right(int value, int position)
{
elements[counter] = value;
next_pointers[counter] = next_pointers[position]; // カレントノードの次を位置の次に
prev_pointers[counter] = position; // カレントノードの前を位置に
prev_pointers[next_pointers[position]] = counter; // 位置の次の前をカレントノードに
next_pointers[position] = counter; // 位置の次をカレントノードに
counter++;
}
// 指定位置の要素を削除
void remove_at_position(int position)
{
next_pointers[prev_pointers[position]] = next_pointers[position];
prev_pointers[next_pointers[position]] = prev_pointers[position];
}
配列によるスタックの実装
int stack_array[MAX_SIZE], top_index = 0; // stack_array[]はスタック、top_indexはスタックトップポインタ
void push(int value)
{
stack_array[++top_index] = value; // スタックトップをインクリメントして値を格納
}
void pop()
{
top_index--; // スタックトップをデクリメント（実際の要素は上書きされる）
}
int get_top()
{
return stack_array[top_index]; // スタックトップ要素を取得
}
int is_empty()
{
return top_index; // スタックが空の場合top_index=0
}
配列によるキューの実装
int queue_array[MAX_SIZE], front = 0, rear = -1; // queue_array[]はキュー、frontは先頭、rearは末尾
void enqueue(int value)
{
queue_array[++rear] = value; // 末尾をインクリメントして値を格納
}
void dequeue()
{
front++; // 先頭をインクリメント
}
int get_rear()
{
return queue_array[rear]; // 末尾要素を取得
}
int is_empty()
{
return front == rear; // 先頭と末尾が同じならキューは空
}
単調スタック
各数値の左側で最も近く、それより小い数値の位置を計算
for(int i = 0; i < n; i++)
{
int current_value;
cin >> current_value;
while(top_index && stack_array[top_index] >= current_value)
top_index--; // スタックから要素をポップ
if(top_index)
cout << stack_array[top_index];
else
cout << "-1";
}
KMP文字列マッチング
// 朴素な方法：暴力
for(int i = 1; i <= n; i++)
{
int match_flag = 1;
for(int j = 1; j <= m; j++)
{
if(text[i] != pattern[j])
{
match_flag = 0;
break;
}
}
}
// next_array[]の計算（パターン文字列に対して、開始位置は1）
// i番目の要素のnext_array[]を計算、つまりパターン文字列のi番目の要素がメイン文字列の
// ある位置と一致しない場合、パターン文字列のどの位置から再び比較を開始すべきか
for(int i = 2, j = 0; i <= n; i++)
{
while(j && pattern[i] != pattern[j+1]) // 一致しない場合、以前の位置に戻る
j = next_array[j];
if(pattern[i] == pattern[j+1])
j++;
next_array[i] = j; // 一致しない場合next_array[i] = next_array[j]
}
// マッチングプロセス
for(int i = 1, j = 0; i <= n; i++)
{
while(j && text[i] != pattern[j+1])
j = next_array[j];
if(text[i] == pattern[j+1])
j++;
if(j == m)
{
cout << i - m + 1; // メイン文字列でパターン文字列と一致する部分文字列の最初の要素のインデックスを出力
}
}
// next_array配列は、text[i] != pattern[j+1]の場合、jをどれだけ戻すかを記録
Trie木
文字列の高速な保存と検索
#include<iostream>
using namespace std;
const int MAX_SIZE = 100010;
int node_counter;
int child_nodes[MAX_SIZE][26];
int node_counts[MAX_SIZE];
void insert_string(string str)
{
int current = 0;
for (int i = 0; i < str.size(); i++)
{
int char_index = str[i] - 'a';
if (!child_nodes[current][char_index])
child_nodes[current][char_index] = ++node_counter;
current = child_nodes[current][char_index];
}
node_counts[current]++;
}
int query_string(string str)
{
int current = 0;
for (int i = 0; i < str.size(); i++)
{
int char_index = str[i] - 'a';
if (!child_nodes[current][char_index])
return 0;
current = child_nodes[current][char_index];
}
return node_counts[current];
}
int main()
{
int operations;
cin >> operations;
while (operations--)
{
char operation_type;
cin >> operation_type;
string input_str;
if (operation_type == 'I')
{
cin >> input_str;
insert_string(input_str);
}
else
{
cin >> input_str;
cout << query_string(input_str) << endl;
}
}
return 0;
}
Union-Find（経路圧縮最適化）
1. 2つの集合をマージする
2. 2つの要素が同じ集合内にあるかどうかを尋ねる
原理：
各集合を1つの木で表し、木の根の番号が集合全体の番号です。各ノードは親ノードを保存し、parent[x]はxの親ノードを示します。
①木の根を判断する方法
if(parent[x] == x)
②xの集合番号を求める方法
int find(int x) // xの祖先ノードを検索
{
if(parent[x] == x) return x; // 再帰出口：xの親がx自身、つまりxが根ノード
return parent[x] = find(parent[x]);
}
ヒープ（最小ヒープ）
主にヒープを手動で書く方法（1次元配列でヒープを保存）
現在のノードがxの場合、左の子のインデックスは2x、右の子のインデックスは2x+1（完全二分木を満たす）
主な操作：
①集合に数値を挿入
heap[++size] = value; // まず値を配列の最後に追加
adjust_up(size); // 次にadjust_up関数で要素を上に移動、最後の位置に格納されているので適切な位置を探す
②集合内の最小値を求める
heap[1]; // 最小ヒープの最小値はヒープトップ
③最小値を削除
heap[1] = heap[size]; // ヒップトップを最後の要素で上書き
size--; // 配列の長さを1減らす
adjust_down(1); // 上書きしたヒップトップ要素をadjust_down関数で適切な位置を探して下に移動
④任意の要素を削除
heap[position] = heap[size]; // 最後の要素でposition番目の要素を上書き
size--; // 配列の長さを1減らす
adjust_down(position), adjust_up(position); // adjust_down関数でposition番目の要素の位置を下に探し、適切な位置が見つかればadjust_up関数は実行されない
⑤任意の要素を変更
heap[position] = value;
adjust_down(position), adjust_up(position);
最小ヒープ：各ノードはその子ノードより小さい
基本操作
void adjust_down(int node_index)
{
int smallest = node_index;
if(node_index*2 <= size && heap[node_index*2] < heap[smallest]) smallest = node_index*2; // 左の子が存在するか、それより大きいか判定、大きければインデックス変更
if(node_index*2+1 <= size && heap[node_index*2+1] < heap[smallest]) smallest = node_index*2+1;
if(node_index != smallest) // インデックスが変わったことを示す
swap_elements(heap[node_index], heap[smallest]); // 2つの要素を交換
adjust_down(smallest); // smallest番目の要素をさらに下に移動
}
void adjust_up(int node_index)
{
while(node_index/2 && heap[node_index/2] > heap[node_index]) // 親ノードが存在するか、それより大きいか判定
{
swap_elements(heap[node_index/2], heap[node_index]); // 大きければ交換
node_index /= 2; // インデックスを上に移動
}
// position_in_heap[node_index]: node_index番目に挿入された数値のインデックス
// heap_position[node_index]: ヒープ中のある点が何番目に挿入されたか
void swap_elements(int a, int b)
{
swap(position_in_heap[heap_position[a]], position_in_heap[heap_position[b]]); // インデックス交換
swap(heap_position[a], heap_position[b]); // 挿入順序の交換
swap(heap[a], heap[b]); // 値の交換
}
ハッシュテーブル
10の-9乗から10の9乗までの数値を0から10の5乗にマッピング（剰余演算を使用、素数で剰余を取る）
チェイン法（連結リスト方式）
void insert_hash(int value)
{
int key = (value % MAX_SIZE + MAX_SIZE) % MAX_SIZE; // 負数の剰余を正数に変換
element_values[node_counter] = value;
next_pointers[node_counter] = hash_table[key]; // node_counter番目の要素のポインタをkey番目の要素のポインタが指す位置に
hash_table[key] = node_counter++; // key番目の要素のポインタをnode_counterに
// hash_table[key]: key番目の連結リストのインデックス
}
bool find_hash(int value)
{
int key = (value % MAX_SIZE + MAX_SIZE) % MAX_SIZE; // 負数の剰余を正数に変換
for(int i = hash_table[key]; i != -1; i = next_pointers[i]) // 値valueの剰余値がhash_table[]配列内の位置を見つける
{
if(element_values[i] == value) // 対応する連結リストにvalueが存在する場合
return true;
}
return false;
}
オープンアドレス法
要素が存在する場合はそのインデックスを返し、存在しない場合は挿入すべき位置のインデックスを返す
int null_value = 0x3f3f3f3f;
memset(hash_table, 0x3f, sizeof(hash_table)); // memsetでバイト単位初期化
int find_hash(int value)
{
int key = (value % MAX_SIZE + MAX_SIZE) % MAX_SIZE;
while(hash_table[key] != null_value && hash_table[key] != value) // 検索時：要素があり、かつvalueでない場合、後ろに検索
// 挿入時：その位置に要素が格納されているか判定、なければ要素を挿入
{
key++;
if(key == MAX_SIZE)
key = 0; // 最後まで到達したら先頭から再検索
}
// 見つからない場合、hash_table[key] == null_valueで停止（配列が十分大きいため）
return key;
}
文字列ハッシュ
核心：文字列をP進数と見なし、10進数に変換し、結果をQで割る余りを取る。Pは131または13331が良い（衝突の確率が低い）、modは2^64を使用し、unsigned long longで保存すれば、オーバーフローした結果がmodの結果となる
typedef unsigned long long ULL;
ULL prefix_hash[MAX_SIZE], power_values[MAX_SIZE]; // prefix_hash[k]は文字列の先頭k文字のハッシュ値、power_values[k]はP^k mod 2^64
power_values[0] = 1;
for(int i = 1; i <= n; i++)
{
prefix_hash[i] = prefix_hash[i-1] * BASE + str[i];
power_values[i] = power_values[i-1] * BASE;
}
// 部分文字列str[l~r]のハッシュ値を計算
ULL get_substring_hash(int l, int r)
{
return prefix_hash[r] - prefix_hash[l-1] * power_values[r-l+1];
}
C++ STL 概要
vector, 可変長配列、倍増の思想
size() 要素数を返す
empty() 空かどうかを返す
clear() クリア
front()/back()
push_back()/pop_back()
begin()/end()
比較演算をサポート、辞書順
vector<int> a(10,3) 長さ10の配列を3で初期化
pair<int, int>
first, 最初の要素
second, 2番目の要素
比較演算をサポート、firstを第1キーワード、secondを第2キーワード（辞書順）
p = make_pair{10,"example"}またはp = {10,"example"}
ある要素の特定の属性をソートする必要がある場合、firstにソート用、secondに非ソート用を配置
string, 文字列
size()/length() 文字列の長さを返す
empty()
clear()
substr(開始インデックス, (部分文字列の長さ)) 部分文字列を返す
c_str() 文字列がある文字配列の開始アドレスを返す
queue, キュー
size()
empty()
push() 末尾に要素を挿入
front() 先頭要素を返す
back() 末尾要素を返す
pop() 先頭要素を削除
priority_queue, 優先度付きキュー、デフォルトは最大ヒープ
size()
empty()
push() 要素を挿入
top() ヒップトップ要素を返す
pop() ヒップトップ要素を削除
最小ヒープとして定義する方法：priority_queue<int, vector<int>, greater<int>> q;
stack, スタック
size()
empty()
push() スタックトップに要素を挿入
top() スタックトップ要素を返す
pop() スタックトップ要素を削除
deque, 双方向キュー
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
set, map, multiset, multimap, 平衡二分木（赤黒木）に基づき、動的に順序付きシーケンスを維持
size()
empty()
clear()
begin()/end()
++, -- 前駆と後続を返す、時間計算量 O(logn)
set/multiset setは重複要素を保存できず、multisetは可能
insert() 数値を挿入
find() 数値を検索
count() 特定の数値の個数を返す
erase()
(1) 入力が数値xの場合、すべてのxを削除 O(k + logn)
(2) 入力がイテレータの場合、そのイテレータを削除
lower_bound()/upper_bound()
lower_bound(x) x以上の最小の数値のイテレータを返す
upper_bound(x) xより大きい最小の数値のイテレータを返す
イテレータはポインタに似ており、要素へのポインタを返す
map/multimap
insert() 挿入する数値はpair
erase() 入力パラメータはpairまたはイテレータ
find()
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, ハッシュテーブル
追加・削除・変更・検索の時間計算量は O(1)
lower_bound()/upper_bound() をサポートせず、イテレータの++をサポートしない
bitset, ビット圧縮
bitset<10000> s;
count() 1の数を返す
any() 少なくとも1つが1かどうかを判断
none() すべてが0かどうかを判断
set() すべてのビットを1に
set(k, v) k番目のビットをvに
reset() すべてのビットを0に
flip() ~と等価
flip(k) k番目のビットを反転