「 2019年01月 」一覧

【書評】Amazon Web Services実践入門

AWSに関する本で2冊目に読みました。

全体的にAWSの概要をサクッと知るのに良い本だと思います。

向いている人

  • インフラの知識が一通りあり、AWSの全体像を短時間でおさえたい人

書かれていること

AWSにおける基本的な機能である、VPC、サブネット、ルートテーブル、EC2、NATなどの知識が一通り学べます。

内容は章ごとに分かれていて、EC2、VPC、Route53、S3、CloudFront、RDS、ELB、AutoScaling、CloudWatch、Billingからなります。

各章は機能の概要とGUIでの操作手順、CLIでの操作手順について一通り説明されています。

ただし、発行されたのが2015年なので所々情報が古いところがあるので、その点は注意する必要があります。(例:RDSは起動と削除しか出来ず停止が出来ない、など)

特にCLIなんかは結構仕様が変わりやすいので、正確な情報は公式のリファレンスを見た方がよいですね。自分はCLIの部分はほぼ読み飛ばしてしまいました。

書かれていないこと

インフラの知識がある程度あることが前提になっているので、サブネットって何?とかDNSってどういう仕組みになってるの?みたいなことは説明されません。

また、実際の利用を前提とした設計パターンのようなものもあまり触れられていないので、そういったことを知りたい人は別の書籍をあたるほうがよいです。

まとめ

AWSの全体像をさくっと知りたい、という人にはよくまとまっていていい本だと思います。

出来れば最新の情報にアップデートした版も出して欲しいところですね。

まあ、クラウドの世界は進歩が早いから最新の情報を知るには公式を当たるほうが手っ取り早いですが、そのための基礎知識をつける意味でもいい本だと思いました。


ABC088

A – Infinite Coins

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

1円玉には制限があり、500円玉は無制限。
なので、500円玉で払える分は最大限支払い、残りを持っている1円で払えるかを判断すればよいです。

よって、Nを500で割った余りが1円の所持枚数A以下であればYes、そうでなければNoとなります。

実装

N=gets.to_i
puts N % 500 <= gets.to_i ? "Yes" : "No"

B – Card Game for Two

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

  • AliceとBobは交互にカードを選ぶ
  • それぞれ自分の得点を最大化するように最適な戦略を取る

ということは、AliceもBobも残っているカードのうち大きい数字からとっていくことになります。

よって、カードを降順にソートすれば、(0インデックスで)偶数番目をAlice、奇数番目をBobが選ぶことになります。

実装

Aliceの点数 – Bobの点数なので、解としては偶数番目は加算、奇数番目は減算すればよいです。

gets
a=gets.chomp.split.map(&:to_i).sort.reverse
ans=0
a.each_with_index do |v, i|
  ans += i.even? ? v : -v
end
puts ans

C – March

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

300点にしてはちょっと難しかったです。

cとa、bの関係を表すと以下のようになります。

$$
\begin{pmatrix} c_{1,1} & c_{1,2} & c_{1,3} \\
c_{2,1} & c_{2,2} & c_{2,3} \\
c_{3,1} & c_{3,2} & c_{3,3} \end{pmatrix} =
\begin{pmatrix} a_1+b_1 & a_1+b_2 & a_1+b_3 \\
a_2+b_1 & a_2+b_2 & a_2+b_3 \\
a_3+b_1 & a_3+b_2 & a_3+b_3 \end{pmatrix}
$$

ここで、条件を満たす (a1,a2,a3,b1,b2,b3)が存在すると仮定すると、aにxを足したものとbからxを引いたものも、つまり、(a1+x,a2+x,a3+x,b1-x,b2-x,b3-x)も条件を満たすことがわかります。(上の式に当てはめてみるとわかります)

よって、xを調整すれば、a1が0のパターンもあり得ることになります。

よって、a1を0としたときの残りのを求めることができます。

求まった数について、求めるのに使った式以外の式を満たすかどうか判定し、矛盾すればNo、問題無ければYesとなります。

実装

c=[]
3.times { c<< gets.chomp.split.map(&:to_i) }
a = [0]
b = c[0]
1.upto(2) {|i| a[i] = c[i][0] - b[0]}

1.upto(2) do |i|
  1.upto(2) do |j|
    if c[i][j] != a[i] + b[j]
      puts "No"
      exit
    end
  end
end

puts "Yes"

D – Grid Repainting

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

迷路の探索問題の応用でとけます。

まず最初に(1,1)から(H,W)までの最短経路を深さ優先探索などで解きます。

そして、最短経路以外の白マスは黒に変えてしまって良いので、(最初の白マスの数 – 最短経路のマス数)を求めれば良いです。

