アルゴリズム

螺旋本

・導入問題

・挿入ソート

・バブルソート

・選択ソート

・安定なソート

・シェルソート

・スタック

・キュー

・連結リスト

・データ構造の応用：面積計算

・線型探索

・二分探索

・ハッシュ

・探索の応用：答えから二分探索

・全探索：再帰で全探索

・コッホ曲線：再帰で図形描画

・マージソート

・パーティション

・クイックソート

・計数ソート

・反転数：ai>ajかつi<jである組の数

・最小コストソート：荷物を取り替えるときの最小のコスト

・根付き木の表現

・二分木の表現

・木の巡回

・木の復元

・二分探索木

・完全二分木

・最大・最小ヒープ

・優先度付きキュー

・フィボナッチ数列

・最長共通部分列

・連鎖行列積

・グラフの表現

・DFS

・BFS

・連結成分

・最小全域木：プロム法

・ダイクストラ

・Union-Find

・kD-Tree：特定の値が指定された領域の入るかを判定

・ワーシャルフロイド：全点対間最短距離

・トポロジカルソート：DAGを一列に並べる

・関節点：エッジを削除した部分グラフが非連結になる点

・木の直径：最遠節点間の距離

・最小全域木：クラスカル法

・直線の直交・平行判定

・射影

・反射

・反時計回り

・線分のこうさ

・線分の交点

・円と直線の交点

・円と円の交点

・点の内包

・凸包：アンドリューのアルゴリズム

・線分交差問題：平面走査

・コイン問題

・ナップザック問題

・最長増加部分列

・最大正方形

・最大長方形

・素数判定

・最大公約数

・冪乗

・８クイーン問題：バックトラッキング

・８パズル

・15パズル：反復深化、IDA*、A*

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

1章 オンラインジャッジを活用しよう

