Akihito Ikeda

AtCoder Beginner Contest 131

posts/2019-06-24diary

解ける問題だけ解きました🤯😇🤯

A - Security

実際に連続しているかどうか判定すればいい🍻

これはなんの面白みもないコード

s = gets.strip

now = ''
ans = 'Good'
s.split('').each do |i|
    if now == i
        ans = 'Bad'
    end
    now = i
end

puts ans

each_consという便利なメソッドを使ってみたやつ

s = gets.strip

ans = 'Good'
s.chars.each_cons(2) do |a, b|
  ans = 'Bad' if a == b
end

puts ans

こっちはsqueezeで連続する文字を圧縮したあと長さを比べて判定してみたやつ

s = gets.strip

if s.size != s.squeeze.size
    puts 'Bad'
else
    puts 'Good'
end

このなかだとeach_consのやつが好き🍻

B - Bite Eating

総和から絶対値が最小のものを除けばよい🍻

n, l = gets.strip.split.map(&:to_i)

apples = n.times.map { |i| l + i }
sum = apples.inject(:+)
min = apples.min_by { |a| a.abs }

puts sum - min

C - Anti-Division

まず$$1 ≤ A ≤ B ≤ 10 ^{18}$$なので、
AからBまでの数をひとつずつ実際にCとDで割ってみるような全探索はムリ🐌

例えば1から10までの整数の中で、2でも3でも割り切れないものを考えてみる。
2でも3でも割り切れない $$=$$ 2と3の倍数ではない」ということなので、
2と3の倍数の数がわかれば、2と3の倍数でないものの数もわかる。

気をつけないといけないのは、2と3の倍数を除く時、最小公倍数である6の倍数が一回多く除かれてしまうこと。

  • 2の倍数 => 2, 4, 6, 8, 10
  • 3の倍数 => 3, 6, 9

10個 - (2の倍数 = 2, 4, 6, 8, 10 = 5個) - (3の倍数 = 3, 6, 9 = 3個) = 2個
となってしまう。 なので余計に引いてしまった最小公倍数の倍数の分を足さないといけない。

この辺りはベン図を描いてみればよくわかる(面倒なので描かない)

つまり、
答え = 全体 - cの倍数の数 - dの倍数の数 + cとdの最小公倍数の倍数の数 となる🍻

Rubyでは最小公倍数がx.lcm(y)で求められるので感動的に便利。
ちなみに最大公約数を求めるにはx.gcd(y)がある。

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

all = b - a + 1
c_mul = b / c - (a - 1) / c  # cの倍数の数
d_mul = b / d - (a - 1) / d  # dの倍数の数
lcm = c.lcm(d) # cとdの最小公倍数
lcm_mul = b / lcm - (a - 1) / lcm # cとdの最小公倍数の倍数の数

puts all - c_mul - d_mul + lcm_mul

D - Megalomania

直感的に「〆切が近いものからやっていけば良さそう」と思って提出したら通った。
証明はわかんない🍻

n = gets.strip.to_i
ab = n.times.map { gets.strip.split.map(&:to_i) }

ab = ab.sort_by { |a, b| b }

now = 0
ans = 'Yes'
ab.each do |a, b|
    now += a
    if b < now
        ans = 'No'
        break
    end
end

puts ans

E, F

力尽きた。仕事後にこの辺りの問題をやるのはたいへーん🍻
でもこの辺りをやってかないと伸びないしなーうーん。
ランチ時に集まってやるのがやはり良さそう🍛

© Akihito Ikeda - Last update 26.11.2020 00:01.