アルゴリズム学びフローを作成してみる
AOJの本
この本を買ってみた。プログラミングコンテスト攻略のためのアルゴリズムとデータ構造…
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (6件) を見る
本の内容とレビュー
知識ゼロからはじめてもわかるように、アルゴリズムがだいたい順番に問題とともに紹介されている。昔paizaでA問題が解けないと悩んでいたが、それはこの本に載っているような、計算量を減らすためのアルゴリズムが組めていないことが原因であったと思う。
書籍の中ではAOJの例題が一緒に載っているので、文章を読んで理解した後に問題を実際に解いて腕試しすることができる。
動的計画法で組み合わせの総数 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側に証明書もたせる設定もできそうだし、そのほうがいいのかねえ…