(ry

2章 アルゴリズムと計算量

与えられた問題を解く方法は１つとは限らず、様々なアルゴリズムを適用することができる

一般的にはアルゴリズムは、時間計算量と領域計算量のトレードオフやバランスを考えてアルゴリズムを設計する

領域計算量より時間計算量の方が問題になることが多い

アルゴリズムの計算量は、最善、平均、最悪の場合について見積もることができる

一般には最悪の場合について見積もる

10^7~10^8程度であれば数秒以内で処理が行えると考えておく

3章 初等的整列

・挿入ソート

・バブルソート

・選択ソート

・安定なソート

・シェルソート

3-1 ソートについて

・安定なソート

同じ数字を持つカードが複数ある場合それらが入力に出現する順序で出力されることを安定なソートアルゴリズムという

まあSTLを使えばOK

3-2 挿入ソート

ソートされている並びにどんどん入れていく

3-3 バブルソート

バブルソートでは、各計算ステップで配列はソート済みと未ソートに分けられる

末尾から隣接する要素を比べていくのを繰り返す

バブルソートの交換回数は転倒数

3-4 選択ソート

選択ソートは各計算ステップで１つの最小値を選択していく直感的なアルゴリズム

3-5 安定なソート

ソートの結果が安定かどうかしばよいばえるためにカードのくみに対する準ばお愚直に調べよ

3-6 シェルソート

shellsortは一定の間隔gだけ離れた要素のみを対象とした挿入ソート

4章 データ構造

・スタック

・キュー

・リスト

4-1 データ構造とは

データ構造とは、プログラムの中のデータの集合を系統立てて管理するための形式で、一般的に単にデータの集合を表すだけではなく、以下の3つの概念から成り立っている

・データの集合

・規則

・操作

・スタック

一時的にデータを退避したいときに有効なデータ構造

push(x)

pop()

isEmpty()

isFull()

などの操作がある

当然O(1)

・キュー

データを到着順に処理したいときに使用するデータ構造

enqueue(x)

dequeue()

isEmpty()

isFull()

などの操作がある

当然O(1)

・リスト

順序を保ちつつ特定の位置へのデータの挿入・削除を行うデータ構造については最初に必要なメモリを確保する固定長の配列ではマシンの資源を効率的に活用する実装が難しくなるので、この問題の要求に答えるものとして双方向連結リストがある

双方向連結リストへの要素の追加はポインタをつなぎ変えるだけなのでO(1)

要素へのアクセスは配列ではO(1)だが、リストではポインタを辿る必要があるのでO(N)

先頭と末尾は当然O(1)

・STL

vectorは要素の挿入・削除にO(N)

listは[]演算子で各要素にアクセスできないが、イテレータを用いて順番にアクセスできる

要素の挿入と削除をO(1) で行える

4-2 スタック

逆ポーランド記法で記述された数式はスタックを用いて計算を行える

4-3 キュー

ラウンドロビンスケジューリングを実装できる

リングバッファで実装する

4-4 連結リスト

高速にデータを入れられる

4-5 STLによるデータ構造

4-6 面積計算

スタックで実装できる

5-1 探索について

・線形探索

普通に前から順番に調べる

番兵という工夫で定数倍の高速化ができる

・二分探索

ソートされたデータを高速に調べる

ソートすれば二分探索が使えるという考え方は色々な問題に応用できる

STLのlower_boundを使えば良い

・ハッシュ

ハッシュ関数と呼ばれる関数値によって要素の格納場所を決定する

ハッシュテーブルという表を用いるアルゴリズムである

要素のキーを引数とした関数を呼び出すだけでその位置を特定できる

O(1)で要素の挿入や検索が行える

イテレータを使うと、どの種類のコンテナに対しても同じ方法でそれらの要素にアクセスできる

さらに配列の要素に対しては、通常のポインタのように扱える

5-2 線型探索

番兵を使えば定数倍の改善ができる

5-3 二分探索

5-4 ハッシュ

衝突を無視すればO(1)で要素の挿入や、検索ができる

5-5 STLによる探索

5-6 探索の応用

6章 再帰・分割統治法

・全探索

・再帰関数

・分割統治法

6-1 再帰と分割統治

問題を部分的な小さな問題を解くことによって元の問題を解くテクニックは様々なアルゴリズムに現れる

その一つが分割統治法

分割統治法

再帰のテクニックを用いると、ある問題を２つ以上の小さい問題に分割して、再帰関数によりそれぞれの部分問題を求めそれらの結果を統合することにより元の問題の解を求めることができる場合がある

このようなテクニックを分割統治法という

1.与えられた問題を部分問題に分割する

2.部分問題を再帰的に解く

3.得られた部分問題の解を統合して元の問題を解く

再帰関数の中で2つの再起関数を呼び出すことを繰り返せば、O(2^n)のアルゴリズムとなり、全ての組み合わせを調べる方法は大きなnに対して適用できない

このアルゴリズムでは、(i,m)の組みについてsolve(i,m)が複数回計算されてしまう無駄があるので、動的計画法というテクニックで改善できる

6-2 全探索

6-3 コッホ曲線

7章 高等的整列

・パーティション

・高等的整列

ここでは、O(nlogn)の高速なアルゴリズムと条件付きでO(n)で動くソートアルゴリズムに関する問題を解く

・マージソート

マージソートのそう計算量はO(nlogn)になる

マージソートは入力データを保持する配列以外に一時的なメモリ領域が必要になる

・パーティション

大きさで左右に分ける

・クイックソート

クイックソートも分割統治に基づくアルゴリズムだが、分割してパーティションを行った時に元の配列内でソートが完了するので統治にあたる明示的な処理はない

クイックソートは安定なソートアルゴリズムではないが、追加のメモリ領域を必要としない

クイックソートの平均計算量はO(nlogn)だが、最悪の場合はO(n^2)である

・係数ソート

係数ソートは各要素が0以上k以下である要素数nの数列に対して、O(n+k)で動く安定なソーティングアルゴリズムである

・STL

クイックソートがベースでO(nlogn)なのでsortを使っとけばよい

7-1 マージソート

指定された要素を腹部部分配列を半分に分割する

それぞれソートする

得られた部分配列を統合する

7-2 パーティション

ある基準よりも小さいものを左に集めて大きいものを右に集める

7-3 クイックソート

partitionで分割してクイックソートを行う

マージソートと同様に分割統治法に基づくアルゴリズムである

クイックソートは追加のメモリを必要としないインプレースソートである

7-4 係数ソート

各要素の値の範囲が決まってる時に線型で動く

7-5 STLによるソート

sort

7-6 反転数

数列Aでai>ajかつi<jである組みの個数を反転数という

バブルソートの交換回数と等しくなる

8章 木

・木構造

・二分木の表現

・木の巡回

8-1 木構造について

木構造は効率的なアルゴリズムとデータ構造を実装するための基礎構造で、情報処理とプログラミングには欠かせない概念となる

標準ライブラリとして提供されている多くのアルゴリズムやデータ構造が木構造に関連している

・根付き木の表現

木構造とはnodeとedgeで表されるデータ構造

rootと呼ばれる他と区別された１つの節点を持つ木を根付き木と呼ぶ

根付き木の節点には親子関係がある

根付き木Tの節点xの子の数をxの次数という

根rから節点xまでの経路の長さをxの深さ(depth)という

節点xから葉までの経路の長さの最大値を節点xの高さ(height)という

・二分木

１つの根を持ち、全ての節点についてその子の数が２以下である木を根付き二分木という

二分木では、左の子と右の子は区別される

8-2 根付き木の表現

節点の個数、各節点の情報(子)が与えられ、parent、depth、typeを出力する

左子右兄弟表現によって木を表すことができる

節点uの親、最も左の子、すぐ右の兄弟

u.parentで親

u.leftが存在しない節点がleaf

u.rightが存在しない節点が最も右の子

存在しないことはNILで表す

ループで深さを求めるより再帰的に深さを求めた方が良さそう

8-3 二分木の表現

u.parent

u.right

u.left

8-4 木の巡回

根節点、左部分木、右部分木の順番で節点の番号を出力するのを先行順巡回という

左部分木、根節点、右部分木という順番で節点の順番を出力するのを中間順巡回という

左部分木、右部分木、根節点という番号で出力するのを後行順巡回という

8-5 木の復元

ある二分木に対して、それぞれ先行順巡回と中間順巡回を行って得られる節点の列が与えられるので、その二分木の後行順巡回で得られる節点の列を出力するプログラムを作成せよ

9章 二分探索木

9-1 二分探索木について

・二分探索木：挿入

・二分探索木：探索

・二分探索木：削除

連結リストの要素を探索するにはO(n)必要である

動的な木構造を用いれば、データの追加・削除・探索をより効率的に行うことができる

探索木は挿入、検索、削除などの操作が行えるデータ構造で、辞書あるいは優先度付きキューとして用いることができる

xを二分探索木に属するある節点とし、yをxの左部分木に属する節点とすると、yのキー <= xのキーである

これが無限に続く

二分探索木に中間順巡回を行うと、昇順に並べられたキーの列を得ることができる

一般的に挿入、検索、削除を行うことができる二分探索木はそれらの計算量がO(logn)となるように実装される

そのためには常に木の高さをできるだけ低く維持する必要がある

バランスが取れた二分木を平衡二分木という

9-2 挿入

insert操作では、二分探索木条件を保つように与えられたデータを正しい位置に挿入する必要がある

二分探索木は、C++では構造体で定義された節点をポインタでつなげることによって実装できる

insertは節点zを挿入するいちを根を始点として探す

9-3 探索

find：キーkが存在するか否かを報告

を実装する

9-4 削除

9-5 STLによる集合の管理

・STL

要素の集合を管理するSTLのコンテナはシーケンスコンテナと呼ばれる順序付きのコレクションと連想コンテナというソートされたコレクションがある

シーケンスコンテナでは追加される要素は値に関係なく、特定の位置に配置されるvectorやlistなど

連想コンテナでは追加される要素の位置は何らかのソート基準によって決められる

set, map, multiset, multimapなど

連想コンテナでは、常に二分探索が行え、要素の探索を高速に行える

setはinsert, erase, findがO(logn)で行える

mapも同じく、insert, erase, findがO(logn)で行える

10章 ヒープ

10-1 ヒープについて

・完全二分木

・二分ヒープ

・優先度つきキュー

データ構造には操作と取り出す時のルールが存在した

データの到着順ではなく、データが持つあるキーを基準にして優先度が高いものから取り出す優先度付きキューは高等的なアルゴリズムの実装において重要な役割を果たす

優先度付きキューは、二分探索木を応用して実現できるが、バランスの良い木を保ちながら効率的な操作を行うには工夫が必要であり、その実装は簡単ではない

二分ヒープというデータ構造を用いれば比較的簡単に優先度付きキューを実装できる

・完全二分木

全ての葉が同じ深さを持ち、内部接点の子の数が2であるような二分木を完全二分木という

また、最下位レベルの葉が左から順に埋まっている木もおおよそ完全二分木と呼ぶ

完全二分木では、節点の数をnとすると、木の高さが常にlog2nとなるためこの性質を利用して高速なデータの管理を行うことができる

・二分ヒープ

二分ヒープは木の各節点に割り当てられたキーが１つの配列の各要素に対応した完全二分木で表されたデータ構造である

二分ヒープは論理的な構造は完全二分木となるが、実際は１次元配列を用いて表す

二分ヒープの各接点のキーはヒープ条件を保つように格納される

この二分ヒープのデータ構造を用いれば、大小関係を保ちつつ、優先度が高い要素の取り出しと新しい要素の追加を効率的に行える

親はi/2, 左の子は2i, 右の子は2i+1に対応する

・優先度付きキュー

各要素がキーを持ったデータの集合Sを保持するデータ構造

挿入と削除はどちらもO(logn)

10-2 完全二分木

10-3 最大・最小ヒープ

10-4 優先度つきキュー

優先度付きキューSに対して、insert(S, k)、extractMAX(S)を行うプログラムを作成する

キーをが大きいものを優先するmax-優先度付きキューはmax-ヒープによって実現できる

10-5 STLによる優先度つきキュー

・STL

priority_queueを使えばよろしい

11章 動的計画法

・フィボナッチ数列

・最長共通部分

・連鎖行列積

・動的計画法

動的計画法は最適な解を求めるための数学的な考え方である

再帰を使った方法はメモ化再帰とも呼ばれる

また漸化式を使った方法もある

小さい部分問題の解をメモリに記憶しておいて、大きい問題の解を計算するのが動的計画法

11-2 フィボナッチ数列

11-3 最長共通部分列

xm = ynのときは、Xm-1とYn-1のLCSニxmを連結しt真央のがXmとYnのLCSとなる

xm != ynのときは、Xm-1とYnのLCSあるいはXmとYn-1のLCSのどちらか長い方がXmとYnのLCSとなる

11-4 連鎖行列積

という変数を準備すると漸化式が組める

O(n^3)

12章 グラフ

・グラフの表現

・深さ優先探索

・幅優先探索

・連結成分

コンピュータで扱う多くの問題は対象とそれらの関係を抽象的に表したグラフというデータ構造で表せる

この章ではグラフの概念を学習し、データ構造として実装方法、グラフの初等的なアルゴリズムに関する問題を解く

・グラフの種類

無向グラフ、有向グラフ、重み付き無向グラフ、重み付き有向グラフがある

閉路のない有向グラフをDAG(directed acycli graph)という

G’の頂点集合と辺集合の両方がGの頂点集合と辺集合の部分集合となっているとき、G’をGの部分グラフという

グラフの基本的なアルゴリズムとして深さ優先探索と幅優先探索がある

幅優先探索は最短経路を求めるアルゴリズムの１つとして応用することができる

グラフは隣接リストと隣接行列による表現がある

・隣接行列の長所

・隣接行列の短所

-頂点の数の二乗に比例するメモリを消費する

-頂点uからvへの関係を1つしか記録できない

・深さ優先探索

スタックによる実装と再起による実装がある

隣接行列を用いた深さ優先探索ではO(|V|^2)となるので大きなグラフに対しては適当ではない

後に隣接リストを使ったより高速な実装を学習する

また、大きなグラフに対する再帰を用いた深さ優先探索はスタックオーバーフローを起こす可能性がある

・幅優先探索

キューを用いて実装する

隣接行列を用いた幅優先探索もO(|V|^2)

・連結成分

連結成分はDFSやBFSで見つけられる

頂点すうとエッジ数が多い大きなグラフに対してはO(n^2)のメモリを必要とする隣接行列は用いることはできないので隣接リストを使う

隣接リストを用いたDFSとBFSはO(|V| + |E|)

頂点uとvの関係を調べるにはuに隣接する頂点の数をnとすると、O(n)のリストを探索しなければならないが、DFSやBFSのように多くのアルゴリズムでは、一度ずつ順番に辿れば良いので問題にならない

12-2 グラフの表現

隣接リストからから隣接行列を出力せよ

12-3 深さ優先探索

再帰関数(C)

12-4 幅優先探索

12-5 連結成分

SNSの友達関係を入力し、双方向の友達リンクを経友してある人からある人へ辿り着けるかどうか判定するプログラムを作る

必ずしも連結ではないグラフに対して、その極大で連結な部分グラフを連結成分という

連結成分はDFSやBFSで見つけられる

探索の際、異なる番号を頂点にふることで同じグループかどうか判定できる

13章 重みつきグラフ

・最小全域木

・最短経路

・最小全域木

木とは閉路を持たないグラフである

全域木とはグラフの全ての頂点を含む部分グラフであって、木である限りできるだけ多くの辺を持つものをいう

グラフの全域木はDFSかBFSで求められるが、全域木は１つとは限らない

最小全域木とは全域木のなかで辺の重みの総和が最小になるものである

プリム法で求められる

・最短経路

DPの一種であるダイクストラ法を使う

ただし、負の重みを持つグラフにはベルマンフォード法やワーシャルフロイド法を使う

優先度付きキューを使うと計算量が変えられる

13-2 最小全域木

13-3 単一始点最短経路

要するにダイクストラ法

14章 高度なデータ構造

・Union-Find

・領域探索

・Union-Find

データを互いに素な集合に分類して管理するためのデータ構造である

経路圧縮とrankを用いた実装はO(logn)より高速

・領域探索

二分探索木を使う

・セグメントツリー

14-1 互いに素な集合

15章 高度なグラフアルゴリズム

・全点対間最短経路

・トポロジカルソート

・関節点

・木の直径

・最小全域木

・関節点

頂点uとそこから出ている全てのエッジを削除して得られる部分グラフが非連結になる時、頂点uをグラフGの関節点という

・トポロジカルソート

グラフの全ての有向辺が左から右へ向かうように全ての頂点を水平線上に並べること

・木の直径

木の最遠節点間の距離を木の直径という

・最小全域木

クラスカルのアルゴリズム

・最大マッチング、最大フロー

15-1 全点対間最短経路

ワーシャルフロイド

ワーシャルフロイドは負の閉路がなければ正しく動作する

逆にいうと、負の閉路があるかどうかを判定できる

15-2 トポロジカルソート

グラフのトポロジカルソートは全ての有効辺が左から右へ向かうように全ての頂点を水平線上に並べること

15-3 関節点

15-4 木の直径

15-5 最小全域木

16章 計算幾何学

・幾何学的オブジェクトの基本要素と表現

・直線の直交・平行判定

・射影

・距離

・線分の交差判定

・点の内包

計算幾何学は幾何学的な問題をコンピュータで解くための効率的なアルゴリズムとデータ構造を研究するための学問である

16-1 幾何学的オブジェクトの基本要素と表現

16-2 直線の直交・平行判定

16-3 射影

16-4 反射

16-5 距離

16-6 反時計回り

外積を利用してベクトルの関係を調べるあ

16-7 線分の交差判定

16-8 線分の交点

16-9 円と直線の交点

16-10 円と円の交点

16-11 点の内包

16-12 凸包

アンドリューのアルゴリズム

16-13 線分交差問題

平面走査

セグ木を使って解くこともできる

17章 動的計画法

・コイン問題

・ナップザック問題

・最長増加部分列

・最大正方形

・最大長方形

DPは特定の問題を解くためのアルゴリズムではなく、汎用性のあるプログラミングテクニックである

17-1 コイン問題

m種類のコインを使ってn円払うときのコインの最小の枚数を求める

17-2 ナップザック問題

いつもの

17-3 最長増加部分列

17-4 最大正方形

17-5 最大長方形

18章 整数論

・素数判定

・最大公約数

・冪乗

18-1 素数判定

18-2 最大公約数

18-3 冪乗

19章 ヒューリスティック探索

・バックトラック

・IDA

・A*

与えられた問題を解析的に解くのが無理な場合または効率的なアルゴリズムが知られていない場合には試行錯誤を繰り返して解を探さなくてはいけないが、無駄な探索を避けたり、より早く解を見つけるための工夫が必要になる

19-1 8クイーン問題

どのクイーンも他のクイーンを襲撃できないように8つのクイーンを配置する問題

普通に全列挙すれば8!で事足りる

バックトラックを適用すればさらに効率的に8クイーン問題を解ける

・１行目の任意のマスにクイーンを配置する

・１行目に配置したクイーンによって襲撃されない２行目のマスにクイーンを配置する

・どのクイーンも襲撃されないi+1マス目がなければ１つ戻って、別の方法を試す

深さ優先探索もバックトラックのアルゴリズムである

19-2 8パズル

よくあるパズル

パズルの問題は状態遷移を繰り返してゴールを発見する探索アルゴリズムで解くことができる

多くの探索アルゴリズムでは一度生成した状態を再度生成しないように探索の空間は木になる

各状態の生成状況を効率的に管理するにはハッシュ法や二分探索木をつかう

８パズルのように考えられる状態の総数がそんなに多くなければDFSやBFSで解が出せる

深さ優先探索の深さに制限を持たせた方法を深さ制限探索という

問題の性質から深さを制限することができれば探索を高速化できる

幅優先探索は多くのメモリを必要とするが、問題に解が存在すれば初期状態から最終状態までの最短の経路を比較的簡単に求められる

19-3 15パズル

この問題は状態の数が膨大になるので、8パズルを解くことができたDFSやBFSでは解けない

反復深化

深さを制限した深さ優先探索を繰り返すことによって最短経路を求められる

深さの制限を増加させながら、解が見つかるまで深さ制限探索をする

一般的に、反復深化では高速化を図るため、探索済みの状態をメモリに記憶しない

ただし１つ手前の状態に戻らないようにするなど、適宜工夫をする

IDA*

反復深化において推定値を用いて枝を刈るアルゴリズムをA*またはIDA*という

ここで推定値はヒューリスティックとも呼ばれ、ゴールまでの下限値の推定値として用いることができる

15パズルでは、現在の状態から最終状態までの最短コストを見積もることができれば枝を刈ることができる

見積もりは正確な値である必要はない

実践的プログラミング

授業めも

第1章 はじめに

各章は90~105分の演習時間を想定して作られている。

問題名に印がつくと難易度が5倍難化する

優しい問題と解いたら一旦次の章に進めば良い

経験が少ない段階では15分以上悩まないことをお勧め

問題に取り組み手順

１.問題を把握

2.計算手順を検討

3.プログラムを書く

4.手元のコンピュータで動作確認をする

5.AOJに提出して確認する

C++でg++ -Wallで、警告を有効にできる

標準入出力とリダイレクションによるファイルを用いたテスト

./a.out < years.input

キーボード入力の代わりにファイルから読み込む

./a.out < years.input > test-output

実行結果をファイルに保存

diff -u test-ouput years.output

自動的な比較

第2章 入出力と配列：シミュレーション

概要：様々な解放につながる基本として、入力データを逐一調べる問題から初めて、配列と周へんの基本操作を取り上げる

また、プログラムを一度に作成するのではなく、部品ごとに作ってテストするスタイルを身につける

さらに、データの量に応じて適切なアルゴリズムが必要になることを経験する

C++で一秒間で実行可能な演算回数の目安

10^6：余裕を持って可能

10^7：多分可能

10^8：シンプルな演算であれば可能

目安として、最近の多くのコンピュータはCPUは1GHzで動作しているのでCPUが100サイクル以内にできる演算なら一秒間に10^6実行可能と期待できる

配列、std::vector、std::arrayと操作

Cの行列は定義の際に定数で長さを与える必要がある

C++はvectorを用いることで、長さを実行時に決められる

arrayは定義の際に長さを定数で与える必要のあるvector

配列のすべての要素を処理する場合はforを用いることが一般的

第3章 整列と貪欲法

ペアの配列は第一要素が異なれば第一要素が同じなら第二要素が比較される

貪欲法はいい方からとっていくアルゴリズム

第4章 動的計画法1

全ての可能性を調べ尽くすのが難しい問題も小さい問題をあらかじめ解いて答えを表に覚えておけば簡単に解ける場合がある

DPは問題が持つ部分構造最適性を利用して効率の良い計算を実現する方法

第5章 分割統治

分割統治ほうは問題を小さな問題に再帰的に分解してそれぞれを解いた上で順次それらを組み合わせて全体の解を得る

分割統治では分割した問題間に重なりがない場合を扱う

例えば二分探索

第6章 基本データ構造

string

stack

queue

set

map

第7章 グラフと木

グラフの表現は隣接行列や隣接リスト

第8章 全域木とDisjointSet

全域木を求めるクラスカル法

第9章 繰り返し二乗法と冪乗

繰り返し二乗法が使える問題では10億ステップ後のシミュレーション結果も求められる

第10章 グラフの探索

連結なグラフの辺を全て辿る方法としてBFSとDFSを紹介する

第11章 最短経路問題

ワーシャルフロイド

ダイクストラ

第12章 平面の幾何

いろいろ

第13章 簡単な構文解析

特定の文法で書かれた文字列を計算機に理解させる

第14章 整数と連立方程式

いろいろ

第15章 補間多項式と数値積分

FFT

第16章 区間の和、最大値、最小値と更新

累積和

BIT

セグ木

第17章 ネットワークフローとマッチング

第18章 組み合わせゲーム

付録

バグとデバッグ

ループ不変条件

Ruby

チーター本

・KiwiJuiceEasy：やるだけ

・InterestingParty：全探索、連想配列の工夫

・Cryptography：全探索or数学

・InterestingDigits：全探索or数学

・ThePalindrome：回文全探索

・FriendScore：全探索

・CrazyBot：BFS、DFS

・MazeMaker：BFS

・NumberMagicEasy：bit全探索

・CorporationSalary：メモ化再帰

・BadNeighbors：DP

・ChessMetric：DP

・HandShaking：数学、DP

・ColorfulBOxesAndBalls：全探索

・StockHistory：貪欲

・BatchSystem：貪欲

・AutoLoan：二分探索で逆算

・CircleCountry：数学

・HamiltonPath：数学

・BinaryFlips：シミュレーション、数学

・CantorDust：数学、考察

・NotTwo：数学、実験

・CutSticks：答えから二分探索

・InfiniteSequence：DP、考察、半分全列挙みたいな

・FloorBoards：DP

蟻本

準備編

・くじ引き

・三角形

・Ants

2-1 全探索

・部分和問題

・Lake Counting

・迷路の最短路

2-2 貪欲法

・硬貨の問題

・区間スケジューリング問題

・Best Cow Line

・Saruman’s Army

・Fence Repair

2-3 DP

・01ナップサック問題

・最長共通部分列問題

・個数制限なしナップサック問題

・01ナップサック問題2

・個数制限つき部分和問題

・最長増加部分列問題

・分割数

・重複組み合わせ

2-4 データ構造

・Expedititon

・Fence Repair

・食物連鎖

2-5 グラフ

・二部グラフ判定

・最短路問題

・最小全域木

・RoadBlocks

・Conscription

・Layout

2-6 数学

・線分上の格子点の数

・双六

・素数判定

・素数の個数

・区間ないの素数の個数

・Carmichael Numbers

2-7 GCJ1

・Minimum Sxalar Product

・Crazy Rows

・Bribe the prisoners

・Millionaire

3-1 二分探索

・lower_bound

・Cable master

・Aggressive cows

・平均最大化

3-2 頻出テクニック1

・Subsequence

・Jessica’s Reading Problem

・Face The Right Way

・Fliptile

・Physics Experiment

・4 Values whose Sum is 0

・巨大ナップサック

・領域の個数

3-3 データ構造

・Crane

・バブルソートの交換回数

・A Simple Problem with Integers

・K-th Number

3-4 DPを極める

・巡回セールスマン問題

・Traveling by Stagecoach

・ドミノ式つめ

・フィボナッチ数列

・Blocks

・グラフの長さkのパスの総数

・Matrix Power Series

・Minimizing maximizer

3-5 ネットワークフロー

・最大通信量

・仕事の割り当て

・二人組

・最小コスト通信

・Asteroids

・Evacuation

・Dining

・Dual Core CPU

・Farm Tour

・Evacuation Plan

・The Windy’s

・Intervals

3-6 計算幾何

・Jack Straws

・White Bird

・Ceneology

・Beaty Contest

・Intersection of Two Prisms

3-7 GCJ2

・Numbers

・No cheating

・Stock Charts

・Watering Plants

・Number Sets

・Wi-fi Towers

4-1 数学2

・ランダムウォーク

・包除原理

・周期的でない文字の数え上げ

・石の塗り方の数え上げ

4-2 ゲーム

・コインのゲーム１

・A Funny Game

・

---準備編---

・くじ引き

4重ループを回すだけ

この本のプログラムはmain関数で読み込まれてグローバル変数に置かれたのち、関数solveが呼ばれることによって問題を解く形式

・三角形

n本の棒から、3本を選んでできるだけ周長の長い三角形を作る

最大の周長を求める

3重ループを回すだけ

・Ants

全てのアリが竿から落ちるまでの最小の時間と最大の時間

最小の場合は簡単

最大の場合は少し実験すればOK

・くじ引き（難しいver）

DPでも出来そう？後でやってみろ

最後の１つを二分探索にすることでO(n^3logn)

kc+kdのとり得るn^2の値をあらかじめ列挙してソートしておけば二分探索ができる

これでO(n^2logn^2)

---初級編---

2-1 全ての基本全探索

・再帰関数

・スタック

pushとpopができる

・キュー

pushとpopができる

・DFS

・部分和問題

・BFS

BFSのような順番で状態の遷移しながら、メモリ使用量を抑える反復深化深さ優先探索というものもある

・迷路の最短経路

・特殊な状態の列挙

全ての解候補を生成するのにはDFSを利用するのがほとんどだが、特殊な状態空間のば良いには短く描く方法がある

next_permutationやビット演算でnCkの組み合わせや部分集合を列挙することもできる

・枝刈り

全探索は解の候補が多くなると、計算量が増大してしまう

例えば、深さ優先探索を行っているとそれ以上遷移して行っても解が存在しないことが明らかな場合がある

このような場合に探索を打ち切ることを枝刈りという

・Column「スタック領域とヒープ領域と静的領域」

関数を呼び出すときにもとの関数におけるローカル変数などをどこかに保存しておく必要がある

この領域をスタック領域という

一方newやmallocなどで確保するメモリの領域をヒープ領域という

グローバル変数が配置される領域を静的領域という

スタック領域はプログラム起動時に一括で確保されるため拡張できない

スタック領域に限界があるので、関数を再帰する回数にも限界がある、大体数万回ぐらい

通常グローバル領域は嫌われるが、コンテストのプログラムでは関数がそれほど多くない上、いろいろな関数から１つの配列にアクセスすることが多いので、グローバル変数を利用すると便利

巨大な配列を確保するときも、スタック領域におくより静的領域においた方がスタックオーバーフローする危険性が減る

最大サイズの配列で定義するときにも少し大きめに確保するとよい

2-2 猛追突進！貪欲法

・硬貨の問題

・区間スケジューリング問題

選べる仕事の中で、終了時間が最も早いものを選ぶことを繰り返すのが正しい

・column「貪欲法のアルゴリズムの証明」

直感的には終了時間が早ければ早いほど、その後に選べる仕事が多くなるからということになる

1 他の任意の選び方に対し、開始時間が早いものから同じ個数のところで終了時間が遅くない

2 よって多く選べる選び方は存在しない

1は帰納法、2は背理法で証明できる

・辞書順最小の問題

辞書順を扱う問題では貪欲法が効果的

普通にやれば良いと思うが、先頭と末尾のアルファベットが同じときに注意

SとSを反転させた文字列を辞書順比較する

・Saruman’s Army

一番左の点から距離Rいないで最も遠い点に印をつけていけば良い

・Fence Repair

コストは、いたの長さ * 節点の深さなので、一番短い板とその次の板を兄弟とすれば良い

これを繰り返す

優先度付きキューを使えば、NlogNでできそう

・column「ハフマン符号」

このアルゴリズムはハフマン符号を作るアルゴリズムである

文字によって文章に出現する頻度が異なるため、頻度の高いものに短い列を割り当てるのが良い

このアルゴリズムを、板を文字に、長さを頻度に置き換えて適用する

2-3 値を覚えて再利用 動的計画法

・01ナップサック問題

・column「memsetによる初期化」

memsetは1byte単位でメモリ領域を埋めるものだが、-1は全てのビットが1なので0と同様にOK、1はダメ

・column「全探索の書き方」

枝刈り探索を行うような場合には関数の引数にそこまでのコストを含めて書いても良いが、今回はうまくメモ化ができなくなるので注意が必要

・column「初期化忘れに注意」

グローバル変数は0で初期化されているので、上のコードは大丈夫だったが、一度の実行で複数の入力を処理するような場合には最初に初期化を行う必要がある

・column「いろいろなDP」

漸化式を変えると上記とは別のDPテーブルの埋め方になる

・最長共通部分列問題

・個数制限なしナップサック問題

・01ナップサック問題2

・個数制限付き部分和問題

・最長増加部分列問題

・分割数

・重複組み合わせ

2-4 データを工夫して記憶するデータ構造

・木・二分木

・プライオリティキューとヒープ

・二分探索木

・Union-Find木

2-5 あれもこれも実はグラフ

・グラフとは

・グラフの表現

・グラフの探索

・最短路問題

・最小全域木

・応用問題

2-6 数学的な問題を解くコツ

・ユークリッドの互除法

・素数に関するアルゴリズム

・余の計算

・冪乗を高速に計算

2-7 GCJの問題に挑戦(1)

・Minimum Scalar Product

貪欲でやるだけ

・Crazy Rows

下三角行列を作る

これも貪欲でやるだけ

・Bribe the Prisoners

DP

・Millionaire

全探索するアルゴリズムからDP

---中級編---

3-1 値の探索だけじゃない二分探索

・ソート列から値を探す

・解を仮定し可能か判定

・最小値の最大化

・平均最大化

3-2 厳選！頻出テクニック

・しゃくとり法

・反転

・弾性衝突

・半分全列挙

・座標圧縮

3-3 様々なデータ構造

・セグメント木

・Binary Indexed Tree

・バケット法と平方分割

3-4 DPを極める！

・ビットDP

・行列累乗

・データ構造を用いて高速化

3-5 水を流して問題を解くネットワークフロー

・最大流

・最小カット

・二部マッチング

・一般マッチング

・マッチング、辺カバー、安定集合、点カバー

・最小費用流

・応用問題

3-6 平面・空間を扱う計算幾何

・幾何の基本

・ギリギリを考える

・平面走査

・凸包

・数値積分

3-7 GCJの問題に挑戦(2)

・Numbers

受験数学の問題

漸化式を使って計算量を落とす

・No Cheating

最大安定集合の問題に帰着できる

・Stock Charts

グラフを考える

最大マッチングの問題に帰着できる

・Watering Plants

・Number Sets

・Wifi Towers

---上級編---

4-1 より複雑な数学的問題

・行列

・mod

・数え上げ

・対称性のある数え上げ

4-2 ゲームの必勝法を編みだせ

・ゲームと必勝法

・Nim

・Grundy数

4-3 グラフマスターへの道

・強連結成分分解

・2-SAT

・LCA

4-4 厳選！頻出テクニック(2)

・スタックの利用

・デックの利用

・ダブリング

4-5 工夫を凝らして賢く探索

・枝刈り

・A*とIDA*

4-6 分けて解いてまとめる 分割統治法

・列の分割統治法

・文字列検索

・接尾辞配列

4-7 文字列を綺麗に扱う

4-8 GCJの問題に挑戦(3)

・Mine Layer

・Year of More Code Jam

・Football Team

・Endless Knight

・The year of Code Jam

---扱わなかったテクニック---

グラフ・組み合わせ最適化

・オイラー閉路

・最小有向木

・最小シュタイナー木

・関節点、橋

・全域最小カット

・単体法

・マトロイド

数値計算

・三分探索、黄金分割法

・Karatsuba法、FFT

数論

・離散対数

・スターンブロコット木

探索

・α-β探索

データ構造

・平衡二分探索木

・Leftist Tree, Skew Heap

・Heavy-Light Decomposition

文字列アルゴリズム

・KMP法、Aho-Corasick法

・Manacherのアルゴリズム

・構文解析