下のようなコードで変数dsが保持しているDataSetのメモリが解放されないといいう問題が起きました。 for (int i = 0; i <= n; i++) { TestDataSet ds = this.GetFromDB(i); foreach (TestDataSet.DataRow row in ds.DataTable) { this.Calc(row.id, row.amou…

今回のお題はこちら 辺をコストの低い順に並べて、辺の始点と終点が同じ木に属していなければ辺を取り入れるというアルゴリズム。これは簡単ですな。 require 'union_find_tree' V = 10 #input E = 10 #input $edges = Array.new(E, Hash.new) #input 辺の始…

今回のお題はこちら お題に書いてある通りコスト最小の辺とその辺で到達できる頂点を一つずつ加えていき、最小全域木を求める方法です。 INF = 2 ** 30 V = 10 #input $cost = Array.new( V ).map!{ Array.new( V, 0 ) } #input $used = Array.new(V, false)…

今回のお題はこちら。 $costに各頂点間のコストをいれれば全点対最短路が計算できます。 実装が簡単なのがいいですな。 V = 10 #input $cost[V][V] #input def warshall_floyd for k in 0..(V - 1) for i in 0..(V - 1) for j in 0..(V - 1) $cost[i][j] = […

今回のお題はこちら。 今回も$costが適切に初期化されていませんが、アルゴリズムはあってます。 INF = 2 ** 30 V = 10 $cost = Array.new( V ).map!{ Array.new( V, INF ) } $d = Array.new(V, INF) $used = Array.new(V, false) def dijkstra(s) d[s] = 0 …

今回のお題はこちら。 横着して$edgeに入力値を代入してないですが、アルゴリズムはあってます。 V = 7 #input E = 10 #input $edges = Array.new #input INF = 2 ** 30 $d = Array.new(V, INF) #各頂点への最短距離 while true update = false for i in 0..…

今回のお題はこちら。 DFSにも大分なれてきました。 $graph = Array.new(4).map!{ Array.new() } $graph[0].push(1) $graph[0].push(3) $graph[1].push(0) $graph[1].push(2) $graph[2].push(1) $graph[2].push(3) $graph[3].push(0) $graph[3].push(2) $col…

今回のお題はこちら。 union find treeも一緒に実装しました。 このデータ構造初めて知ったなぁ。 class UnionFindTree attr_accessor :parent, :rank def initialize(n) @parent = Array.new @rank = Array.new for i in 0..(n - 1) @parent.push(i) rank.p…

今回のお題はこちら。 これも発想の転換によって簡単に解けるようになる問題ですな。 Rubyには組み込みクラスでプライオリティキューが用意されていないようなのでArrayを使って実装しました。 が、これだと計算量がO(N^2logN)になるので不正解です。 自前で…

今回のお題はこちら。 漸化式中のΣを取り除く式変形が難しいですな。 $m = 3 #input A = [1, 2, 3] #input M = 10000 #input $dp = Array.new( A.length + 1 ).map!{ Array.new( $m + 1, 0 ) } for i in 0..A.length $dp[i][0] = 1 end for i in 0..(A.lengt…

今回のお題はこちら 漸化式の立て方がいまいちわからない。。実行結果がおかしいけど、先に進みたいので今時点のプログラムを載せます。 require 'pp' N = 4 #input M = 3 #input Lm = 10000 #input $dp = Array.new( M + 1 ).map!{ Array.new( N + 1, 0 ) }…

今回のお題はこちら A = [4,2,3,1,5] #input $dp = Array.new(A.length, 1) for i in 0..(A.length - 1) for j in 0..i $dp[i] = [$dp[i], $dp[j] + 1].max if A[i] > A[j] end end puts $dp.max

今回のお題はこちら 漸化式思いつかないよ。。精進あるのみですな。 MaxK = 17 A = [3, 5, 8] M = [3, 2, 2] $dp = Array.new( MaxK + 1, -1) $dp[0] = 0 for i in 0..(A.length - 1) for j in 0..MaxK if $dp[j] >= 0 $dp[j] = M[i] elsif j < A[i] || $dp[…

今回のお題はこちら 重さと価値を入れ替えるというのが思いつきませんでした。。 W = [2,1,3,2] #input V = [3,2,4,2] #input maxWeight = 5 #input MaxV = 100 MaxN = 100 INF = 2**29 $dp = Array.new( W.length + 1 ).map!{ Array.new( MaxV * MaxN + 1, …

今回のお題はこちら。 問題から漸化式をぱっと作れるようになりたいですなー。 require 'pp' S = "abcd" #input T = "becd" #input $dp = Array.new( S.length + 1 ).map!{ Array.new( T.length + 1, 0 ) } S.split('').each_with_index do |s, i| T.split('…

前回のお題を再帰を使わずループを使って書き直してみました。 こっちの方がわかりやすいですな。 W = [2,1,3,2] #input V = [3,2,4,2] #input maxWeight = 5 #input $dp = Array.new( W.length ).map!{ Array.new( maxWeight + 1, 0 ) } (W.length - 1).dow…

今回のお題はこちら。 今回はdp用メモテーブル$dpのサイズを間違えて不具合になりました。 ナップサックに入れられる重さは0〜wなので、 配列のサイズはwじゃなくてw+1にしないといけないんですなー。 W = [2,1,3,2] #input V = [3,2,4,2] #input w = 5 #inp…

今回のお題はこちら。 この問題解いてて知ったんだけど、変数の値の入れ替えを↓のように書けるのはかなり嬉しいですね。 a,b = b,a 入れ替え以外にも複数の代入文を一つにまとめるとわかりやすくなる場合がありました。 これは今後も使っていきたい。 L = [8…

今回のお題はこちら。 Rubyはeach_with_indexとかselectとかmapとか、配列に便利なメソッドが揃ってていいですね。 R = 10 #input X = [1, 7, 15, 20, 30, 50] #input $covered = Array.new(X.length, 0) count = 0 for i in 0..(X.length - 1) if $covered[…

よく考えたらコールスタックサイズはコールスタックに割り当てられているメモリサイズによって決まるんじゃないか？と思ったので再度実験しました。 コールスタックにはリターンアドレスとローカル変数が納められているので前回のコードを以下のように修正し…

前回のコードを書いていてコールスタックの最大サイズが気になったので調べてみました。 検索しても出てこなかったので自分で以下のコードを実行してみました。 $i = 0 def test() puts $i $i += 1 test() end test() 結果、「21628」まで出力したところで「…

今回のお題はこちら。 本の回答例で先頭と末尾の文字のどちらをtに移すか判定するところをforループを使って処理していましたが、再帰を使って書いてみました。 こっちの方がすっきりしてていいですね。 あーでもInputの文字数が2000文字までだから、コール…

今回のお題はこちら。 Rubyってint型の最大値って組み込み型の定数で定義されてたりしないんでしょうか。 C#のint.MaxValueみたいに。 後、Rubyでインクリメント演算子が使えないことにちょっとビックリしました。まぁ無くてもいいけど。。 startTimes = [1,…

今回のお題はこちら。 A = 620 #input c500 = 2 #input c100 = 0 #input c50 = 3 #input c10 = 1 #input c5 = 2 #input c1 = 3 #input coins = [[c500, 500], [c100, 100], [c50, 50], [c10, 10], [c5, 5], [c1, 1]] leftMoney = A paidNumOfCoins = 0 coins…