ごっそログ

勉強したことなどを書いていきます

「プログラミングコンテストチャレンジブック」を読んだ (第1章～第2章)

技術書 アルゴリズム データ構造

アルゴリズム、データ構造の勉強がてら、「プログラミングコンテストチャレンジブック」の1、2章を読んだ。
7億年前に基本情報の勉強をしていた時に感じていた、結局のところこれ何に使うねん的な疑問が少し解消された気がする。(グラフとか)
2-3 動的計画法の漸化式の部分、2-5 グラフの利用例は難しく結構大雑把な理解になってしまったので、手を動かしながらもう一度読み返したい。
1,2章のプログラミング例の実装を真似て理解を深めるか、続きを読み進めるか悩んでいる。

以下要約

第1章 準備編

オーダー

  • 計算量は「何に比例するか」で考え、それをアルゴリズムのオーダーと呼ぶ。

    • 例えばn回のループが4重になっていればO(n4)と表す

  • 実行時間制限に収まるかどうかを調べるためには、オーダーの式に最大値を代入すればよい

二分探索

  • 一度に候補の場所が半分になり、計算量はO(log n)(対数時間と呼ぶ)

第2章 初級編

2-1　全探索

全探索

再帰関数

  • 再帰呼び出しは計算に時間がかかる
    →呼び出し回数が指数的に広がるため

  • 引数を渡した際の結果が一定の場合、1回計算したら配列等にメモしておくことで高速化できる(メモ化 、後述)

スタックとキュー

  • push (積む) と pop (取出す) という二つの操作ができる

  • スタックはLIFO、キューはFIFO

深さ優先探索 (Depth-First Search, DFS)

  • ある状態から始め、遷移できなくまで状態を進め、遷移できなくなったら１つ前に戻る
    →再帰関数で簡単に書けることが多い

幅優先探索 (Breadth-First Search, BFS)

  • DFSと同じくある状態から始めてたどり着けるすべての状態を探索する。

  • はじめの状態に近いほうから検索する
    →最短経路・最短手数 を求めるのに適している

  • 同じ状態は一度しか通らないので計算量は O(状態数 * 遷移の仕方)

枝刈り

  • それ以上状態を遷移しても解が存在しないことが明らかな場合に
    それ以上探索せず打ち切ることを枝刈りという。

    • (ex) 合計がkとなる数の組み合わせを探す問題で途中で合計がkを超えてしまったとき、それ以上の探索は不要。

2-2　貪欲法

  • ルールに従ってその場での最善を繰り返すアルゴリズム設計技法

  • アルゴリズムが正しければシンプルかつ高速になることが多い

  • 間違ったアルゴリズムを選ばないような注意が必要

  • 辞書順比較を扱う問題などで有効なことが多い

2-3　動的計画法 (Dynamic Programming, DP)

ナップサック問題

  • 重さと価値をw, vとするn個の品物があるとき、
    重さの総和がWを超えないように選んだ時のvの総和の最大値を求める

  • 各品物を入れる or 入れないで分岐しながら探索する愚直な方法ではO(2n)の時間がかかる

    • この探索法には「i番目以降から重さがj以下になるように選ぶ」という探索を
      同じ引数に対して何度も行っているという問題がある

    • 最初の計算時に結果を記録することで、2回目以降の計算を省略できる (メモ化)

  • ナップサック問題等におけるメモ化テーブルの値は漸化式になっている

    • 再帰関数を書かなくても漸化式を直接用いて各項の値を検索することで、式がすっきりする

2-4　データ構造

  • 「ヒープ」「二部探索木」「Union-Find木」を扱う。

定義

  • 丸(○)をノード または節点と呼ぶ
  • 線(ー)を辺 と呼ぶ
  • ここで扱う木は 「根」 と呼ばれるノードを最も上に一つ持つ
  • 各ノードはデータと、「子」 のノードを持つ
  • 自身を「子」として持つノードを 「親」 と呼ぶ
  • 親が同じノードを「兄弟」と呼ぶ
  • 子を持たないノードを「葉」と呼ぶ

ヒープ

  • 二分木

    • 全てのノードについて子が2個以下である木

  • 順位キュー (プライオリティーキュー)

    • 次の操作ができるデータ構造
      • 数を追加する
      • 最小の数値を取り出す (値を取得し削除する)

  • ヒープ とは

    • プライオリティーキューの操作を二分木を用いて効率的に実現するデータ構造

  • ヒープの仕組み

    • 必ず子の数字は親の数字より大きい
    • 上から下へ、左から右へ順にノードが詰まっている

  • ヒープの計算量

    • 追加、最小値取り出しの操作には木の深さに比例した時間がかかる (つまりO(log n) )

二分探索木

  • 二分探索木 は次のような操作が効率的に行えるデータ構造である

    • 数値を追加する
    • ある数値が含まれているか調べる
    • ある数値を削除する

  • 二分探索木の仕組み

    • 左の子以下の数はすべて自分の数より小さく、
      右の子以下の数はすべて自分の数より大きくなるように管理する

  • 数の探索

    • 根から子に向かって、大きければ右、小さければ左と進んでいけば見つかる

  • 数の追加

    • 根から子に向かって数の探索と同様に進めば本来あるべき場所がわかるので、そこに追加する

  • 数の削除

    • 削除したいノードが左の子を持っていなければ右の子を持ってくる
    • 削除したいノードの左の子が右の子を持っていなければ左の子を持ってくる
    • どちらでもなければ、左の子以下で最大のノードを削除したいノードの位置に持ってくる

