動的計画法で組み合わせの総数 nCr を求めてみる
もっと早い組み合わせの総数 (combination)の求め方
動的計画法 - DP(Dynamic Programming)
最近AtCoderの問題をちょろちょろ見ているのですが、その中でいわゆるDP(Dynamic Programming)が勝負の鍵を握っているということがわかりました。組み合わせの求め方についてはいろいろやってきましたが、以下の方法では巨大な組み合わせを算出すると時間がかかってしまいます。
nantonaku-shiawase.hatenablog.com
nantonaku-shiawase.hatenablog.com
Combinationのための動的計画法
英語圏のサイトだとDP自体ちゃんと体系化されているっぽいので、以下のサイトからアルゴリズムを学び、やり方を汎化してみます。
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については、固定値で先にすべての場合を求めておく方がよさそう
CloudflareとLet’s Encryptを同時に使ってると、Let’s Encryptが更新できない件
- tls: handshake failure
- There were too many requests of a given type :: Error creating new authz :: Too many invalid authorizations recently.. Skipping.
tls: handshake failure
Let's Encryptで更新かけるとき、こんなエラーログが出る
# cd /opt/letsencrypt/ # ./certbot-auto renew (省略) Attempting to renew cert from /etc/letsencrypt/renewal/freestylewiki.xyz.conf produced an unexpected error: Failed authorization procedure. freestylewiki.xyz (tls-sni-01): urn:acme:error:tls :: The server experienced a TLS error during domain verification :: remote error: tls: handshake failure. Skipping.
remote error: tls: handshake failure. で検索をかけると原因がわかった。
解決策
I had Cloudflare running on the site, once I paused it I could renew the certs.
Cloudflareを一時停止状態にすればよいらしい。助かった〜
Cloudflare側の設定
これ
- 一旦DevelopmentModeに変えて
- Pauseを押す
この後、certbot-auto renew を再実行するとうまく更新できた。
There were too many requests of a given type :: Error creating new authz :: Too many invalid authorizations recently.. Skipping.
何回もcertbot-auto renewしてたら、以下のようなわかりやすいエラーが出た。メンゴメンゴ。
Attempting to renew cert from /etc/letsencrypt/renewal/freestylewiki.xyz.conf produced an unexpected error: urn:acme:error:rateLimited :: There were too many requests of a given type :: Error creating new authz :: Too many invalid authorizations recently.. Skipping.
解決策
1時間だけ待つ
だるいな。
Cloudflare側に証明書もたせる設定もできそうだし、そのほうがいいのかねえ…
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