ABC179 - Marginalia

A: Plural Form

str = gets.chomp
puts str + (str[-1] == "s" ? "es" : "s")

B: Go to Jail

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

f = dice.each_cons(3).any? {|d1, d2, d3|
  d1[0] == d1[1] && d2[0] == d2[1] && d3[0] == d3[1]
}

puts f ? "Yes" : "No"

C: A x B + C

提出していないけれど、これはたぶん TLE。

require "prime"

n = gets.to_i

puts (1..n - 1).sum {|c|
  (n - c).prime_division.inject(1) {|acc, (a, b)| acc * (b + 1)}
}

できた。484ms。
総当りで、仮に a ≦ b とすれば、a は高々 √n 個で済む。

n = gets.to_i

x = Integer.sqrt(n)
ans = 0

(1..x).each do |a|
  (a..n / a).each do |b|
    c = n - a * b
    next if c < 1
    if a == b
      ans += 1
    else
      ans += 2
    end
  end
end

puts ans

上を圧縮。466ms。

n = gets.to_i

ans = 0

(1..Integer.sqrt(n)).each do |a|
  (a..n / a).each do |b|
    next if n - a * b < 1
    ans += (a == b) ? 1 : 2
  end
end

puts ans

さらに改良。64ms。わーい、いまのところ Ruby で最速！
b のループをせずに計算で済ませている。

n = gets.to_i

x = Integer.sqrt(n)
ans = 0

(1..x).each do |a|
  bn = n / a - a
  bn -= 1 if (n % a).zero?
  ans += bn * 2 + 1
end
ans += 1 if x * x == n

puts ans

D: Leaping Tak

TLEまちがいなし。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}

s = (1..n).select {|i|
  lrs.any? {|l, r| (l..r).cover?(i)}
}
count = 0

try = ->(x) {
  if x == n
    count += 1
  else
    s.each do |jump|
      nxt = x + jump
      break if nxt > n
      try.(nxt)
    end
  end
}
try.(1)

puts count % 998244353

TLEだが、悪くない。メモ化。でも、s をすべて求めているのがいけないのだな。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}

s = (1..n).select {|i|
  lrs.any? {|l, r| (l..r).cover?(i)}
}
memo = {}

try = ->(x) {
  return memo[x] if memo[x]
  count = 0
  s.each do |i|
    a = x + i
    if a > n
      break
    elsif a == n
      count += 1
    else
      count += try.(a)
    end
  end
  memo[x] = count
}

puts try.(1) % 998244353

公式解説の解法。わからんぞ。

n, k = gets.split.map(&:to_i)
lrs = k.times.map {gets.split.map(&:to_i)}.sort

MOD = 998244353

dp = Array.new(n, 0)
ans, dp[0], dp[1] = 0, 1, -1

(0...n).each do |i|
  ans = (ans + dp[i]) % MOD
  lrs.each do |l, r|
    break unless i + l < n
    dp[i + l] = (dp[i + l] + ans) % MOD
    next unless i + r + 1 < n
    dp[i + r + 1] = (dp[i + r + 1] - ans) % MOD
  end
end

puts ans