【AtCoder:8回目】AtCoder Beginner Contest 131の振り返り（Ruby）

【目次】

【本題】

振り返り

今回は 6/16(日)に開催されたAtCoder Beginner Contest 131の振り返りを行います。

AtCoder Beginner Contest 131 - AtCoder

今回も２問までです。

３問目が解けそうに思えたのですが、途中のテストで躓いてしまいました・・・

いっそ全部テスト落ちてくれていた方が解決策も探しやすいのですが、公開されていないテストの一部だけで躓いているとなると、何が原因なのか特定が非常に難しいです・・・

レーティングは微増です。

A - Security

問題文 すぬけ君の管理する研究室の扉にはロックがかかっており、解錠にはセキュリティコードを入力する必要があります。

セキュリティコードは 4 桁の数字列です。セキュリティコードが「入力しづらい」とは、同じ数字が連続する箇所が存在することを言います。

現在のセキュリティコード S が与えられます。 S が「入力しづらい」なら Bad を、そうでなければ Good を出力してください。

制約 S は半角数字のみからなる長さ 4 の文字列

文字列を一文字づつ分割して、前後の文字列が同一なのか比較する方法でコードを実装しました。結構力技です・・・

s = gets.chomp.split("")
 
sss = ''
ssss = ''
s.each do |ss|
  ssss = 'Bad' if ss == sss
  sss = ss
end
 
if ssss == 'Bad'
  puts 'Bad'
else
  puts 'Good'
end

案の定もっと良い方法がありました。

puts gets.chomp.squeeze.size == 4 ? "Good" : "Bad"

squeezeメソッドは、文字列中で同じ文字が連続している部分を1つの文字にまとめ、新しい文字列を返します。

新しい文字列が4文字であれば、"Good"で、それ以外は"Bad"を出力するという方法です。

B - Bite Eating

問題文 N 個のリンゴがあります。これらはそれぞれリンゴ 1 、リンゴ 2 、リンゴ 3 、...、リンゴ N と呼ばれており、リンゴ i の「味」は L + i − 1 です。「味」は負になることもありえます。

また、 1 個以上のリンゴを材料として、アップルパイをつくることができます。その「味」は、材料となったリンゴの「味」の総和となります。

あなたはこれらのリンゴを全て材料として、アップルパイをつくる予定でしたが、おなかがすいたので 1 個だけ食べることにしました。勿論、食べてしまったリンゴはアップルパイの材料にはできません。

つくる予定だったアップルパイとできるだけ同じものをつくりたいので、 N 個のリンゴ全てを材料としてできるアップルパイの「味」と、食べていない N − 1 個のリンゴを材料としてできるアップルパイの「味」の差の絶対値ができるだけ小さくなるように、食べるリンゴを選ぶことにしました。

このようにして選ばれたリンゴを食べた時、食べていない N − 1 個のリンゴを材料としてできるアップルパイの「味」を求めてください。

なお、この値は一意に定まることが証明できます。

制約 2 ≦ N ≦ 200 − 100 ≦ L ≦ 100 入力は全て整数である。

とりあえずリンゴ一つ一つの味を配列に格納して、それらの絶対値を個別に比較して、最小の配列の位置を特定し、それと合計を引くという手法で実装しました。

力技だと分かりながらも、他の方法を実践していると時間が経過してしまいから、そのまま力技で実装してしまわざる得ないのが辛いところ・・・

 n,l=gets.split.map &:to_i
 
eat = []
n.times do |i|
  eat << (l + i)
end
 
ee = eat[0].abs
num = 0
eat.each_with_index do |e,i|
  if e.abs < ee
    ee = e.abs
    num = i
  end
end
 
sum = 0
eat.each { |i| sum += i }
 
puts sum - eat[num]

こちらも案の定、もっと良い実装方法がありました。

N, L = gets.split.map &:to_i
a = [*L...L+N]
p a.inject(:+) - a.min_by(&:abs)

味は連番になるので、範囲オブジェクトで定義して、inject(:+)で合計値を出しています。

min_byメソッドは、ブロックの戻り値が最小値となる要素を返すので、(&:abs)を指定する事で、絶対値の最小を抽出できます。

C - Anti-Division

問題文 整数 A , B , C , D が与えられます。 A 以上 B 以下の整数のうち、 C でも D でも割り切れないものの個数を求めてください。

制約 1 ≤ A ≤ B ≤ 10 18 1 ≤ C , D ≤ 10 9 入力はすべて整数である

はじめに下記の全通りの実装を試しましたが、パターンが膨大になるので、これだと処理時間オーバーになってしまいました。

a,b,c,d=gets.split.map &:to_i

range = Range.new(a,b)

num = 0
range.each do |i|
  num +=1 if i % c != 0 && i % d != 0
end

puts num

次に試したのは、下記の実装です。

まず、あるxとyという整数があった場合、xをyで割った時の商が、0~xの数字の中で、yで割り切れる数の個数になるという考え方をベースとしました。

なので、aとbを、それぞれcとdで割って、割り切れる個数を求めます。

なお、cとdで共通して割り切れる数も存在する事が想定される為、cとdの最小公約数でも割って、その個数も求めます。

最終的に、cとdで割った数の合計から、最小公約数で割った数を引けば、cとdのどちらかで割り切れる数の個数が導き出せます。

aとbの両方でこの計算をしたのは、0~bの結果と0~aの結果を引く事で、a~bの結果を抽出できるからです。

なお、今回はa以上という条件なので、a自体も割り切れる数の対象に含まれています。なので、aがc・dのいずれかで丁度割り切れる場合は、a自身の個数が商に含まれないので、+1する必要があります。

その結果、出来上がったのが下記のコードです。

a,b,c,d=gets.split.map &:to_i
a_c = a/c
a_d = a/d
a_cd = a/(c.lcm(d))
b_c = b/c
b_d = b/d
b_cd = b/(c.lcm(d))

sum = (b_c + b_d - b_cd) - (a_c + a_d - a_cd)
sum += 1 if a % c == 0
sum += 1 if a % d == 0
sums = b-a+1
puts sums-sum

しかし、こちらのコードだと一部のテストが通らず、原因不明のまま、時間が経過してしまいました・・・

ただ、よくよく見返すと、sum += 1は一回で良いのに、二度処理を記述していたのが原因だと分かりました。

なので下記の様にコードを修正すると、正常に通りました。勿体無い事をした・・・

a,b,c,d=gets.split.map &:to_i
a_c = a/c
a_d = a/d
a_cd = a/(c.lcm(d))
b_c = b/c
b_d = b/d
b_cd = b/(c.lcm(d))

sum = (b_c + b_d - b_cd) - (a_c + a_d - a_cd)
sum += 1 if a % c == 0 || a % d == 0
sums = b-a+1
puts sums-sum