Union-Find木

  • グループ分けを管理するデータ構造。以下の操作が行える

    • 要素aと要素bが同じグループに属すかどうか調べる
    • 要素aと要素bのグループを併合する

  • Union-Find木も木を使って表現され、1つの木が1つのグループを表す

    • ただし二分木とは限らないし、親子関係も重要ではない

  • 併合

    • 片方の木の根からもう片方の木の根に辺を張る

  • 判定

    • 要素aと要素bが同じグループに属すかどうか調べるには、木の根を見る
      同じ根にたどり着けば同一グループとみなすことができる

  • 実装時の注意

    • 木のデータに偏りが発生すれば計算量が膨大になってしまう
      →そのため、偏りが発生しないような工夫が必要となる
      • 併合の際、高さの低いものを高いものの根に張る
      • 縮約

  • Union-Find木の計算量

    • 上記の工夫を行えば非常に高速

2-5　グラフ

グラフの定義

  • 頂点 と 辺 からなる。

  • 頂点は「対象」、辺は「対象どうしの結びつき」を表す

  • 頂点の集合V、辺の集合EからなるグラフをG(V, E)と表す

  • 2点u, vを結ぶ辺をe(u, v)と表す

グラフの種類

  • 有向グラフ … 辺に向きがあるグラフ
  • 無向グラフ … 辺に向きがないグラフ

重み

  • 辺には様々な属性がつくことがあり、代表的なものに重みがある。

無向グラフの用語

  • 2頂点の間に辺があるとき、2つの頂点は「隣接している」という

  • 隣接している頂点の列をパスという

  • 始点と終点が同じパスを閉路という

  • 任意の2頂点間にパスが存在するグラフを連結グラフという

  • 頂点につながっている辺の数をその頂点の次数という

  • 閉路を持たない連結グラフを「木」という

    • 木は辺の数が頂点数 - 1になる

  • 連結でないグラフで閉路を持たないものを「森」という

有効グラフの用語

  • 有効グラフで閉路を持たないものを「DAG (Directed Acyclic Graph)」という

    • DAGの頂点の間には順序関係を与えることができる

  • 各頂点に番号を付け、頂点viからvjに向かって辺があるとき、i < jが成り立つような番号の付け方を
    トポロジカル順序という

  • トポロジカル順序に従い頂点を左から右に並び替えると(トポロジカルソート)全ての辺は左から右に向かう

    • このような順序をつけることでDAGの問題をDPを用いて解けるようになることがある。

グラフの表現

  • グラフをデータとして表現する方法に、「隣接行列」「隣接リスト」がある

隣接行列

  • 頂点の個数 * 頂点の個数の二次元配列gでグラフを表現する。

無向グラフの場合

  • 「頂点iと頂点jが結ばれているか？」という情報で事足りる
    →結ばれていればg[i][j]、g[j][i]の値を1にすればいい

有向グラフの場合

  • 「頂点iから頂点jに向かう辺があるか？」という情報があればよい
    →向かう辺があれば二次元配列g[i][j]の値を1にする
    • 無効グラフのケースと違い、g[i][j] = g[j][i]とは限らない

重み付きグラフの場合

  • g[i][j]の値を辺の重みにする
    辺がないときは十分に大きな定数INFを定義し、g[i][j] = INFとする

隣接行列の欠点

  • 常にO(頂点の個数 ^ 2)のメモリを消費する
  • 多重辺や自己ループがある場合の表現が難しい

隣接リスト

  • 「隣接する頂点のリスト」を持つことでグラフを表現する
  • O(頂点の個数 + 辺の個数)のメモリしか消費しない

グラフの利用例

  • グラフの彩色問題
  • 最短路問題 (頻出)

  • 単一始点最短路問題 (ベルマンフォード法)

    • 始点を固定したときに他の全ての頂点との間の最短路を求める問題

  • 単一始点最短路問題 (ダイクストラ法)

  • 全点対最短路問題 (ワーシャル-フロイド法)
  • 経路復元
  • 最小全域木

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

ユークリッドの互除法

概要

  • 最大公約数を求めるアルゴリズム
  • 自然数a, bの最大公約数を求める関数をgcd(a, b)とすると、
    gcd(a, b) = gcd(b, a % b)が成り立つ

ユークリッドの互除法の計算量

  • O(log max(a, b))

素数判定

  • 整数nの約数はn未満なので、2～n-1までの整数で割り切れるかどうかを試せば素数かどうか判定できる
    ここでnが約数dを持ったとするとn/dもnの約数なので、min(d, n/d) <= √n
    よって2～√nまでの整数を試すだけで十分である
  • 同様に素因数分解、約数列挙もO(√n)で行える

エラトステネスの篩(ふるい)

概要

  • 多くの整数を素数判定する際に用いる

  • 2以上n以下の整数をすべて書き出すと、その中の最小である2は素数である
    →2の倍数をすべて取り除くと、残りの中で最小である3は素数である
    →3の倍数をすべて取り除くと、残りの中で最小であるmは素数である
    →mの倍数をすべて取り除くと…　という操作を繰り返し素数を列挙する

エラトステネスの篩の計算量

  • O(log log n)程度

べき乗を高速に計算する

  • 繰り返し二乗法

2-7

  • 問題集なので省略