AOJ - DSL_1_A (Union-Find) を解いてみた
DSL_1_Aは、Coursera Algorithm I で最近習ったばかりのUnion-Findです
AOJ - DSL_1_A
互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge
quick find で求めてみる
時間切れでアウトです
- 授業でも言われてましたが、quick-findは要素の更新を行う操作がどうしても遅いのです
id.collect! { |element|
(element == updated) ? updating : element
}
quick-unionで求めてみる
これだと余裕で解けました。
追記 2018/07/11
- 嘘です、07:93秒もかかってるので使い物になりません。。。
quick-unionのミソは、unionにしてもfindの操作にしてもどちらの場合でも最初に木構造の最上位を求めることだと思われます。(それをしないと、配列上で複数の親をもつ構造が表現できない)
# coding: utf-8 class QuickUnion attr :id def initialize(n) @id = (0...n).to_a end def root(i) while i != @id[i] do i = @id[i] end i end # find, check if p and q has the same root def same?(p, q) root(p) == root(q) end # union, to merge components containing p and q # set id of p's root to the id of q's root def unite(p, q) i = root(p) j = root(q) @id[i] = j end end lines = $stdin.read array = lines.split("\n") n = array[0].split(" ")[0].to_i q = array[0].split(" ")[1].to_i un = QuickUnion.new(n) for i in 1..q com = array[i].split(" ")[0] x = array[i].split(" ")[1].to_i y = array[i].split(" ")[2].to_i if com == '0' # unite(4,3) id[4] = 3, 4の頭を3にする un.unite(x, y) else # same puts un.same?(x, y) ? "1" : "0" end end
しかしやっぱりRubyは使いやすい
計算量の削減 O(α(N))
経路圧縮とrankの実装を行うことで処理時間をO(α(N))まで削減できます。
・00:22秒で終了しました。これでようやくAtCoderで使えるレベル
# coding: utf-8 class UnionFind attr :id, :rank def initialize(n) @id = (0..n).to_a @rank = Array.new(n,0) end def root(i) if @id[i] == i or i == @id[@id[i]] i else @id[i] = root(@id[i]) @id[i] end end # find, check if p and q has the same root def same?(p, q) root(p) == root(q) end # union, to merge components containing p and q # set id of p's root to the id of q's root def unite(p, q) i = root(p) j = root(q) return if i == j if @rank[i] < @rank[j] @id[i] = j else @id[j] = i; @rank[i]+=1 if @rank[i] == @rank[j] end end end lines = $stdin.read array = lines.split("\n") n = array[0].split(" ")[0].to_i q = array[0].split(" ")[1].to_i un = UnionFind.new(n) for i in 1..q com = array[i].split(" ")[0] x = array[i].split(" ")[1].to_i y = array[i].split(" ")[2].to_i if com == '0' # unite(4,3) id[4] = 3, 4の頭を3にする un.unite(x, y) else # same puts un.same?(x, y) ? "1" : "0" end end
AOJ - ITP1_7_D (行列の積) を解いてみた
ITP1_7_Dは、今自分の中でブームの行列の積の問題です。生で計算しないにしても、機械学習にも大いに関係があります。
AOJ - ITP1_7_D
Matrix Multiplication | Aizu Online Judge
自分の回答
行列の積をプログラムに起こすと?
もし自分がJavaで行列計算をするのであれば、JAMA: Java Matrix Package を使う気がします。JAMAは見た感じちゃんとオブジェクト指向的な気がします。ちなみにJavaの行列計算は全体的にパフォーマンス悪めっぽいので実際の大規模データには向かないかもしれません。
問題の内容
問題自体は2つの行列を単純に掛け算するのみです。インプットの例は以下、
1:数値n, m, lが与えられる
3 2 3
2:行列 A[n][m] が与えられる、縦の数がn, 横の数がm
1 2 0 3 4 5
3:行列 b[m][l] が与えられる、縦の数がm, 横の数がl
1 2 1 0 3 2
問題の解法
手計算だとわかるのですが、これをプログラム化するのに結構苦戦しました。
行列計算の参考リンク
行列同士を掛け算すると、外側の要素が答えの要素になります。
[行列の積]
●[m×n型][n×p型]=[m×p型]
積が定義されるためには,左の列数と右の行数が等しくなければなりません。結果は,[m×p型]となります。
なので、解答を保持する行列C = A*bとおくと、
4:行列 C[n][l] を0で初期化する
0 0 0 0 0 0 0 0 0
5:行列 C[n][l] を変数i,j,kを使って埋めます。
変数は以下の範囲で動きます、が最初は行列Cの出来上がりの構造を考えたほうがいいでしょう。
- 0 <= i < n
- 0 <= j < m
- 0 <= k < l
AOJ - ITP1_7_B (組み合わせ) を解いてみた
偉そうに書いてるが、これは序の口の問題である。。。
AOJ - ITP1_7_B
How many ways? | Aizu Online Judge
自分の回答
解法1 algorithm - Finding all possible combinations of numbers to reach a given sum - Stack Overflow
愚直な手順(ナイーブな解法とか煽られるやつ)
アルゴリズム
This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:
この問題は全ての和の組み合わせを再帰的に解き、目標の数に一致したもの以外をフィルタリングすることで解くことができます。
処理フロー
引数に対象の数列N、目標X、部分配列Pをとる関数subset_sumを作成する
- subset_sumに初期値N、X、空の部分配列を入れて開始
- この時点での合計値 S = 配列Xの合計値 で計算する
- S=Xかどうか検査
- S==X であれば、その部分配列Pを記録して4へ進む
- S>=X ならば、プログラム終了
- S<Xであれば4へ進む
- 数列Nの長さiを取得してループを開始、i = 0 〜 iまで以下を繰り返す
- n = 数列Nのi番目の要素とおく
- 配列R = Nのi+1番目以降の全ての要素とおく
- 配列TR = 配列P の末尾に n を連結したものとおく
- 関数subset_sumに引数としてR, X, TR を渡して実行
結果
メモリ制限に引っかかる…これではダメです…でも一応nCrの組み合わせの出し方は書いておく → Javaで簡単な組み合わせの総数 nCr を求めてみる - なんとな~くしあわせ?の日記
解法2 Given an array A[] and a number x, check for pair in A[] with sum as x - GeeksforGeeks
2つのアルゴリズムを使う
- 配列Aと数値xが与えられた時、その和がxになる配列A内の組み合わせ(ペア)をチェックする
- 数値xが2より大きくなった場合
アルゴリズムA
Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.
時間計算量:これは我々がどのようなソートアルゴリズムを使っているかによる。マージソートやヒープソートをつかっている場合最悪でも (-)(nlogn) となる。クイックソートをつかっている場合は、最悪でも O(n^2) になる。
Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.
空間計算量:これも、我々がどのようなソートアルゴリズムを使っているかによる。例えば空間計算量はマージソートならばO(n)、ヒープソートならばO(1)になる。
処理フロー
引数に対象の数列A、配列サイズar_size、その和sumをとる関数hasArrayTwoCandidatesを作成する
- 配列Aを昇順でソートする
- ソートされた配列の中の要素から候補を見つけるために、2つのインデックス用の変数を初期化する
- 1つ目の変数を、最左端の値で初期化する: L = 0
- 2つ目の変数を、最右端の値で初期化する: R = ar_size - 1
- L < R の間これを繰り返す ( while L < R )
- もし A[L] + A[R] == sum ならば、1を返す
- もし A[L] + A[R] < sum ならば、Lをインクリメント、L++
- それ以外は Rをデクリメント、R--
- 配列全てから候補が見つからなければ、0を返す
アルゴリズムB
This method works in O(n) time if range of numbers is known.
この手法は数値の範囲が既知のものであればO(n)で動作する
処理フロー
和は与えられた和で、配列Aは我々が見つけたいペアとなる(?)
- 2分木の連想配列を初期化する M[] = {0, 0, 0...}
- 配列A[]の中にある、各々のA[i]に対して以下を実行
- もし M[x - A[i]] がセットされていれば A[i], x - A[i] を出力
- M[A[i]] をセットする
アルゴリズムC
処理の流れとしては、Cを走らせてから先ほどのアルゴリズムAかBを内部で使用する。
We have discussed a O(n^3) algorithm in the previous post on this topic. The problem can be solved in O(n^2Logn) time with the help of auxiliary space.
先に我々は、AとBのアルゴリズムでこれがO(n^3)で動作することを議論した。この問題は空間計算量の助けによりO(n^2 log n)で解ける
処理フロー
対象の数列をAとする
- 補助用の配列auxを作成する、そして全ての求めるべき和の可能性のあるペアをそこに格納する。auxのサイズは n が 配列Aのサイズとすると、 n*(n-1)/2になる
- 補助用の配列aux[]をソートする
- 今やXに等しいなんらかの数値の組み合わせの和を配列auxから見つける問題は簡単化された。その2つの要素を能率的に見つけるにはアルゴリズムAが使えるだろう。
ここには以下のような特筆すべきポイントがある
- 配列aux は 配列Aから抽出したペアを表している。配列auxから2つの要素を選ぶ一方で、その2つの要素が一般に配列Aの中にあるかどうかをチェックする必要がある
- 例えば、A[1]とA[2]の和が最初の要素だとして、A[2]とA[4]の和が次の要素だとすると、これは配列Aの中から抽出した4要素を持った配列ということにはならない
結果
アルゴリズムAとCを使用してやることで普通に解けた。
- 解法1
- ターゲットの配列が1〜100まであったとき、そこから全ての組み合わせを求めると161700になってしまう、そこから更に計算して合計値が100になるのを探すのは効率が悪すぎる
- 解法2
- 求めるべき要素3つのうち1つを決め撃ちして、残り二つを配列から挟み撃ちの形で求めているので早い