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

シェアする

  • このエントリーをはてなブックマークに追加

フォローする