【AOJ ALDS1_9】A: Heaps - Complete Binary Tree
問題
ヒープ 完全二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 完全二分木とは, すべての葉が同じ深さであり内部節点の次数が2であるような二分木である.
- 節点番号がiであるとき, 親はi/2, 左の子ノードは2i, 右の子ノードは2i+1で求めることができる.
コード
#include<iostream> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; signed main(){ int h; int A[251]; cin >> h; for(int i = 1 ; i <= h ; i++){ cin >> A[i]; } for(int i = 1 ; i <= h ; i++){ cout << "node " << i << ": key = " << A[i] << ", "; if(i/2 >= 1) cout << "parent key = " << A[i/2] << ", "; if(2 * i <= h) cout << "left key = " << A[2 * i] << ", "; if(2 * i + 1 <= h) cout << "right key = " << A[2 * i + 1] << ", "; cout << "\n"; } }
【AOJ ALDS1_8】C: Binary search trees - Binary Search Tree III
問題
二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 二分探索木の削除を実装する問題
- 削除するノードを以下の3つの条件で場合分けし処理を行う.
- 子ノードを持たない
- 子ノードを1つだけ持つ
- 子ノードを2つ持つ
- 1, 2の場合は対象ノードを取り除くだけで良い.(取り除いてその子ノードを親ノードに繋げば良い)
- 3の場合は, 右部分木の最小ノードを削除したいノードに置き換える.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; struct Node{ int data; Node *parent, *left, *right; }; Node *root; Node* findNode(int x){ Node *r = root; while(r != NULL && r->data != x){ if(x < r->data){ r = r->left; }else{ r = r->right; } } return r; } Node* getMinNode(Node *u){ while(u->left != NULL) u = u->left; return u; } Node* getSuccessor(Node *u){ if(u->right != NULL) return getMinNode(u->right); Node *p = u->parent; while(p != NULL && p->right == u){ u = p; p = p->parent; } return p; } void deleteNode(Node *u){ Node *target; Node *child; // 削除対象ノードを決める // 子ノードが無い or 1個だけの場合, 削除対象ノードはuそのもの // 子が2つある場合, uの次接点となる. if(u->left == NULL || u->right == NULL){ // 子ノードがない or 1個 target = u; }else{ target = getSuccessor(u); } // 削除対象ノードの子ノードを求める if(target->left != NULL){ child = target->left; }else{ child = target->right; } // 子ノードがある場合, 子ノードの親ノードを削除対象ノードの親ノードにする if(child != NULL){ child->parent = target->parent; } // 左 or 右のノードに子ノードを格納 if(target->parent == NULL){ root = child; }else{ if(target == target->parent->left){ target->parent->left = child; }else{ target->parent->right = child; } } // 削除対象が異なる場合はdataを入れ替え if(target != u) u->data = target->data; free(target); } void insertNode(int x){ Node *root_tmp = root; Node *elem; elem = (Node *)malloc(sizeof(Node)); elem->data = x; elem->left = NULL; elem->right = NULL; Node *prev = NULL; while(root_tmp != NULL){ prev = root_tmp; if(elem->data < root_tmp->data){ root_tmp = root_tmp->left; }else{ root_tmp = root_tmp->right; } } elem->parent = prev; if(elem->parent == NULL){ root = elem; }else{ if(elem->parent->data < elem->data){ elem->parent->right = elem; }else{ elem->parent->left = elem; } } } // 先行巡回 void preorder(Node *u){ if(u == NULL) return; cout << " " << u->data; preorder(u->left); preorder(u->right); } // 中間巡回 void inorder(Node *u){ if(u == NULL) return; inorder(u->left); cout << " " << u->data; inorder(u->right); } signed main(){ int n; string command; int elem; cin >> n; rep(i, n){ cin >> command; if(command == "insert"){ cin >> elem; insertNode(elem); }else if(command == "find"){ cin >> elem; if(findNode(elem)!=NULL) cout << "yes" << endl; else cout << "no" << endl; }else if(command == "delete"){ cin >> elem; deleteNode(findNode(elem)); }else{ inorder(root); cout << "\n"; preorder(root); cout << "\n"; } } }
参考
PDFです.
http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-二分探索木.pdf
【AOJ ALDS1_8】B: Binary search trees - Binary Search Tree II
問題
二分探索木 検索 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 二分探索木の探索を行う問題
- 二分探索木の構築(insert)自体は前回のものを流用
- 関数findは, カレントノードがNULLになるまでループし, 値が見つかったらtrueを返し見つからない場合はfalseを返せば良い.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; struct Node{ int data; Node *parent, *left, *right; }; Node *root; bool find(int x){ Node *r = root; while(r != NULL){ if(r->data == x){ return true; }else if(x < r->data){ r = r->left; }else{ r = r->right; } } return false; } void insert(int x){ Node *root_tmp = root; Node *elem; elem = (Node *)malloc(sizeof(Node)); elem->data = x; elem->left = NULL; elem->right = NULL; Node *prev = NULL; while(root_tmp != NULL){ prev = root_tmp; if(elem->data < root_tmp->data){ root_tmp = root_tmp->left; }else{ root_tmp = root_tmp->right; } } elem->parent = prev; if(elem->parent == NULL){ root = elem; }else{ if(elem->parent->data < elem->data){ elem->parent->right = elem; }else{ elem->parent->left = elem; } } } void preorder(Node *u){ if(u == NULL) return; cout << " " << u->data; preorder(u->left); preorder(u->right); } void inorder(Node *u){ if(u == NULL) return; inorder(u->left); cout << " " << u->data; inorder(u->right); } signed main(){ int n; string command; int elem; cin >> n; rep(i, n){ cin >> command; if(command == "insert"){ cin >> elem; insert(elem); }else if(command == "find"){ cin >> elem; if(find(elem)) cout << "yes" << endl; else cout << "no" << endl; }else{ inorder(root); cout << "\n"; preorder(root); cout << "\n"; } } }
【AOJ ALDS1_8】A: Binary search trees - Binary Search Tree I
問題
二分探索木 挿入| アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 二分探索木を生成する問題
- ある節点xの左部分木に属する節点をy1, 右部分木に属する節点をy2としたとき, y1のキー xのキー かつ xのキー y2のキーを満たすものである.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define pb push_back #define INF 1e9 using namespace std; struct Node{ int data; Node *parent, *left, *right; }; Node *root; void insert(int x){ Node *root_tmp = root; Node *elem; elem = (Node *)malloc(sizeof(Node)); elem->data = x; elem->left = NULL; elem->right = NULL; Node *prev = NULL; while(root_tmp != NULL){ prev = root_tmp; if(elem->data < root_tmp->data){ root_tmp = root_tmp->left; }else{ root_tmp = root_tmp->right; } } elem->parent = prev; if(elem->parent == NULL){ root = elem; }else{ if(elem->parent->data < elem->data){ elem->parent->right = elem; }else{ elem->parent->left = elem; } } } void preorder(Node *u){ if(u == NULL) return; cout << " " << u->data; preorder(u->left); preorder(u->right); } void inorder(Node *u){ if(u == NULL) return; inorder(u->left); cout << " " << u->data; inorder(u->right); } signed main(){ int n; string command; int elem; cin >> n; rep(i, n){ cin >> command; if(command == "insert"){ cin >> elem; insert(elem); }else{ inorder(root); cout << "\n"; preorder(root); cout << "\n"; } } }
【AOJ ALDS1_12】A: Graph II - Minimum Spanning Tree
問題
最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge
方針
- 最小全域木(Minimum Spanning Tree)を作ろう.
- 全域木は閉路を持たない木(でいいのだろうか)
- 最小全域木は, 辺のコストの和が最も小さくなる全域木のこと.
- 頂点数がであることから, プリムのアルゴリズムを利用してMSTを求める.
- プリム法は, 以下のようなアルゴリズムである.
- 任意の頂点rを選び, Tに追加する.
- MSTに属する頂点の集合をT, グラフGの頂点の集合をVとする.
- Tに属する頂点とV-Tに属する頂点を繋ぐ辺の中で, コストが一番小さいノードuを選びそれをMSTの辺とする.
- uをTに追加する.
- これをV=Tとなるまで(2)から(4)を繰り返す.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define ALL(v) v.begin(), v.end() #define pb push_back #define INF 1e9 #define N_MAX 100 using namespace std; // 隣接行列 int G[N_MAX][N_MAX]; // d[i] := 頂点iからMSTの集合Tまでの最短距離 int d[N_MAX]; // 確定したノード bool visited[N_MAX]; // 親ノード int p[N_MAX]; void init(){ rep(i, N_MAX){ d[i] = INF; visited[i] = false; p[i] = -1; } } int prim(int n){ init(); // 始点は0 d[0] = 0; while(true){ int u = -1; int _min = INF; // 最短距離で行けるノードuを確定 rep(i, n){ if(d[i] < _min && !visited[i]){ u = i; _min = d[i]; } } if(u == -1) break; visited[u] = true; // ノードuから行けるノードの最短距離を更新 rep(v, n){ if(G[u][v] != -1 && !visited[v] && G[u][v] < d[v]){ d[v] = G[u][v]; p[v] = u; } } } int sum = 0; rep(i, n){ if(visited[i]){ sum += G[i][p[i]]; } } return sum; } signed main(){ int n; cin >> n; rep(i, n){ rep(j, n){ cin >> G[i][j]; } } cout << prim(n) << endl; }
ところで確定したノード適当にvisitedにしちゃったんですけどこれvisitじゃ色々おかしい気がする.
【AOJ ALDS1_11】D: Graph I - Connected Components
問題
グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- グラフの連結成分(Connected Components)を求める問題.
- 連結成分とは, 必ずしも連結でないグラフGに対して, その極大連結部分グラフのことをグラフGの連結成分という.
- G'がGの極大連結部分グラフであるとは, 1) G'がGの部分連結グラフであること 2) G'を部分グラフとして持つようなGの連結部分グラフが存在しないこと が満たされているものを言う.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #include<stack> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define pb push_back #define MAX_N 100001 using namespace std; vector<int> G[MAX_N]; int label[MAX_N]; void dfs(int start, int id){ stack<int> s; s.push(start); label[start] = id; while(!s.empty()){ int u = s.top(); s.pop(); rep(i, G[u].size()){ int v = G[u][i]; if(label[v] == -1){ label[v] = id; s.push(v); } } } } void solve(int n){ int id = 1; rep(u, n){ if(label[u] == -1){ dfs(u, id); id++; } } } void init(){ rep(i, MAX_N) label[i] = -1; } signed main(){ int n, m, s, t; cin >> n >> m; rep(i, m){ cin >> s >> t; G[s].pb(t); G[t].pb(s); } init(); solve(n); int q; cin >> q; rep(i, q){ cin >> s >> t; if(label[s] == label[t]){ cout << "yes" << endl; }else{ cout << "no" << endl; } } }
風邪を引きながら理解するのは無理があった.
参考
http://coconut.sys.eng.shizuoka.ac.jp/gn/04/handout6.pdf
http://dopal.cs.uec.ac.jp/okamotoy/lect/2012/graphtheory/lect10.pdf
【AOJ ALDS1_6】C: Sort II - Quick Sort
問題
Quick Sort | Aizu Online Judge
方針
- クイックソートはの高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量はである.
- それを解するため, しきい値(pivot)をランダムに取る, データ列の中央値を取るなどの工夫が必要.
- 分割統治法に基づいたアルゴリズムであるが, マージソートと違いインプレースソートである.
コード
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<ctime> #include<cctype> #include<climits> #include<iostream> #include<string> #include<vector> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<memory> #include<functional> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define INF 1e9 #define MAX_N 100001 using namespace std; struct Card{ char c; int num; }; int n; Card A[100001], B[100001]; int comp; Card l[MAX_N/2+2]; Card r[MAX_N/2+2]; void merge(int left, int right, int mid){ rep(i, mid-left){ l[i] = B[left + i]; } rep(i, right-mid){ r[i] = B[mid + i]; } l[mid-left].num = r[right-mid].num = INF; int left_idx, right_idx; left_idx = right_idx = 0; REP(i,left,right){ comp++; if(l[left_idx].num <= r[right_idx].num){ B[i] = l[left_idx]; left_idx++; }else{ B[i] = r[right_idx]; right_idx++; } } } void mergeSort(int left, int right){ if(right - left > 1){ int mid = (right + left)/2; mergeSort(left, mid); // 左 mergeSort(mid, right); // 右 merge(left, right, mid); // マージ } } int partition(int p, int r){ int i; i = p-1; REP(j, p, r){ if(A[j].num <= A[r].num){ i++; swap(A[i], A[j]); } } swap(A[i+1], A[r]); return i+1; } void quickSort(int p, int r){ if(r - p > 0){ int ret = partition(p, r); quickSort(p, ret-1); quickSort(ret+1, r); } } bool compare(Card l, Card r){ return (l.num <= r.num); } signed main(){ cin >> n; rep(i, n){ cin >> A[i].c >> A[i].num; B[i].c = A[i].c; B[i].num = A[i].num; } quickSort(0, n-1); mergeSort(0, n); bool flag = false; rep(i, n){ if(A[i].c != B[i].c) flag = true; } if(flag) cout << "Not stable" << endl; else cout << "Stable" << endl; rep(i, n){ cout << A[i].c << " " << A[i].num << endl; } }