ABC162

https://atcoder.jp/contests/abc162
過去問。
　

A: Lucky 7

n = gets.chomp
puts n.include?("7") ? "Yes" : "No"

B: FizzBuzz Sum

n = gets.to_i
result = 0

(1..n).each do |i|
  next if i % 3 == 0 || i % 5 == 0
  result += i
end

puts result

C: Sum of gcd of Tuples (Easy)

とりあえずメモ化してみた。

def gcd(a, b, c)
  a.gcd(b).gcd(c)
end

k = gets.to_i
memo = {}
sum = 0

(1..k).each do |a|
  (1..k).each do |b|
    (1..k).each do |c|
      ary = [a, b, c].sort
      if memo[ary]
        sum += memo[ary]
      else
        n = gcd(a, b, c)
        memo[ary] = n
        sum += n
      end
    end
  end
end

puts sum

これでは全然ダメ。
少し工夫してみる。

k = gets.to_i
sum = 0

(1..k).each do |a|
  (a..k).each do |b|
    (b..k).each do |c|
      case
      when a == b && b == c
        sum += a
      when a == b
        sum += b.gcd(c) * 3
      when b == c
        sum += c.gcd(a) * 3
      when c == a
        sum += a.gcd(b) * 3
      else
        sum += a.gcd(b).gcd(c) * 6
      end
    end
  end
end

puts sum

これで 265ms で AC だった。
　

D: RGB Triplets

とりあえず単純にやってみる。

n = gets.to_i
s = gets.chomp

if n < 3
  puts 0
else
  count = 0
  (0...n).each do |i|
    (i + 1...n).each do |j|
      (j + 1...n).each do |k|
        next if j - i == k - j
        if s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
          count += 1
        end
      end
    end
  end
  puts count
end

これはあっさり TLE。
解説を見る。結構いいところまでいっていたようだった。

n = gets.to_i
s = gets.chomp

r = g = b = 0

s.each_char do |c|
  case c
  when "R" then r += 1
  when "G" then g += 1
  when "B" then b += 1
  end
end

result = r * g * b

(0...n).each do |i|
  (i + 1...n).each do |j|
    k = 2 * j - i
    next if k < 0 || k >= n
    if s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
      result -= 1
    end
  end
end

puts result

しかしこれも一つだけ TLE。ループを while 文に変更してみる。

n = gets.to_i
s = gets.chomp

result = s.count("R") * s.count("G") * s.count("B")

n.times do |i|
  j = i + 1
  while j < n
    k = 2 * j - i
    if j < k && k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i]
      result -= 1
    end
    j += 1
  end
end

puts result

1810ms で AC。小手先のテクニックだなあ。