ALDS_11_A Graphを解く話

グラフの表現の理解を問う問題である.

隣接リスト表現から隣接行列表現へ変換する処理を実装する.

隣接リスト表現(Adjacency List)

・有限グラフを表現するためのリスト
・1つのリストが1つの頂点に対応して,隣接するノードが接続

隣接行列表現(Adjacency Matrix)

・有限グラフを表現するための行列
・行列の各要素は頂点のペアが隣接しているか否かを示す.

以下のサイトで,グラフと辺をいじったり行列とリストを確認できる.

https://visualgo.net/graphds

 

実装

入力は
 頂点番号u 出次数k uに隣接する頂点v_1, v_2, ..., v_k
の形式で与えられる.

u = 1\ to\ nを行番号, j = 1\ to\ kを列番号にする.
頂点のペアに対して1は辺あり,0は辺なしで隣接行列 m_{uj}に代入.

gist6e33ed8e2c8bdb6f8de899f271efe4f7

 

感想

シンプルなのでかなり簡単な問題.

ALDS1_8-A Binary Search Tree Iを解く話

根付き木,二分木に続いて二分探索木を実装する.

二分探索木(Binary Search Tree)

・内部接点はが {キー,左部部分木, 右部分木} を持つような根付き木.

・二分探索木条件(Binary search tree property)を満たす木.

 二分探索木条件: 左部分木の根 <= キー <= 右部部分木の根

 

特徴

・二分探索木に中間順巡回を行うと,昇順に並んだキーが得られる.

・連結リストのように動的にキーの挿入,削除が可能.

 

挿入操作の実装

・ノード同士はポインタで接続

・各ノード: {キー,左部分木のルートへのポインタ,右部分木のルートへのポインタ}

・挿入するキーは葉になる.

・最初のループでxを挿入する位置z(現在葉の子)まで移動

・xはNILなのでxの親yをいじってzをつなぐ.

・yがNILのときzはrootにする.

 

計算量

木の高さh回キーの比較をする.ノード数がnのとき,h = log_2(n)なので計算量はO(log_2(n)).バランスの悪い木ではノード数だけ比較をするので計算量がO(n)になることに注意.

 

実装

gist75c6237289e9f10b588a26566640136c

 

 感想

 実装をする前に必要な時間を見積もるようにしている.短時間で実装できるようになる事も目標だが,自分の実装力を客観的に測定できる事も必要である.まだ見積もり時間を越してしまうが,AOJ本を始めた頃に比べて精度は高くなっている.

ALDS1_7_B Binary Treeを解く話

二分木を実装させる問題である.

tooshitaka.hatenablog.com

とほとんど同じだ.

まず用語の整理からする.

二分木

・ノードの子の数が最大でも2である木.

・子は左,右と区別される.

ノードuの高さ

・木の最下段からuへのパスを考えたとき,通る辺の数.

ノードuの高さ計算

・ノードの深さ計算と類似.

・根から葉に向かって全てのノードを巡回.

・「子の高さ + 1」は自分の高さ,として再帰で計算.

アルゴリズム

  1. int setHeight(u)
  2.     int h1 = h2 = 0
  3.     if Tree[u].left != NIL
  4.         h1 = setHeight(Tree[u].left) + 1
  5.     if Tree[u].right != NIL
  6.         h2 = setHeight(Tree[u].right) + 1
  7.     return Max(h1,h2)

実装

gistfff80805ef0fcf4b269770b8ba2acfd2

感想

Decision Trees — OpenCV 2.4.13.2 documentation

A decision tree is a binary tree (tree where each non-leaf node has two child nodes).

 とある.基本的なデータ構造を勉強していると,具体的な応用例までをなかなか考えない.

決定木は二分木だということを覚えておく.

ALDS1_7_A Rooted Treesを解く話

入力を根付き木として保存する問題である.

ノードの深さ,種類(根,内部ノード,葉),深さも答えさせるのでそれぞれの概念の定義をきちんと理解する必要がある.

木(Tree)

・連結で閉路をもたないグラフ G = (Vertex, Edge)

・木について話すときは頂点(Vertex)をノード(Node)と言ったりする.

根付き木

・特別なノードである根(Root)を1つだけ持つ木.

多分木/N分木(Multi-way tree/ N-ary tree)

・3つ以上の子を持つノードが存在する木.

木に関する用語

・ノードuの親(Parent): uから根rに向かうパスの最初のエッジでuと繋がるノード.
・ノードuの深さ(Depth):根rからuにたどり着くまでの辺の数.
・根(Root):親を持たないノード.
・内部ノード(Internal node):親と子を持つノード.
・葉(Leaf):子を持たないノード.

左子右兄弟表現(Left-child right-sibling representation)

木構造の表現の1つ.
・多分木を2分木により表現.
・1つのノードを{親,最も左の子,最も近い右の兄弟}により表現.
・この表現を配列で管理して木全体を実装.

ノードの深さの計算

①素朴なやり方:ノードから根にたどり着くまでの辺を数える.

再帰を使ったやり方:

  1.  深さ0で根からスタート.

     2. 左子へ一段下がる.このとき深さをインクリメント.

     3. 同じ段の最も右の兄弟まで辿る.兄弟の深さは同じ.

     4. 2と3を最も左の葉にたどり着くまで繰り返す.

