問題 ヒープ 完全二分木 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 完全二分木とは, すべての葉が同じ深さであり内部節点の次数が2であるような二分木である. 節点番号がiであるとき, 親はi/2, 左の子ノードは2i, 右の子ノードは2i+1で求めるこ…

問題 二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木の削除を実装する問題 削除するノードを以下の3つの条件で場合分けし処理を行う. 子ノードを持たない 子ノードを1つだけ持つ 子ノードを2つ持つ 1, 2の場合は対象ノー…

問題 二分探索木 検索 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木の探索を行う問題 二分探索木の構築(insert)自体は前回のものを流用 muttan1203.hatenablog.com 関数findは, カレントノードがNULLになるまでループし, 値が見つかった…

問題 二分探索木 挿入| アルゴリズムとデータ構造 | Aizu Online Judge 方針 二分探索木を生成する問題 ある節点xの左部分木に属する節点をy1, 右部分木に属する節点をy2としたとき, y1のキー xのキー かつ xのキー y2のキーを満たすものである. コード #inc…

問題 最小全域木| アルゴリズムとデータ構造 | Aizu Online Judge 方針 最小全域木(Minimum Spanning Tree)を作ろう. 全域木は閉路を持たない木(でいいのだろうか) 最小全域木は, 辺のコストの和が最も小さくなる全域木のこと. 頂点数がであることから, プリ…

問題 グラフの連結成分 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 グラフの連結成分(Connected Components)を求める問題. 連結成分とは, 必ずしも連結でないグラフGに対して, その極大連結部分グラフのことをグラフGの連結成分という. G'がGの極…

問題 Quick Sort | Aizu Online Judge 方針 クイックソートはの高速なソートであるが, すべての要素がすでに整列済みの場合など最悪の計算量はである. それを解するため, しきい値(pivot)をランダムに取る, データ列の中央値を取るなどの工夫が必要. 分割統…

問題 パーティション | アルゴリズムとデータ構造 | Aizu Online Judge 方針 iをA[r]以下の数が格納されている終端を示す変数とする. jをpからr-1まで進めていき, A[j]がxより大きければそのまま, x以下の場合はiを1つ進めてスワップする. 最後にi+1とr番目…

問題 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 バックトラック法を用いて探索を行おう. コード #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> #…</deque></queue></list></map></vector></string></iostream></climits></cctype></ctime></cmath></cstring></cstdlib></cstdio>

問題 木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 inorderを先頭から見ていったとき, その値をcとする. そのcの位置をpreorderの中から探し, その値をmとする. prem[m]より左側の値はcを根とする木の左部分木, 右側は右部分木となる. そ…

問題 Tree Walk | Aizu Online Judge 方針 二分木を実装する. 行きかけ順(Preorder Tree Walk), 通りかけ順(Inorder Tree Walk), 帰りがけ順(Postorder Tree Walk)を実装する. 行きかけ順は, 根（接点）→左部分木→右部分木の順で出力を行う. 通りかけ順は左…

問題 Rooted Trees | Aizu Online Judge 方針 根付き木を実装する. Nodeという構造体を定義しておき, ノード番号(id), 親ノード(parent), 子ノード(child), 深さ(depth)というメンバを定義する. 入力にそって親子関係を構築していく. すべて終わったあと, ro…

問題 Pollock's conjecture | Aizu Online Judge 方針 動的計画法を使う. nを表現するのに必要な正四面体の数の最小値 としたとき, はとして求めることができる. 1から順番にもとめておき, 入力したnを添え字にしてテーブルを出力する. コード #include<iostream> #inc</iostream>…

問題 Miscalculation | Aizu Online Judge 方針 ルール1は通常の優先順位（乗算→加算）で演算する. ルール2は左から順番に計算する. ルール1とルール2の結果が等しく, 入力した数字とも等しければU ルール1が入力した数字と等しければM, ルール2と等しければ…

問題 Carpenters' Language | Aizu Online Judge 方針 文法を見てみると, 実は挿入位置は関係なくてかっこの個数だけで判定できることが分かる. 左括弧, 右括弧それぞれの個数を保持しておき, 同じの時はYes, そうでないときはNoを出力する. コード #include<iostream></iostream>…

