[AtCoder]AtCoder Beginner Contest 154を解いてみた[Ruby]

プログラミング

AtCoder Beginner Contest 154のA~Dまでを解いてみました。C問題まではサクサクいけましたが、D問題がとても難しく苦労しました、、、。

コンテストページはhttps://atcoder.jp/contests/abc154になります。

ABC154A – Remaining Balls

問題

文字列Sの書かれたボールがA個、文字列Tの書かれたボールがB個あります。
高橋君は、文字列Uの書かれたボールを1個選んで捨てました。
文字列S,Tの書かれたボールがそれぞれ何個残っているか求めてください。

自分の回答

def balls(s, t, a, b, u)
  if s == u
    a = a - 1
  elsif t == u
    b = b - 1
  end
  puts "#{a} #{b}"
end

s, t = gets.chomp.split(" ")
a, b = gets.chomp.split(" ").map(&:to_i)
u = gets.chomp
balls(s, t, a, b, u)

文字列uが文字列sと等しければ、aの個数が一つ減り、文字列uが文字列tと等しければ、bの個数が一つ減ります。

ABC154B – I miss you…

問題

文字列Sが与えられます。Sのすべての文字をxで置き換えて出力してください。

自分の回答

def miss(word)
  puts word.gsub(/./, 'x') 
end

word = gets.chomp
miss(word)

gsubメソッドを使って任意の文字をxに変換しています。正規表現で、.(ピリオド)が任意の一文字と言う意味になります。

ABC154C – Distinct or Not

問題

整数列A1,A2,…,ANが与えられます。 この整数列のどの2つの要素も互いに異なるならばYESを、そうでないならNOを出力してください。

自分の回答

def distinct(numbers, n)
  puts n == numbers.uniq.count ? "YES" : "NO"
end

n = gets.chomp.to_i
numbers = gets.chomp.split(" ").map(&:to_i)
distinct(numbers, n)

与えられた配列の中に数字の被りがなければ”YES”、あったら”NO”を出力します。

単に数字の被りがあるかどうかを確認するだけなので、簡単にできます。

最初に与えられた数字の個数nと配列からuniqで重複を取り除いた後の配列の個数が同じかどうかを判別すれば簡単に求められます。

例
n = 6
numbers = [4, 1, 3, 1, 6, 2]

1が重複しているので、numbers.uniq!とすると

numbers = [4, 1, 3, 6, 2]

となり、配列の個数が減ります。なので、この場合、nとnumbersの個数が違うので、答えは"NO"となります。
まとめると、最初の配列の個数nとuniqメソッドをかけた後の配列の個数とを比較すれば、良いです。

ABC154D – Dice in Line

問題

N個のサイコロが左から右に一列に並べてあります。左からi番目のサイコロは1からpiまでのpi種類の目がそれぞれ等確率で出ます。

隣接するK個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

自分の回答(誤)

まずは、不正解例からみていきましょう。

def dice(n, k ,dices)
  expects = 0
  i = 0
  max = 0
  
  # サイコロの目の種類の合計を求める
  while i <= n - k do
    sum = dices[0..k-1].inject(:+)
    if sum > max
      max = sum
      dices_max = dices[0..k-1]
    end
    dices.shift
    i = i + 1
  end

　#  期待値の合計を求める
  dices_max.each do |num|
    expects += ((1 + num)/2.to_f)
  end
  puts expects
end
 
n, k = gets.chomp.split(" ").map(&:to_i)
dices = gets.chomp.split(" ").map(&:to_i)
dice(n, k ,dices)

簡単に説明しますと、与えられたサイコロの配列(dices)を0番目からk番目まで足して、sumに入れます。その時のサイコロの組み合わせをdices_maxとします。
その後、先頭の一文字消して、また0番目からk番目まで足してを繰り返します。最後に、一番種類の多い組み合わせの期待値の合計を求めて終了です。

これでも、正しい値は出るのですが、計算に時間がかかりすぎて、実行時間超過となってしまいます。なので、計算の仕方を時間のかからないように変えなければなりません。

自分の回答

def dice(n, k ,dices)
  i = 0
  max = 0
  expects = 0
  sum = dices[0..k-1].inject(:+)
  dices_first = dices[0..k - 1]
  
　# サイコロの目の種類の合計を求める
  while i < n - k do
    sum = sum - dices[i] + dices[i + k]
    if sum > max
      max = sum
      dices_first = dices[i + 1..i + k]
    end
    i = i + 1
  end

　#  期待値の合計を求める
  dices_first.each do |num|
    expects += ((1 + num)/2.to_f)
  end
  puts expects
end

n, k = gets.chomp.split(" ").map(&:to_i)
dices = gets.chomp.split(" ").map(&:to_i)
dice(n, k ,dices)

変えたところは、サイコロの種類の合計を求めるところです。最初はそれぞれk個のサイコロの種類の合計を計算していました。しかし、それだとkが大きくなった時にとても時間がかかってしまいます。

なので、i番目からi+k-1番目のサイコロの種類の合計を求めたら、その値からi番目のサイコロの種類の値を引いて、i+k番目のサイコロの種類の値を足すように変更しました。文字だとよくわからないと思うので、下の図を参考にしてください。

これで、実行時間超過を回避して、正解となりました。累積和を利用したこの方法は他でも使いそうなので、覚えておいた方がいいですね。

もう一つのポイントは期待値を最後に求めているところです。

最初にそれぞれの期待値を求めてから、期待値の合計が最大となるサイコロの組み合わせを求めてもいいのですが、期待値はサイコロの目の種類の値に比例します。つまり、サイコロの目の種類が大きければ大きいほど期待値も大きくなります。なので、サイコロの目の種類の値が大きい組み合わせを求めた後に、そのサイコロの組み合わせの期待値の合計を求めた方が計算が少なくなる気がします。

タイトルとURLをコピーしました