■
Problem
Solution
This problem can be solve by DFS with depth of tree. In my code, lists.size() == depth means that the traversing depth changes.
Source Code
Maximum Product of Word Lengths
Problem
Solution
This problem can be solved effectively by using bit manipulation. We can manage the count of appearance of each letters. Lower case letters are transformed to Integer within 26. This takes 0(N2) time.
Source Code
AWSにおける可用性を向上するパターンをまとめる
クラウドにおける可用性とは
「可用性(Availability)」とはシステムが継続して稼働できる能力の事。システムを稼働しているサーバーや、データを保存しておくデータベースが１つで設計されている場合、その１つが落ちた場合にシステムが止まってしまう。これは可用性の低い設計である。設計者はサーバーやデータセンタが落ちることを想定して、可用性の高い設計をする必要がある。
参考
カテゴリ:CDP:可用性を向上するパターン - AWS-CloudDesignPattern
Multi-Serverパターン
Multi-Serverとは、仮想サーバー(EC2)を複数台ならべELB(ロードバランサー)によって適宜不可を振り分けることである。ELBにはヘルスチェック機能が備わっているので、１つのサーバーが止まった場合は、そのサーバーには処理を振り分けずに健康なサーバーのみに処理を振り分ける。これによって１つのサバーが落ちても、システムを仮想し続けることができる。
注意点
EBLと複数のEC2を使用するので、単一よりもコストがかかる
Multi-Datacenterパターン
AWSは複数のデータセンターを保持している。Multi-Datacenterパターンは複数のデータセンターにサーバーを構築しておくことで、１つのデータセンターが障害が起きた場合でも、システムを稼働し続ける事ができる。これもMulti-Serverパターンと同様にELBが処理を振り分けてくれる。
Deep Health Checkパターン
ロードバランサーやDNSはヘルスチェック機能が備わってるが、基本的にはチェック出来る範囲は直接紐付いているサーバーのみである。 Deep Health Checkは直接紐付いているサーバーだけではなく、もっと奥深くのサーバーもチェックし、そのステータスをロードバランサーやDNSに返してシステム全体のヘルスチェックを行うものである。
システムはDNS→Webサーバー→Proxyサーバー(代わりにアプリケーションリクエストを送るためのサーバー。直接リクエストを送らずにProxyサーバーをはさむのでセキュリティ面で恩恵がある)→アプリケーション・サーバー→データベースといくつものサーバをはさむ事がある。その全てのサーバーに対してヘルスチェックを行う事ができる。
Floating IPパターン
使用しているサーバーが止まった場合、マシンイメージを用いて仮想サーバーを新たに高速に作り、その仮想サーバーにEIPを付け替えることでシステムを稼働し続けることができる。EIPを付け替える操作もAPIが用意されているので自動化することができる。
Routing-Based HAパターン
続く。
配列における３つの要素の和
Problem
与えられた配列において、任意の３点の和がゼロとなる組合せを全て取得する問題。
Solution
この問題は以下のように解くことができる。
- 任意の３点をstart, middle, endと置く(start < middle < end)
- startを固定し、
middle = start + 1,end = arr.length - 1と置く - 上記により３点が決まるので、３点の和を計算し
sと置く s == sumならば、その要素達をリストに追加。この時、middle++,end--する。- 更新したmiddleとendがそれぞれ前回と同じ値ならば、更に
middle++,end--する。こうすることで重複を除く事ができる。 - 4, 5を(middle < end)が成り立つ間繰り返す。
- 以上の処理をstartを0 → arr.length - 3 まで行う。
コレによる計算量はO(N2)となる。
Source Code
AtCoder ABC D - Mixing Experiment
問題
D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder
解き方
全列挙を考える
全列挙する場合、i番目の薬品を購入する場合としない場合を２パターンをN回行うので、計算量はO(2N)となりNは最大40なので間に合わない。
動的計画法を使う
dp(i, x, y)を以下のように定義する。
dp(i, x, y) := {i番目までの薬を使用した時、物質aの和がx, bの和がyとなる、最小コスト}
漸化式を立てる
dp(i, x, y)は漸化式を用いて次のように表す事ができる。
dp(i, x, y) = min(dp(i - 1, x, y), dp(i - 1, x - a[i], y - b[i]) + cost[i])
後は配列のインデックスがOutOfRangeしないようにfor文を回してあげる。するとi に N - 1 を代入したdp[N - 1][x][y]は、全ての薬品を考慮した時のx, yのコストを取得することができる。あとは、与えられた比となるx, yを見ていき最小コストを出力してあげる。
ソースコード
ビット操作を用いて順列を求める
どの部分の要素を既に使用したかをbitを用いて管理する