再帰で書くと

  1. calc_depth(node, depth)

  2.     Tree[node].d = depth

  3.     if Tree[node].child != NIL

  4.         calc_depth(Tree[node].child, depth++)

  5.     if Tree[node].sibling != NIL

  6.         calc_depth(Tree[node].sibling, depth)

実装

gist7ec757a5dfd1c569386c0d0bf956fe8d

感想

AOJ本を読んでいるときはスラスラ進むのだが,実装ではスムーズにいかず時間を取られる.cvpaper.challengeで有名な片岡さんの記事を思い出した.

片岡裕雄 技術メモ How to study "computer vision" (Kataoka style)

僕は「完璧に理解すれば実装はできる」と思っているので,実装する時には手法についてとことん理解度を高めるようにします.

 今回は論文手法うんぬん以前の基本的なデータ構造だが,やっていることは変わらないはず.本を読んだときは「なるほど」と納得するが実装で「?」になる.恐らく理解はしているのだが,それが「実装に足りる理解」ではなかったのだと思う.まずは自分の「実装に足りる理解度」を把握するのが目標である.

ALDS1_2 Bubble sortを解く話

そらで書けないと恥ずかしいバブルソートを実装する.

 

特徴

・「泡がぶくぶく...」という説明で有名

・ 配列の要素数が大きい場合は計算量が大きくなるので非実用的

 

アルゴリズム

  1. Bubblesort(A)
  2.     n = A.length
  3.     for i = 0 to n - 1
  4.         for j = n - 1 downto 1
  5.             if(A[j] < A[j - 1])
  6.                 swap(A[j], A[j - 1])

 

実装

gist14532d31250bad311cb0fd295619e621

 

計算量

最悪ケースでは外側のループが回るたびに, n - 1回,n - 2回,...., 1回の比較をする.
これらを全部足すとn ( n - 1 )  /  2回.なので計算量はO(n^2)

 

感想

バブルソートの問題は前に解いたのだが,今回ここに書くために改めて実装した.

ただ前回と違い,問題に記載してる疑似コードを見ないですぐに書けるようになっていた(内側のループをインクリメントで書くミスをしたが).

バブルソートなんぞ簡単な問題で」と言われてしまうかもしれないが,前回はAOJ本をほぼ写経するレベルだったので,自分の成長を確認できてうれしい.

 

ALDS1_6_A Counting sortを解く話

計数ソート(Counting sort)を実装する.

 

特徴

  • 配列の要素をキーとするソートアルゴリズム
  • キーを要素とする別の配列を用意して出現頻度と累積和を計算
  • 累積和から任意のキー以下の要素数がわかり,正しい位置に要素を代入

 

アルゴリズム

A: ソートする配列,B:ソート済みの配列,n: Aの要素数,k: キー(Aの要素)の最大値

  1. Countingsort(A, B, n, k)
  2.     C[K]
  3.  // 初期化
  4.     for i = 0 to k
  5.         C[i] = 0
  6.     // Aの要素の出現頻度を計算
  7.     for i = 0 to n
  8.         C[A[i]]++
  9.  // 累積和を計算
  10.     for i = 1 to k
  11.         C[i] = C[i] + C[i - 1]
  12.     // 累積和をもとにAの要素をBの正しい位置に代入
  13.     for i = n - 1 downto 0
  14.         B[C[A[i]]] = A[i]
  15.         C[A[i]]--

 

計算量

サイズ n 配列の走査とサイズk 配列の走査をするので計算量はO(n + k)

実装

gist26c42254b7044f831a5cac19840a2d07

 

感想

累積和をなぜ計算しているか理解するのに時間がかかった.自分の値以下の要素がいくつあるのかを知るのがポイント.それが分かると自分の位置がわかるのでソートできる.

色々調べてると計数ソートは基数ソートとかなり関係あるみたい.

www.opendatastructures.org

ただAOJには基数ソートないんだよなぁ.

ALDS1_6 Quick Sortを解く話

情報系の学生ならみんな知っているクイックソートを解く.

自分は学部時代にやったはずだが,まったく覚えていなかった.

 

特徴

  • 配列を分割統治でソートするアルゴリズム
  • 配列を2つに分割する際におおまかにソート(Partitionアルゴリズム
  • 分割した配列を引数にそれぞれ再帰的にQuicksortを呼び出し
  • 補助的な配列を必要としない(マージソートは必要)in-placeなアルゴリズム
  • Pivot(Partitionの閾値)の選び方によって様々な種類が存在.沼が深そうなので今回は配列の最後尾をPivotとするLomuto partition schemeを実装.

 

アルゴリズム

ALDS1_6-B Partitionを関数内で利用.

  1. Quicksort(A, l, r)
  2.     If l >= r
  3.         return
  4.     p = Partition(A, l, r)
  5.     Quicksort(A, l, p - 1)
  6.     Quicksort(A, p + 1, r)

 

 計算量

最悪ケースではPartitionに  O(n) 必要.また,配列の要素数 n のときPartitionでの2分割は O(log_2(n)) 回実行. よって全体の計算量は  O(nlog_2(n)).

 

実装

gistba1b8bbf64e8d297a504469b5b3f3c6b

 

感想

Partitionが理解できていれば問題なし.配列の最後尾をPivotとして選ぶのは今まで知らなかった.なんとなくクイックソートは真ん中で分割していくやつかー,とかずっと思ってた.