問題 Make a Sequence | Aizu Online Judge 方針 置くたびにm個以上つながっているかを調べる. 縦横斜めの３方向を探索するので, dx, dy, dzという配列を用意しておき3重ループする. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) f</bits/stdc++.h>…

問題 Strange String Manipulation | Aizu Online Judge 方針 S,A,Cを総当りして, エントロピーが一番低くなる場合を探す. 誤差を考えて, epsを足さないと死んでしまう. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a</bits/stdc++.h>…

問題 Quality of Check Digits | Aizu Online Judge 方針 4桁の数字(abcd)をループで作る. eを求め, それをチェック関数に投げる. abcdの各桁を0-9の数字で置き換え, 0になったら-1を返す. また, 連続する2桁を交換し（ただし, それぞれが違う文字のときのみ…

問題 Rearranging a Sequence | Aizu Online Judge 方針 与えられたM個の値を逆順に出力する. 出力したかどうかを管理しておき, １回も出力していない場合に限って出力を行う. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int</bits/stdc++.h>…

問題 Thread Tree | Aizu Online Judge 方針 木を作って順に辿って出力する. 英語つらいなって思ったけどそんなに難しくなかった.（これは方針ではない） コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n </bits/stdc++.h>…

問題はこちら. abc060.contest.atcoder.jp 問題A：Shiritori 文字列A, B, Cが3つ与えられた時, それらがしりとりになっているか判定せよ. #include <iostream> using namespace std; signed main(){ string a, b, c; cin >> a >> b >> c; if(a[a.size()-1] == b[0] && </iostream>…

問題 Broken Audio Signal | Aizu Online Judge 方針 区間を狭めていって, その区間によって結果を出力する. xが偶数番目のときに上界, 奇数番目のときに下界を決めることができる. xが連続した時はnone, 上界がないなど様々な場合分けがあってとてもつらい.…

問題 M and A | Aizu Online Judge 方針 SとTの部分文字列を交互に繋げてSを作ることができるか調べる. Sの部分文字列は自明にSに含まれているので, Tの部分文字列を考える. Tの先頭から順に探索し, 部分文字列であるかを試す. （Sの偶数番目と奇数番目をと…

問題 Calling Extraterrestrial Intelligence Again | Aizu Online Judge 方針 とを満たすp, qを求める. (p, qは素数) エラトステネスの篩を使って素数を生成する. それらを使ってpとqの組を試す. qを求めるループの条件式は, という不等式から, とした. コ…

問題 Lagrange's Four-Square Theorem | Aizu Online Judge 方針 全部探索する. コード #include <iostream> using namespace std; signed main(){ int n; while(cin >> n, n){ int cnt = 0; for(int i = 1 ; i * i <= n ; i++){ if(i*i == n) cnt++; for(int j = i ; </iostream>…

問題 Calender Colors | Aizu Online Judge 方針 N個のLABカラーが与えられる. そこからM個取り出し, 要素それぞれの差の二乗の和を求める. その和の最大値が答え. であることから全探索しても良さそう. M個取り出すときにbitを使うと便利っぽい. コード #in…

問題 Counting Sort | Aizu Online Judge 方針 計数ソート（バケットソート）をしよう. アルゴリズムは問題をそのまま実装. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; </bits/stdc++.h>…

問題 Grey Area | Aizu Online Judge 方針 ヒストグラムを印刷するために必要なインク量を求めようという問題. vを入力する際に, 区画の最大値(imax), 頻度の最大値(hmax)を求める. hist[i] := の頻度としたとき, を計算する. 最後に0.01を足す(線とかを引く…

問題A：Three-letter acronym 3つ文字列が与えられるので, それぞれの1文字目を大文字にしてつなげ表示する. 文字コードでやった. #include <iostream> #include <cstring> using namespace std; int main(){ string s1, s2, s3; cin >> s1 >> s2 >> s3; cout << (char)('A'+s1[</cstring></iostream>…

問題 And Then There Was One | Aizu Online Judge 方針 Josephus problemという有名な問題らしい. (ただし, ) という漸化式を解くことでで求まる. コード #include <iostream> using namespace std; int f(int n, int k){ if(n == 1) return 0; return (f(n-1, k)+k)%</iostream>…