アルゴリズム
概要 †
- 構造化されたプログラミング言語の基本要素を,僕なりに形式・意味の両面から分析し、まとめたもの。
- 人は騙し騙し仕事というのをしているけれども、プログラミングはそういう騙しが効かないから無理
目次 †
コメント †
- 極めて重要
- 図で頑張って描くのは当然やるが、それとは別にプログラムに何を格納しているのかを書いたほうが良い
- 図を見返してやるのは結構めんどいので
- assertとかを書く時に間違えない
- デバッグ楽
ループ †
- for (int i = 0; i < NUM; i++)について。
- 色んな見方が出来る。
- 形式的にはプログラムポインタが順々に回るという見方だけ、これだけでプログラミングするのは相当辛かった。
- ということで、意味的に考えられないかなぁと模索する。
- 意味論的考察なので、極めて当然のことを書いているし、整理としては理系的に体系化されたものというより、僕の頭の中の整理ってだけ。
反復（大局的） †
視点固定（局所的） †
- この見方が出来ると、上の解釈のように、頭の中で動く変数の数を劇的に抑えられる。
全探索（大局的） †
- この見方ができると、複数のforループを同じ「全探索」一つに見ることができて、強力。
- 上にも書いたが、局所的に見ればループ変数i,j,h,kが決まり、視点が固定された世界でif文を行っているようにも解釈できる。
- つまり、「今i, j, h, kの番号のカードが既に置いてある。これを足してkになれば万々歳だねbreak」という見方も出来る。
- しかし、この場合は目的からして全探索として見た方が綺麗だと思う。
最大最小 †
- 全探索の亜種
- 最大最小とは、考えられる状態全ての可能性のうち、最も評価値が高いor低いもの、という意味なので全探索として見れる。
- 上の問題の条件で、4枚のカードの合計が最も10に近くなるi, j, h, kの組の一つを求めよ、という場合、
int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
for (int h = 0; h < 5; h++) {
for (int k = 0; k < 5; k++) {
int ijhk_val = ABS(card[i] + card[j] + card[h] + card[k] - 10);
if (min_ijhk_val > ijhk_val) {
min_ijhk_val = ijhk_val;
min_i = i; min_j = j; min_h = h; min_k = k;
}
}
}
}
}
return flag;
- と、全探索空間を張るi,j,h,kに対応するijhk_val=f(i, j, h, k)の最小化を行えば良い。
- なお、最小最大問題は普通配列などに格納されているものを使うので、以下のように書くと可視性が良くなる。
int min_i, min_j, min_h, min_k;
int min_ijhk_val = INF;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
for (int h = 0; h < 5; h++)
for (int k = 0; k < 5; k++)
if (min_ijhk_val > ABS(card[i] + card[j] + card[h] + card[k] - 10))
min_ijhk_val = ABS(card[min_i = i] + card[min_j = j] + card[min_h = h] + card[min_k = k] - 10);
return flag;
量化記号 †
- 「全てのi, jについてP(i, j)を満たす」(\( \forall \)), 「P(i, j)を満たすi, jが存在する」(\( \exists \))の条件式の実装について。
- 直感的に実装可能で、かつ可読性の高い実装方法について考える。
全称記号 †
- n変数で\( \forall a_i P(a_1, a_2, .., a_n) \)なる条件式を実装する方法について書く。
- \( \forall \phi = T \)なので、初期化はfaf = 1とする。
- 全探索をかけて、一個でもNGなら全称はNGなので、fafを0にして全部breakする。
- ここで、初めのループではif (!P(a)) の中でbreakすることも出来るけど、他のところとの整合性的な観点から、if文は僕は分けます(下例の16行目と18行目)。
- 例, \( \forall \) i, j in [1, NUM] (x[i] + y[j]) % 2 == 0
- https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall.cpp
#include <iostream>
#define NUM 6
int main(int argc, char** argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
//--------------------------------------------------------------------
// for all i, j in [1, NUM], (x[i] + y[j]) % 2 == 0 ? faf = 1 : faf = 0;
//--------------------------------------------------------------------
int faf = 1; // for all flag
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
// cont-condition
if (!((x[i] + y[i]) % 2 == 0))
faf = 0;
if (!faf)
break;
}
if (!faf)
break;
}
std::cout << faf << std::endl;
return 0;
}
- めんどい場合
- faf &= f(i)だと、f(i)がboolじゃないとバグるので、faf = faf && f(i)とする
int a[1000] = {};
bool faf = 1;
for (int i = 0; i < 1000; i++) {
faf = faf && (a[i] == 0);
}
cout << faf << endl;
存在記号 †
- n変数で\( \exists a_i P(a_1, a_2, .., a_n) \)なる条件式を実装する方法について書く。
- \( \exists \phi = F \)なので、初期化はtef = 0とする。
- 全探索をかけて、一個でもOKならOKなので、tefを1にして全部breakする。
- ここで、初めのループではif (P(a)) の中でbreakすることも出来るけど、他のところとの整合性的な観点から、if文は僕は分けます(下例の16行目と18行目)。
- 例, \( \exists \) i, j in [1, NUM] (x[i] + y[j]) % 3 == 0
- https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists.cpp
#include <iostream>
#define NUM 6
int main(int argc, char** argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
//----------------------------------------------------------------------
// there exists i, j in [1, NUM], (x[i] + y[j]) % 3 == 0 ? tef = 0 : tef = 1;
//----------------------------------------------------------------------
int tef = 0; // there exists flag
for (int i = 0; i < NUM; i++) {
for (int j = 0; j < NUM; j++) {
// condition
if ((x[i] + y[i]) % 3 == 0)
tef = 1;
if (tef)
break;
}
if (tef)
break;
}
std::cout << tef << std::endl;
return 0;
}
全称記号(1変数の場合) †
- 1変数の場合、より早く実装出来る方法について書く。
- 全探索をかけて、一個でもNGならbreakする。
- すると、ループが最後まで回ったかどうかをチェックすることで、fafを判定することができる。
- 例, \( \forall \) i in [1, NUM] (x[i] + y[i]) % 2 == 0
- https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/forall_one.cpp
#include <iostream>
#define NUM 6
int main(int argc, char** argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
//----------------------------------------------------------------------
// for all i in [1, NUM], (x[i] + y[i]) % 2 == 0 ? faf = 1 : faf = 0;
//----------------------------------------------------------------------
int i;
for (i = 0; i < NUM; i++) {
// cont-condition
if (!((x[i] + y[i]) % 2 == 0))
break;
}
int faf = (i == NUM);
std::cout << faf << std::endl;
return 0;
}
存在記号 †
(1変数の場合) [#a33f4556]
- 1変数の場合、より早く実装出来る方法について書く。
- 全探索をかけて、一個でもOKならbreakする。
- すると、ループが最後まで回ったかどうかをチェックすることで、tefを判定することができる。
- 例, \( \exists \) i in [1, NUM] (x[i] + y[i]) % 7 == 0
- https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/thereexists_one.cpp
#include <iostream>
#define NUM 6
int main(int argc, char** argv)
{
int x[NUM] = {1, 2, 3, 4, 5, 6};
int y[NUM] = {1, 2, 3, 4, 5, 6};
//--------------------------------------------------------------------
// there exists i in [1, NUM], (x[i] + y[i]) % 7 == 0 ? tef = 0 : tef = 1;
//--------------------------------------------------------------------
int i;
for (i = 0; i < NUM; i++) {
// condition
if ((x[i] + y[i]) % 7 == 0)
break;
}
int tef = (i != NUM);
std::cout << tef << std::endl;
return 0;
}
前進的隣接二項関係から生成されるまとまり †
#include <stdio.h>
#define NUM 9
// 前進的な隣接二項関係を規定するものとする
// 先を見るイメージで実装
int main(void)
{
int a[NUM] = {1, 2, 2, 2, 2, 2, 3, 4, 4};
int count = 0;
for (int l = 0; l < NUM; l++) {
int tmpl = l;
// 先に進めることが出来て、先に進めるべき時なら
while (l < NUM - 1 && a[l] + 1 == a[l+1])
l++;
for (int i = tmpl; i <= l; i++)
printf("%d ", a[i]);
printf("\n");
count++;
}
printf("count: %d\n", count);
return 0;
}
1 2
2
2
2
2 3 4
4
count: 6
問題の見方 †
要求される情報の量 †
- どれくらいの量の情報を求められているのか？
- 多ければ、全探索などナイーブなアルゴリズムになりやすい。
- 少なければ、色々な同一視を駆使することが出来る。
- プロコンでは、少ない情報しか聞かない問題ほど、全探索では計算が間に合わないものを出してくることが多い。
- yes-no
- 相当情報を削ってもいいはず。
- 同一視をガンガン考え、他の見方と組み合わせる。
データの見方 †
- 操作ステップを引数とした関数
- ステップの前後で変わらない、もしくは何らかの規則性がある(e.g. 0, 1, 0, 1, ...)
- \( \Sigma a[i] \)など
- \( \Sigma a[i] \)なる数列
- a[i] >= 0, a[i] <= 0なら単調性が保証される。
- \( \Sigma a[i] - \Sigma a[j-1] \)によって、jからiまで足した数列を得る。
特性関数の作りやすさ †
- 「このinputはこの問題の答えですか？」というyes-noクエッションに答えられるか？
yes-no †
- 全てのinputに対して、「このinputはこの問題の答えですか？」という質問に対して答えられるとする。
- そうすれば、inputの全てを探索することで、yes-noを判別することが出来る。
最大最小問題 †
- 「Pの時、xの最大値を求めよ」という問題に対しても、特性関数が役に立つことがある。
- 逆問題として、x<=maxの時は必ずそれに対応するPが存在し、x>maxの時は必ずそれに対応するPが存在しない。
- つまり、「この解の候補xに対応するPを満たすinputが存在しますか？」という質問に対する答えがyesならx<=maxで、noならx>maxである。
- yes-noの時と同様に、解の候補xに対して全てを探索し、上の条件を満たすものが存在する最も大きいものを見つければ、そのxが最大である。
- さらに逆問題の特性関数として、「この解の候補x以上に対応するPを満たすinputが存在しますか？」という問題を考える。
- のように、ある値を境にそれ以前が1, その後が0になるはずである。
- このような特性関数を実装することが出来るのならば、xに対して二分探索を用いることで、xの最大値を計算することが出来る。
- このようなPを選んで二分探索を行うことを、勝手に逆像的二分探索と呼んでいる。
境界条件 †
- 特異なinputに対して、そこだけ正しいoutputを吐かない、ということがありえる。
- このようなinputに対応できる能力は、完璧で瀟洒なプログラマには不可欠。
- まずこのような特異入力が発生しうる条件としては、以下のようなものが挙げられる。
- 数学的ま場合分け（0で割るなど）
- アルゴリズムの原始的順像における前提
- 数学的な場合分けについては、数学の論理をちゃんと展開すればいいのでそんなに問題にはならない。
- アルゴリズムの原始的順像の問題については、問題に対していい加減なアプローチを試す段で、思考が限定されることにより起きる。
- 思考が束縛される前に、trivialなinput-outputの組をいくつか考えておいて、それを満たすかを作ったアルゴリズムが対応できているかをCheckする。
- ここで考えられないようなinputが特異になるようでは、アルゴリズムが残念だというスタンス。
- 逆に言えば、今考えたtrivialなinputは除外して考えることが出来るということ。
- また、アルゴリズムを見て、何でミスりそうかを考えるのもありだが、これは大変なのでおすすめできない。
- 結局何が言いたいかというと、増えた条件としてのtrivialな条件を境界条件の候補とみなすしかないのでは、ということ。
- これで問題ないとすると、本当であれば関数の一番始めに、思いついたtrivialなinputを門前払いするのが一番安全。
- しかし、全ての思いついた条件を門前払いするのは頭が悪いので、アルゴリズムが実装し終わった後にtrivialなinputで通るかtestするのがいいでしょう。
再帰関数 †
基本構造 †
再帰関数の引数は、「今」と「過去」に二分される †
- 再帰は、未来について記述する。
- 「今自分がvにいて、その座標は(x, y)であり、」「一つ前、pから、dの方向で来た」という感じになる。
- 未来については、自分の子供が全部集めてから、この関数で作り出す。
根付き木構造のDFS †
- 根付き木構造のあるノードのみに着目していると想定してください。
int DFS(node* A) {
if (is_leaf(A))
return funcWhenNodeIsLeaf(A); // 葉は末端条件なのでそのまま返す。
funcWhenNodeComesDown(A); // Aに下がる直後に行う！！
for (auto child : A->children)
DFS(child);
int ret = funcWhenNodeComesUp(A); // Aから上がる直前に行う！！
// 主に、childrenが最新状態になっているので、それを走査したりする。
return ret;
}
- 重要なのは、コードに位置によって、「Aに下がる直後に行う」「Aから上がる直前に行う」という意味が付加できているところ。
グラフのDFS †
- グラフだと、木構造のプログラムを使ってしまうと、永遠に無限ループする
- 解決策: Aに来た時点で、もう計算されていたり、異常状態だったりしないかを確認する！
- そもそも、is_leaf(A)に相当する状態とはなにか？
- unvisitedな子がいなくなったら、is_leaf(A)に相当する。
- しかし、それを事前に走査するのは面倒なので、異常値で零元や単位元を返すことで対処することが多い
- グラフの走査状態
- visitedとvisitingを用意する！（visitingはマジで忘れるので注意）
- Aがvisited: 「Aは正しい状態になっている」ので、来る必要がない
- Aがvisiting: 「まだ子の計算が全部終わっていないので、まだAは正しく計算できていない。」
- 例: ループ検出
- visitingなのに再度visitしたら、ループがある
- 例: グラフサイズ
- visitingかfinalizedだったら、問答無用で0。そうでなければ、子のサイズを足す。
int DFS(node* A) {
if (state[A] == finalized) return ret_vec[A]; // もう計算が終わっているので、計算しないでそのまま返せる。これのおかげで、グラフが根付き木に潰れる。
if (state[A] == pending) return nothing; // いま計算中なので、計算しない。 これが呼ばれるということは、ループがある。
state[A] = pending; // まだ子供が全員確定していない
funcWhenNodeComesDown(A); // Aに下がる直後に行う
for (auto child : A->children)
DFS(child);
ret = funcWhenNodeComesUp(A); // Aから上がる直前に行う
// 主に、childrenが最新状態になっているので、それを走査したりする。
state[A] = finalized;
ret_vec[A] = ret;
return ret;
}
- is_validは、「来てから考える」実装になっている
- for文の直後にif文を挟むことで、次に行って良いかを確認することでも実装できる（往々にして、面倒くさくなるので、「来てから考える」方が良い）
陽にグラフを持たないグラフアルゴリズム †
- 「遷移をその場で作るBFS」のコーディングパターンが無いのがいけないという感じはある
- BFS, ダイクストラ等では、このほうが速い。また、完全グラフでもメモリ位いっぱい持つ必要がなくなる
再帰関数の妥当性チェック †
- 再帰関数のテストデータの作り方と、そのデバッグの仕方について。
- 再帰関数のテスト関数は、(1) 一回ですぐreturnするもの (2) 一回再帰して返るもの (3) 出来るなら二回以上再帰するもの の三つでチェックする。
// n!
int frac(int n, int input)
{
if (n == 0)
return 1;
return n * frac(n - 1);
}
- この場合、frac(0), frac(1), frac(4)くらいでチェックするのが妥当である。
再帰関数のデバッグ †
#include <iostream>
using namespace std;
#define MAP_SIZE 16
int map[MAP_SIZE] = {0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, };
void rm_map_part(int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
map[index] = 0;
rm_map_part(index - 1);
rm_map_part(index + 1);
}
int main(void)
{
rm_map_part(3);
for (int i = 0; i < MAP_SIZE; i++)
cout << map[i];
cout << endl;
return 0;
}
- mapを再帰的に、1の帯を全て埋める関数を考える。
- ここの話題とは関係ないが、再帰関数は(1)終端条件(2)操作(3)再帰呼び出しの順に書くとやりやすい。
- 再帰呼び出しではあまりゴタゴタとif文を書かず、終端条件で弾いた方が思考回路的に楽。
- このような関数について、例えばどこでどのように操作が行われているのかを知りたいとする。
- しかし、このまま下のように表示すると、意味が分からないことになる。
void rm_map_part(int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
map[index] = 0;
cout << "index: " << index << endl;
rm_map_part(index - 1);
rm_map_part(index + 1);
}
mechuser@UoT-IST-Ub:~/tmp$ ./a.out
index: 11
index: 10
index: 9
index: 8
index: 7
index: 6
index: 5
index: 4
index: 3
index: 2
index: 12
index: 13
index: 14
index: 15
index: 16
index: 17
index: 18
index: 19
index: 20
index: 21
index: 22
index: 23
index: 24
- 何が分からないかというと、どこのindexをやったあとに、どこのindexが呼ばれたのかが分からない。
- これに対処するために、以下のように再帰関数に一つ引数を追加してやることで、少し見通しのよいログが得られる。
- どこで何が呼ばれているのかがはっきりする。
void rm_map_part(int n, int index)
{
if (index < 0 || index >= MAP_SIZE || !map[index])
return;
for (int i = 0; i < n; i++)
cout << " ";
cout << "index: " << index << endl;
map[index] = 0;
rm_map_part(n + 1, index - 1);
rm_map_part(n + 1, index + 1);
}
mechuser@UoT-IST-Ub:~/tmp$ ./a.out
index: 11
index: 10
index: 9
index: 8
index: 7
index: 6
index: 5
index: 4
index: 3
index: 2
index: 12
index: 13
index: 14
index: 15
index: 16
index: 17
index: 18
index: 19
index: 20
index: 21
index: 22
index: 23
index: 24
bit演算 †
- 低位Bitから0, 1, ...と名付けていく。
- 基本操作関数
- bit-nをゲットする。(n < sizeofbit)
r = (a >> n) & 1;
- bit-nに1をセットする。(n < sizeofbit)
a |= 1 << n;
- bit-nを0をセットするn < sizeofbit)
a &= ~(1 << n);
- 2^nに関する演算
- aを2^nで割った商を取得する。(n < sizeofbit, 負の場合答えが1減る。下の余りと対応している。
r = a >> n;
- aを2^nで割った余りを取得する。(n < sizeofbit, 負の余りも正で出る)
r = a & ~(-1 << n);
#include <iostream>
using namespace std;
void print_bit(int a)
{
for (int i = 8; i >= 0; i--)
cout << (int)((a >> i) & 1);
cout << endl;
}
int main(void)
{
int a, n, r;
// bit-nをゲットする。
cout << "----get bit-n----" << endl;
a = 10, n = 2;
print_bit(a);
r = (a >> n) & 1;
cout << n << "-bit: " << r << endl;
cout << "----get bit-n----" << endl;
a = 10, n = 3;
print_bit(a);
r = (a >> n) & 1;
cout << n << "-bit: " << r << endl;
// bit-nに1をセットする。|=は1の部分を埋めるフィルタ
cout << "----set bit-n 1----" << endl;
a = 0, n = 2;
a |= 1 << n;
print_bit(a);
// bit-nに0をセットする。&=は1の部分だけ通すフィルタ。
cout << "----set bit-n 0----" << endl;
a = 0x04, n = 2;
a &= ~(1 << n);
print_bit(a);
// aを2^nで割った商を取得する。(0 <= n < SIZEOFINTBIT, -1 / 4 = -1など、普通の余りより1大きくなっている。下の余りと対応)
cout << "----/ 2^n----" << endl;
a = 11, n = 2;
r = a >> n;
print_bit(a);
print_bit(r);
cout << a << "/ 2^" << n << " = " << r << endl;
cout << "----/ 2^n----" << endl;
a = -11, n = 2;
r = a >> n;
print_bit(a);
print_bit(r);
cout << a << "/ 2^" << n << " = " << r << endl;
// aを2^nで割った余りを取得する。(0 <= n < SIZEOFINTBIT, 負の余りも正で出る)
cout << "----% 2^n----" << endl;
a = 11, n = 2;
r = a & ~(-1 << n);
print_bit(a);
print_bit(r);
cout << a << "% 2^" << n << " = " << r << endl;
cout << "----% 2^n----" << endl;
a = -13, n = 2;
r = a & ~(-1 << n);
print_bit(a);
print_bit(r);
cout << a << "% 2^" << n << " = " << r << endl;
return 0;
}
----get bit-n----
000001010
2-bit: 0
----get bit-n----
000001010
3-bit: 1
----set bit-n 1----
000000100
----set bit-n 0----
000000000
----/ 2^n----
000001011
000000010
11/ 2^2 = 2
----/ 2^n----
111110101
111111101
-11/ 2^2 = -3
----% 2^n----
000001011
000000011
11% 2^2 = 3
----% 2^n----
111110011
000000011
-13% 2^2 = 3
== BFSとDFS==
おなじみ幅優先探索と深さ優先探索．これらの構造と具体的な記述方法について †
戻り値ありの再帰によるBFS †
- 漸化式のアナロジーで記述できる．
- 引数を状態（=添字，データ，制限など）と見なして，これをより簡単な状態を用いて表す，というのが基本的な考え方．
- 例えば，
a[] = {1, 2, 3, 4, 5};
f(i, a[], b[]) = [0番目からindex個までに対して∑a[b[i]]を確定した場合，0番目からNUM番目に対して∑a[f[i]]が100に最も近づく時の∑a[b[i]]]
int rec(const int* a, int* f, int index)
{
if (index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += a[i] * f[i];
return sum;
}
// index番目を取らない
int n = rec(a, f, index + 1);
// index番目を取る
f[index] = 1;
int p = rec(a, f, index + 1);
f[index] = 0;
return (abs(n - 100) > abs(p - 100)) ? p : n;
}
- 問題は，これの一般化．
- 今回，データ(const int* a)と状態(int i, int* f)について，どのように扱うかについて記述する．
- データは変更されえないので，constで書く．これは問題ない．
- 状態は，実体で渡すことも，参照で渡すことも可能である．
- 実体で渡す場合は特に気にすることはないが，メモリコピーなどに時間がかかり，どうしても遅くなってしまう．また，記述量も増える．これはやれば出来るので，以下には記述しない．
- indexはint型なので問題ないが，fのような配列を全て毎回コピーするのは骨が折れるかもしれない．
参照による引数渡し †
- 参照を渡す場合，関数による再帰型であれば，子ノードを呼ぶ前に引数のお膳立てするときに気にせず書き換えて，子ノードから返って来たら即刻元の状態に戻すことで参照を再帰に組み込むことが出来る．
- 具体的には，//index番目を取るのf[index] = 1;とf[index] = 0;がそれに該当する．
- これによって，ノードの行き来の間，安全に参照を書き換えることが出来る．
枝刈り †
- 戻り値を持つ再帰関数での枝刈りは少し面倒である．
- というのも，自分が枝刈りされる＝「自分が枝刈り条件に引っかかる」or「自分の子供全てが枝刈り条件に引っかかる」の２つが考えられるからである．
- 後者は，stack型や，戻り値のない再帰と違って，親が子供を見放さないことによる性質である．
- すなわち，枝刈りには以下の２つの処理が必要である．
- 「一番始めに枝刈り条件を適用して，戻り値として枝刈りされたことを親に知らせる」
- 「子ノードを全て呼び終わった後に，それらが全て枝刈りされていれば，自分も枝刈りされたとして，戻り値として枝刈りされたことを親に知らせる」
まとめ †
- すなわち，以下のように記述するのが最も機械的，かつ安全に戻り値のある再帰を記述できる．
- (1) 引数を受け取る
- (2) 枝刈りを行い，枝刈りされるのであれば，枝刈りされた印を戻り値として返す．
- (3) 終端ノードであるかどうかを確かめる．終端ノードであれば，そのための処理を行い，戻り値を返す．
- (4) ここからは子ノードの数だけ，以下を呼び出す処理
- (4-a) 親から渡された引数から，子ノードに渡す引数を生成する．親の引数が，実体ならばコピーを作成して，参照ならば改変する．
- (4-b) 子ノードを呼出して，その戻り値をret_iとして保存する．
- (4-c) (4-a)で改変した参照を元に戻す．
- (5) 子ノードが全て枝刈りされていれば，自分も枝刈りされたと親に戻り値として返す．
- (6) ret_iを用いて，何らかの演算を行い，親に自分の返すべき値を返す．
- これらは構造を限定することで，省略可能な手続きが存在する．
- (4-c)は，引数が全て実体のとき，省略することが出来る．
- (5)は，戻り値が存在しない場合，省略することが出来る．
コード例 †
int rec(const int* a, int* f, int index, int* available)
{
*available = AVAILABLE;
// 終端ノード条件
if (index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += a[i] - f[i];
return sum;
}
// 枝刈り条件
int nsum = 0;
for (int i = 0; i < index; i++)
nsum += a[i] * f[i];
if (nsum > 100) {
*available = NOT_AVAILABLE;
return NOT_FOUND;
}
// index番目を取らない
int nav;
int n = rec(a, f, index + 1, &nav);
// index番目を取る
f[index] = 1;
int pav;
int p = rec(a, f, index + 1, &pav);
f[index] = 0;
// 子供が枝刈りされる時の条件
if (nav == NOT_AVAILABLE && pav == NOT_AVAILABLE) {
*available = NOT_AVAILABLE;
return NOT_FOUND;
}
if (n > 100 && p > 100)
return NOT_FOUND;
else if (n > 100)
return p;
else if (p > 100)
return n;
else
return max(p, n);
}
stackとqueueによるDFSとBFS †
- stackとqueueはDFSとBFSにそれぞれ対応している．
- 特にstackは「全ての引数を実体で渡す，戻り値なしの再期関数」と同値な記述が可能である．
- 上で記述したように，(4-c)(5)が省略され，すっきり書くことが出来る．
- むしろこっちの性質の方が僕の主張したいことである．
- こんな感じで記述する．枝刈りが一回しかなく，n.f[n.index]=1の後に=0と戻しておらず，戻り値でNOT_FOUNDが出てこないためコードが短くなっていることに注意．
class Node {
public:
int index;
int a[NUM];
int f[NUM];
Node(int index, int *a, int *f);
};
Node::Node(int index, int *a, int *f) {
this->index = index;
for (int i = 0; i < NUM; i++) {
this->a[i] = a[i];
this->f[i] = f[i];
}
}
int main(int argc, char** argv)
{
int a[NUM] = {97, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int f[NUM] = {};
queue<Node> st;
Node firstnode = Node(0, a, f);
st.push(firstnode);
int ret = 0;
while (!st.empty()) {
Node n = st.front(); st.pop();
// 枝刈り
int nsum = 0;
for (int i = 0; i < n.index; i++)
nsum += n.a[i] * n.f[i];
if (nsum > 100)
continue;
// 終端ノード
if (n.index >= NUM) {
int sum = 0;
for (int i = 0; i < NUM; i++)
sum += n.a[i] * n.f[i];
ret = (abs(100 - ret) > abs(100 - sum)) ? sum : ret;
continue;
}
// 取らない
Node node_n = Node(n.index + 1, n.a, n.f);
st.push(node_n);
// 取る
n.f[n.index] = 1;
Node node_p = Node(n.index + 1, n.a, n.f);
st.push(node_p);
}
cout << ret << endl;
return 0;
}
戻り値なし，実体引数のみの再帰 †
- これは，上のstackと全く同じ構造となる．
- オブジェクトや配列のコピーが存在する代わりに，枝刈り条件や戻り値の条件や参照の管理が必要なくなる点で楽である．
== 2分全探索==
- int型が2進数であることを利用して，以下のように「n個の中から任意個数の選択」を記述できる．
- 本当に簡単に記述できるのでお勧め．上の再帰のものと全く同じ機能のプログラムだが，相当記述量が抑えられている．
int main(int argc, char** argv)
{
int a[NUM] = {99, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int maximum = 0;
for (int i = 0; i < round(pow(2, NUM)); i++) {
int sum = 0;
int tmpi = i;
for (int j = 0; j < NUM; j++, tmpi /= 2) {
if (!(tmpi & 1))
continue;
sum += a[j];
}
maximum = (abs(maximum - 100) > abs(sum - 100)) ? sum : maximum;
}
cout << maximum << endl;
return 0;
}
メモ化 †
- 今のところ、僕が使ったことのあるメモ化はDPテーブルと、for all, there existsの自明な条件を弾くためのメモ。
DPテーブル †
- 問題の答えの情報量を十分に持つ関数F[i][j]が存在するとする。
- この時、Fに関する漸化式と、初期条件によって、テーブルすべてを埋められることがある。
- このような使い方をDPテーブルという。
- 例が欲しい
boolの配るDP †
- 注意しないといけない！
- そもそも配るDPは+=なり可換演算を前提しているので、|=で書き込む必要。まあ集めるDPもそうなんだけど。
量化のメモ化 †
- 例えば、i=i0,j=j0である条件式P(i, j)を満たすとする。
- さらに、漸化的に、i=i0+3*n(n:自然数),j=j0は自明にP(i, j)を満たすものとする。
- すると、上の例だと全称は本当であれば、「iの個数 * jの個数」回Pをチェックしなければならないが、メモ化によって「3*jの個数」回に抑えることが出来る。
- 例が欲しい
ユークリッドの互除法 †
- 整数a, bが与えられたとき、最大公約数、最小公倍数を求めたい、というときに使うアルゴリズム。
- 非常に計算量が低く、確かlog(max(a, b))くらいだった気がする。適当。
- 拡張ユークリッドの互除法では、a*x+b*y=gcd(a, b)なるx, yを求めることが出来ます。
普通のユークリッドの互除法 †
- gcd(a, b) = gcd(b, a % b) (b != 0)
拡張のユークリッドの互除法 †
- b*x+(a%b)*y = gcd(b, a%b) = gなるx, yが求まっているとする。
- この時、a*X+b*Y=gcd(a, b) = gなるX, Yを求めたい。
- b*x+(a%b)*y = g
- ⇔b*x+(a-a/b*b)*y = g
- ⇔a*y+b*(x-a/b*y) = g
- ←X=y, Y=x-a/b*y
- つまり、一回互除したa, bでのx, yから、一つ上のX, Yが求まる、ということ。
- これを実装するとこうなる。実装はそれなりに楽。
- https://robotich.ddns.net/svn/tmp/wakatabe/cpractice/exeucledean.cpp
#include <iostream>
using namespace std;
int exgcd(int a, int b, int* x, int* y)
{
if (b) {
int prex, prey;
int tmp = exgcd(b, a % b, &prex, &prey);
*x = prey;
*y = prex - a / b * prey;
return tmp;
} else {
*x = 1;
*y = 0;
return a;
}
}
int main(void)
{
int a = 129409;
int b = 38750;
int x, y;
int g = exgcd(a, b, &x, &y);
cout << "a : " << a << endl;
cout << "b : " << b << endl;
cout << "gcd : " << g << endl;
cout << "a * x + b * y = gcd" << endl;
cout << a << " * " << x << " + " << b << " * " << y << " = " << g << endl;
return 0;
}
二分探索 †
- 一般的に二分検索として知られている二分探索法を、より一般的な形で記述する。
- 全順序とスカラー積の定められた集合のある部分集合Xに関して、ある唯一のaに対して条件Pが\( P(\{x \in X | x \preceq a\}) = true \wedge P(\{x \in X | a \prec x\}) = false \)を満たすとき、aを高速に近似探索する手法。
- 換言すれば、全順序とスカラー積の定められた集合のある部分集合Xに関して、aによる切断の特性関数Pが既知の時、aを高速に近似探索する手法。
- 計算量はO(O(P(x))log n)で、xの探索空間が大きくなければ、実質計算量はO(P(x))くらい。
- ちなみにaの一意性はXが全順序集合であることに起因する。
- 全順序は、\( \forall x \in X \forall y \in X \)xとyに等号不等号のような関係を規定できる、という意味。
- Xが有限濃度と同値になる場合（要するにXの探索空間が有限なら）、aは近似探索ではなく、有限時間で必ず一意に求まる。
- 二分探索は一般化すると、「ある条件P」を満たす全順序集合の最大最小問題と同一視できる。
- 「P(x) = trueを満たす、xの最大値を求めよ」 or 「P(x) = falseを満たす、xの下限を求めよ」
- 手法について説明したいが、これだけでは微小量eを取ったときにa-e, a+eのどちらでPがtrueになるかかは不明である。
- この差異は符号が入れ替わるだけで、どちらにしても一般性を失わないなので、a-eをXの内点と限定する。
- つまり、x<=aでP(x)=true, x>aでP(x)=false。
- アルゴリズム
- (1) Pを満たすXの元lb(lower bound)と、Pを満たさないXの元ub(upper bound)を見つける。
- (2) mid = (lb + ub) / 2に相当するXの元が条件Pを満たすか、をチェックする。
- (2-1) midがPを満たすXの元である場合、Pを満たすXの元lbをmidに入れ替える。
- (2-2) midがPを満たさないXの元である場合、Pを満たすXの元luをmidに入れ替える。
- (3) ub-lbがある(近似のため)の数値EPSを下回るまで、もしくは気が済むまで、これを繰り返す。
- なお、ubは常にlbより真に大きくなるようにPを設定しなければならない。
- また、P(lb)は絶対に1, P(ub)は絶対に0にならなければならない。
- Xが無限集合ならば、このアルゴリズムはub-lbを0に収束させるので、ub<=a<lbより、aを必ず収束させる。
- Xが有限集合ならば、このアルゴリズムはlb=(lb+ub)/2, ub=(lb+ub)/2の時にのみ収束するが、これに収束するとは一般には言えない。
- 実用上
- Xが浮動小数点の有限部分集合の場合、コンピュータ上では計算誤差と丸め誤差により、やはり収束しない。これはパソコンが正確に計算をしないために起きる。
- Xが整数型の有限部分集合の場合、aは必ず収束する。
二分検索(int) †
- \( X = A \wedge A \subset N \), Aは有限集合
- int a[NUM] = {0, 1, 3, 3, 3, 6};で3を探したい、という時にはPは以下のようになる。
- P(x) = 1 if (x <= 3), P(x) = 0 if (x > 3)とする。この時、P(x) = 1となるxを最大化する。
- 上のような問題設定を行うことで、x<=3を満たす最大のxが求まる。
- 探索空間は配列の添字の数なので、高々有限個である。
- 3があるかないかを判別する方法
- もし、配列aの中に3が含まれていれば、二分探索の結果、a=3と求まる。
- もし、配列aの中に3が含まれていなければ、二分探索の結果、a<3の数値が求まる。
- つまり、収束したaが3であるか否かを判別すれば良い。
- 例、判別はどうでもいいので二分探索部分のみ。常に、P(lb)=1, P(ub)=0なので、探索区間は[lb, ub)で狭めていく。
#include <iostream>
#include <cstdio>
#define NUM 6
#define TOFIND 3
using namespace std;
int main(void)
{
int a[NUM] = {0, 1, 3, 3, 3, 6};
int lb, ub;
// [lb, ub)
// 探索空間を配列全体にする初期化をする
lb = 0; ub = NUM;
while (ub - lb > 1) {
int mid = (ub + lb) / 2;
if (a[mid] <= TOFIND)
lb = mid;
else
ub = mid;
}
// 下が開なので、ubは探索している値になってはならない。
// よって、複数同じ値がある場合は最も添字が大きい値になる。
cout << "find " << TOFIND << endl;
cout << "lb: " << lb << endl;
cout << "ub: " << ub << endl;
return 0;
}
二分検索(double) †
- \( X = \{x | 0.0 < x <= 10000.0\} \), Xの元は浮動小数点。
- x<=1.23456を満たすxの最大値を求めたい、という時にはPは以下のようになる。
- P(x) = 1 if (x <= 1.23456), P(x) = 0 if (x > 1.23456)とする。この時、P(x) = 1となるxを最大化する。
- 上のような問題設定を行うことで、x<=1.23456を満たす最大のxが近似的に探索できる。
- 上の考察よりaは一般には収束しない。
- 例, EPS=1e-3
#include <cstdio>
#include <iostream>
#define TOFIND 1.23456
using namespace std;
int main(void)
{
double lb, ub;
// [lb, ub)
lb = 0.0; ub = 1.0e+4;
while (ub - lb > 1e-3) {
double mid = (lb + ub) / 2;
if (mid <= TOFIND)
lb = mid;
else
ub = mid;
}
cout << lb << " < " << TOFIND << " <= " << ub << endl;
return 0;
}
二分探索による最大化問題 †
- 「平均単位重さあたり価値mに対して、\( \Sigma v_i / \Sigma w_i >= m \)なるk個の選び方が存在するならP(m) = 1, しないならP(m) = 0」
- 「平均単位重さあたり価値mに対して、\( \sigma (v_i - m w_i) >= 0 \)なるk個の選び方が存在するならP(m) = 1, しないならP(m) = 0」
- つまり、「P(m) = 1 ⇔ \( v_i - m w_i \)をソートして、大きいものからk個取った和が0以上」である。
- あとはこれを実装する。ここで、上の二つの超超基本的な例と、このmain関数が酷似していることに注意。
- forで100回しか回してないけど、二分検索で100回って、1/2^100=1e-30なんで十分小さくなります。
#include <iostream>
#define NUM 5
#define KNUM 2
using namespace std;
void swap(double *a, double *b)
{
double c = *a;
*a = *b;
*b = c;
}
double v[NUM] = {1.0, 2.0, 3.0, 4.0, 5.0};
double w[NUM] = {5.0, 4.0, 3.0, 2.0, 1.0};
int prop(double m)
{
double tmp[NUM];
for (int i = 0; i < NUM; i++)
tmp[i] = v[i] - m * w[i];
for (int i = 0; i < NUM - 1; i++)
for (int j = 0; j < NUM - i - 1; j++)
if (tmp[j] < tmp[j+1])
swap(&tmp[j], &tmp[j+1]);
double sum = 0.0;
for (int i = 0; i < KNUM; i++)
sum += tmp[i];
return sum >= 0;
}
int main()
{
// [lb, ub)
double lb = 0.0, ub = 10000.0, mid;
for (int i = 0; i < 100; i++) {
mid = (lb + ub) / 2;
if (prop(mid))
lb = mid;
else
ub = mid;
}
cout << mid << endl;
}
再帰の処理の順序 †
- 木構造探索のパターン
- 再帰の前の処理は「下がるときにやる」
- 再帰の後の処理は「上がるときにやる」
- グラフは、メモ化再帰するとDAGになるというのが大事な気がする
ポインタ †
- 意味論
- 関数引数のデータ量を軽くするためのポインタ
- 配列のスタートポイントを指定するためのポインタ
- 動的オブジェクト作成のためのポインタ
乱数関数呼び出し †
キャッシュ効率 †
- キャッシュ効率
TL4sでTLEしてたコードの配列の添え字の順番入れ替えたら483msになって通って、さすがに意味不明すぎる
ちゃんとよく回す変数は一番最後の添え字にしておくことが定数倍速くするのにめちゃくちゃ重要っぽい
a/bの切り上げ †
- 切り上げのコーディングイディオム
(a-1)/b+1
- この方法だと、aもbも一回ずつしか出てこないから嬉しい。
pythonのswapみたいな術 †
tie(i, j) = mt(j, i)
足してsになる数列の全列挙 †
- 数列に制限がない場合
- next_permutationに0000001111みたいなのを食わせて、連続1をカウントする
- n!ではなくnCkで停止する
- ある場合
時変するデータ構造 †
- プログラムのどこのところで何を持っているのかをきちんとコメントに書く
- 全てのプログラム・カウンタの位置について、このデータ構造は何を保持している、というのを明示的定義をしている必要があると思うのだけど、正直そんな脳の要領がない
- DPの使い回しで、数学ではD_{i, j} = max(D_{i-1, j}, D_{i-1, j+w_i} + p_i)が、逆回しDPテーブル使い回しでDP[j] = max(DP[j], DP[j+w[i-1]]+p[i-1])になったりするけど、これも「DP[j]=i, jのループが回るまえはD_{i-1, j}で回ったあとはD_{i, j}」とか表記がプログラム・カウンタに依存する
- グラフのDFSとかもっとそれが顕著で、閉路探索するDFSではvisitedだけではなくvisitingの状態を保持しなきゃいけなかったりするけど、一体どのタイミングをvisitedと呼ぶのか？とか、そのへんの「データの意味がプログラムポインタの位置により逐次的に変化する」系の実装をどうすべきか答えがでてない
- 例えばダイクストラでpriority_queue qとint mindist[n]があったとして、初期値にq.push(start);を入れるのはまあ自明として、mindist[start] = 0とするのはあまり自明じゃない
検索のwhile †
- whileの検索パターンは
- 欲しいものを明確化し、
- 停止条件を明示することが極めて重要
- while(i<n&&!(f(i)) i++;は、二値判定関数f(i)がi<nで定義される関数だとして、f(i)を満たす最初のiを検索する。
2つのテーブルを使い回すDP †
- STLのswapは速いので、DPそのものをswapしたほうがいい。
- curr = i % 2, next = (i + 1) % 2ではなくて
隣接グラフ †
DPの特異点 †
- 自然数iをj分割するDP、考察も初期値も実装も何もかも自明ではない
- DP[i][j] = DP[i-j][j] + DP[i][j-1]を考える。実装上注意すべきポイントが詰まっている。
- 初期値は何か？
- 結論、j=0である。
- DP[i][0] = 1…ではない！！！DP[0][0] = 1, DP[0][j!=0] = 0が正しい初期値。
- いい加減に初期値を決めない。
- DPの特異点
- 特異点とは、自己辺が張られているような遷移が存在する位置である。ここは初期値として与えなければならない。
- i=i-j, j=jを連立方程式として解くと、j=0が出てくる
- どういう意味かというと、ここにアクセスすると自己辺がはられてるのでバグる
- 自己ループが張られる状態について適当に集めて正しく計算ができるのは、運が良いだけ。
- 集めるDPの場合、自己ループが存在するため、ここにアクセスしてはならない！
- 以下のような感じで実装するのがそもそものパターンであるべき
rep(i, n) rep(j, n) if (isSingular(i, j)) {
dp[i][j] = init(i, j);
}
rep(i, n) rep(j, n) if (!isInited(i, j)) {
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
- DP[i][j] = DP[i-j][j] + DP[i][j-1]の式を出すのキツい。場合の数苦手だなあ。
- DP範囲外の値へのアクセス
- 今回、DP[i<0][j]みたいなやつにアクセスする。
- 数学側で、この値をきちんと考えて自然な定義にして拡張すると、実装が楽になる
- まあ、普通はif (from_i >= 0 && from_j >= 0) DP[i][j] += DP[i][from_i][from_j]みたいにすればよいんだけど
- 特異点と配るDP
- DP遷移の特異点に注意しなければならないのは配るDPでも同様。自分に配るとバグる。
- DP範囲外の値へのアクセスと配るDP
- 配らなくて良い範囲が零元であることを前提としているだけだから、
- 分割数では配るDPではバグりくいけど、一般ではバグってもおかしくない、
- 初期値は常に特異点か？
- そんなことはないが、特異点ならば初期値を必ず与えなければならないは真っぽい。
- 集めるDPで初期値にアクセスするのはそもそも馬鹿
- 逆に、特異点だからアクセスしてはいけないのではなくて、初期値だからアクセスする意味がないししてはいけない
累積和 †
- 累積和を元の配列を捨てても良い時のメモリ削減パターン
- as[i+1]=a[i]と初期化してas[i+1]+=as[i]とするやつ
- 元のを得るのも別に[i, i+1)を足せば良いので楽
整数の整数乗 †
連続の云々 †
- 連続を数えるようなものはバグりやすいことが知られている
- めんどい時はUFを使うとよい。連結成分の個数を管理したほうがよいことが多い。
00001101101011->2212
DPの最大サイズは添字の大文字で †
count関数 †
- 使ったら絶対llでキャスト！unsignedだから計算途中で負にしたりして悲しいことが起きる
builtin関数 †
- ある数xが2で割り切れる回数は、__builtin_ctzll(x)で求められます（t(railing) z(eros)の数をc(ount)しているため）
ランタイムエラー †
- sortに渡すラムダの比較関数が間違ってるとランタイムエラーが起きる。
例外処理のための1-indexed †
- 実装上、「最後に〜した添字」みたいなものを持つ必要があって、そのような添字が存在しない可能性がある場合は、わざと1-indexedで書いて添字0を例外地として扱うと実装が楽になる可能性がある
roundでも+EPSが必須の場合がある †
- 2019 TCO R1A Hard
- 1.0049999999が1.005になったりしませんか（冷静に考えると、大概整数の乗算除算で出てくる誤差死のはりあんさんの言ってる案件が多い気がしてきました）
- 問題に登場する値の範囲などから、1.004999999 が計算中に出てこないという仮定を置くことでこれが使えるようになります（もちろんこの仮定が成り立たない問題もあり、そういう場合は有理数などで計算をする必要があります）
- なるほど、roundでeps足すのは初めて聞くテクだったので勉強になりました、ありがとうございます！
- まぁ基本的な考え方は切り捨ての時にepsを足そう、というのと全くおんなじだと思います
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