実装

実装のポイントとして、マスの境界値の判断ロジックをシンプルにするために、事前に外枠を黒マスで囲んでおきます。

H,W=gets.chomp.split.map(&:to_i)
s = []
s << ['#'] * (W+2)
H.times { s << ['#'] + gets.chomp.split("") + ['#']}
s << ['#'] * (W+2)

d = Array.new(H+2).map{Array.new(W+2,Float::INFINITY)}

def dfs(s, d, i, j, c)
  return if s[i][j] == '#'
  return if d[i][j] <= c

  d[i][j] = c
  dfs(s,d,i,j+1,c+1)
  dfs(s,d,i,j-1,c+1)
  dfs(s,d,i+1,j,c+1)
  dfs(s,d,i-1,j,c+1)
end

dfs(s, d, 1, 1, 1)

if d[H][W] == Float::INFINITY
  puts -1
else
  ans = 0
  s.each {|ss| ans += ss.count('.')}
  puts ans - d[H][W]
end

ABC089

A – Grouping 2

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「3人以上のグループを出来るだけ多く作る」なので、解は\(\lfloor N/3 \rfloor\)になる。

実装

puts gets.to_i/3

B – Grouping 2

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

「桃色、白色、緑色の3種類」or「桃色、白色、緑色、黄色の4種類」なので、黄色(Y)が1つでもあれば4種類、そうでなければ3種類となる。

実装

gets
a=gets.chomp.split(" ")
puts a.include?('Y') ? "Four" : "Three"

C – March

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

組み合わせの条件は以下の2つです。

  • 全ての人の名前が M,A,R,C,H のどれかから始まっている
  • 同じ文字から始まる名前を持つ人が複数いない

1つ目の条件より、入力のうちM,A,R,C,Hで始まらないものは無視して良いことがわかります。

2つ目の条件より、3人の組み合わせとして有効なのは、

(Mで始まる人、Aで始まる人、Rで始まる人)
(Mで始まる人、Aで始まる人、Cで始まる人)
  :
のような組み合わせになります。

ここで、例えば(Mで始まる人、Aで始まる人、Rで始まる人)の組み合わせの数は、

Mで始まる人の人数 x Aで始まる人の人数 x Rで始まる人の人数

で求めることが出来ます。

よって、最初に以下の5つの数を計算しておき、そこから3つを取り出した時の組み合わせ毎にその積をとって、その総和を出せば解になります。

  • Mで始まる人の人数
  • Aで始まる人の人数
  • Rで始まる人の人数
  • Cで始まる人の人数
  • Hで始まる人の人数

実装

rubyで組み合わせを求める場合、配列のcombinationを使うと簡単です。

N=gets.to_i
h=Hash.new(0)
N.times do
  s = gets.chomp
  h[s[0]] += 1 if s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H'
end

ans = 0
h.values.combination(3) do |l,m,n|
  ans += l*m*n
end
puts ans

D – Practical Skill Test

問題

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

LからRへDずつ移動した際の距離の総和を求める問題です。

L、Rは最大9万なので、距離を求めるのが1回であれば、Dずつ移動しながら移動距離の総和を出せば良いです。

しかしながら、与えられるL、Rの組み合わせの数Qは最大105なので、都度Dずつ移動しながら距離を計算するのは時間がかかりすぎます。

よって、L、Rが与えられた時に定数時間で移動距離を出す方法を考える必要があります。

考え方のポイントとしては、Dは常に一定である、という点です。

例えば入力例1のように、Aが1〜9でDが2である場合、移動パターンは以下の2種類しかありません。

  • 1 → 3 → 5 → 7 → 9
  • 2 → 4 → 6 → 8

よって、奇数の場合は1からの累積距離、偶数の場合は2からの累積距離、を事前に求めておくことで、任意の点間の移動距離を定数時間で求めることが出来ます。

例えば、例1の4から8の場合は、(2から8の累積距離)-(2から4の累積距離) を計算すれば、4から8への移動距離を求めることが出来ます。

実装

H,W,D=gets.chomp.split.map(&:to_i)
p = Array.new(H*W+1)
H.times do |i|
  gets.chomp.split.map(&:to_i).each_with_index do |v,j|
    p[v] = [i,j]
  end
end

d = [0] * (D+1)
(D+1).upto(H*W) do |i|
  d[i] = d[i-D] + (p[i][0] - p[i-D][0]).abs + (p[i][1] - p[i-D][1]).abs
end

Q=gets.to_i
Q.times do
  l,r = gets.chomp.split.map(&:to_i)
  puts d[r] - d[l]
end