A – Infinite Coins
問題
解法
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
問題
解法
- 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
問題
解法
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
問題
解法
迷路の探索問題の応用でとけます。
まず最初に(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
コメント