なんとな~くしあわせ?の日記

ClojureとかAWSの設定とかをメモする技術ブログ

AOJ - ALDS1_7_A, B, C を解いてみた

勝手に解いてろとか言わないで…

ALDS1_7_A, B, Cは、木構造(根付き木、二分木)です

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge
二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

木構造を使うときの基本

まあ、木構造単体でプログラミングコンテストの問題が出されることはほとんど無さそうなのですが…*1

  • とりあえず、構造体 or クラスで以下のような型を作る
  • 木構造の1要素を1つのNodeというクラスで表現します。中には親要素のid、左と右の要素のidを持ちます。
  • Rubyの場合はStructを使うと楽にそういうのが作れる、Generics無しにそれを配列型にできるし
Node = Struct.new(:parent, :left, :right)
nodes = Array.new(N) { Node.new }

ALDS1_7_A - 根付き木

1つの節(ノード)に複数の子がくっつく場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_children ( id, nodes )

その接点の直下の子ノードを求める

ALDS1_7_B - 二分木

1つの節(ノード)に2つの子しかつかない場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_height ( id, nodes )

その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree - Stack Overflow)

get_sibling ( id, nodes )

その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか2択になる

ALDS1_7_C - 木の巡回

木の巡回には3種類あるという話。

  • 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
  • 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
  • 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

自分の回答

用意した関数を紹介しておく

pre_parse ( root, nodes )

根節点、左部分木、右部分木の順で節点の番号を出力する

in_parse ( root, nodes )

左部分木、根節点、右部分木の順で節点の番号を出力する

post_parse ( root, nodes )

左部分木、右部分木、根節点の順で節点の番号を出力する

使用例?

単純な木構造って、実務でも競プロでも使うことが稀な気がする。すごい単純なデータが問題で、なおかつ階層がキーになる場合に使えばいいのかな?いい問題があれば追記します。

*1:木構造よりも、それの発展系のグラフアルゴリズムの出題が多そう

アルゴリズム学びフローを作成してみる

AOJの本

この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…

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

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

本の内容とレビュー

知識ゼロからはじめてもわかるように、アルゴリズムがだいたい順番に問題とともに紹介されている。昔paizaでA問題が解けないと悩んでいたが、それはこの本に載っているような、計算量を減らすためのアルゴリズムが組めていないことが原因であったと思う。

書籍の中ではAOJの例題が一緒に載っているので、文章を読んで理解した後に問題を実際に解いて腕試しすることができる。

見通しを立ててみる

書籍の中では、「このアルゴリズムを学んだら、次はこれに進めます」という情報が書いてある。ちょっとその情報をdraw.ioというサービスで絵にしてみた。(こういう風に、構造化していけば雑然とした概念がまとまるかなあという願望…)

図を書いていて思ったこと。

  • 業務プログラミングでは、緑の線を出るか出ないかぐらいの知識しか使わない
  • 自分は木構造とグラフと動的計画法の知識が足りない感じなので、そこをマスターしていく必要がある

高解像度版

f:id:panzer-jagdironscrap1:20170706000220p:plain

プロコンで解いた問題を格納

今日は何か新しいことをやる気力が無くなったので、今まで解いた問題のコードを格納するリポジトリを作ってみた

github.com

動的計画法で組み合わせの総数 nCr を求めてみる

もっと早い組み合わせの総数 (combination)の求め方

動的計画法 - DP(Dynamic Programming)

最近AtCoderの問題をちょろちょろ見ているのですが、その中でいわゆるDP(Dynamic Programming)が勝負の鍵を握っているということがわかりました。組み合わせの求め方についてはいろいろやってきましたが、以下の方法では巨大な組み合わせを算出すると時間がかかってしまいます。

nantonaku-shiawase.hatenablog.com
nantonaku-shiawase.hatenablog.com

Combinationのための動的計画法

英語圏のサイトだとDP自体ちゃんと体系化されているっぽいので、以下のサイトからアルゴリズムを学び、やり方を汎化してみます。

www.csegeek.com

Rubyによるサンプルプログラム
  • 要は2次元配列にnCrの答えを予め用意しておき、後で使う時は添字アクセスするのだ
def choose(n, r)
  1 if r == 0 or r == n

  # store C(n,r) in a matrix
  c = Array.new(n+1).map{Array.new(r+1,0)}
  i,j = 0

  for i in 0..n
    # C(i,0) = 1 for i = 0...n
    c[i][0] = 1
  end
  for j in 0..r
    # if n = 0, C(n,r) = 0 for all 'r'
    c[0][j] = 0
  end

  for i in 1..n
    for j in 1..r
      if i == j
        # C(n,n) = 1
        c[i][j] = 1
      elsif j > i
        # case when r > n in C(n,r)
        c[i][j] = 0
      else
        # apply the standard recursive formula
        c[i][j] = c[i-1][j-1] + c[i-1][j]
      end
    end
  end

  return c[n][r]
end

n = 5
r = 2
comb = choose(n,r)

puts "C (#{n},#{r}) = #{comb}"
処理内容を表で表現してみる
  • nCr , n = 3, r = 2 を求める

1. 行 n、列 r の格子を考える

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
(3,0) (3,1) (3,2)

2. C(i,0) = 1 for i = 0...n

(0,0) = 1 (0,1) (0,2)
(1,0) = 1 (1,1) (1,2)
(2,0) = 1 (2,1) (2,2)
(3,0) = 1 (3,1) (3,2)

3. if n = 0, C(n,r) = 0 for all r

(0,0) = 0 (0,1) = 0 (0,2) = 0
(1,0) = 1 (1,1) (1,2)
(2,0) = 1 (2,1) (2,2)
(3,0) = 1 (3,1) (3,2)

4. j と i、それぞれ 1から最大値まで

  • i == j であれば、1を設定(初期値っぽい)
  • j > i であれば、0を設定(計算に関係ないから)

それ以外は

  • c[i][j] = c[i-1][j-1] + c[i-1][j]
    • 斜め左上のセルと上のセルを合計したものがそのセルの値

(0,0) = 0 (0,1) = 0 (0,2) = 0
(1,0) = 1 (1,1) = 1 (1,2) = 0
(2,0) = 1 (2,1) = 2 (2,2) = 1
(3,0) = 1 (3,1) = 3 (3,2) = 3

実際使う時は

  • nCr の NとRについては、固定値で先にすべての場合を求めておく方がよさそう