Rubyで「分野別 初中級者が解くべき過去問精選100問」を解く

Ruby

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
　
全探索：全列挙

ITP1_7_B - How Many Ways?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

loop do
  n, x = gets.split.map(&:to_i)
  break if (n + x).zero?
  
  count = 0
  [*1..n].combination(3) do |given|
    count += 1 if given.inject(:+) == x
  end
  
  puts count
end

　

AtCoder Beginner Contest 106 B - 105

https://atcoder.jp/contests/abc106/tasks/abc106_b

n = gets.to_i

puts 1.step(n, 2).map {|i|
       (1..i).select {|x| (i % x).zero?}.size == 8
     }.count(true)

　

AtCoder Beginner Contest 122 B - ATCoder

https://atcoder.jp/contests/abc122/tasks/abc122_b

str = gets.chomp
result = str.split(/[^ACGT]/).map(&:size).max
puts result || 0

　
全列挙で解いてみる。

s = gets.chomp

max = 0

doit = ->(str) {
  return if str.empty?
  (str.length).downto(1) do |l|
    next if /[^ACGT]/.match(str[0, l])
    max = l if l > max
  end
  doit.(str[1..-1])
}
doit.(s)

puts max

　

パ研杯2019 C - カラオケ

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

n, m = gets.split.map(&:to_i)
table = n.times.map {gets.split.map(&:to_i)}

puts [*0...m].combination(2).map {|t1, t2|
       n.times
        .map {|student| [table[student][t1], table[student][t2]].max}
        .inject(:+)
     }.max

　
全探索：工夫して通り数を減らす全列挙

AtCoder Beginner Contest 095 C - Half and Half

https://atcoder.jp/contests/abc095/tasks/arc096_a

a, b, ab, x, y = gets.split.map(&:to_i)

z = [x, y].max * 2
puts 0.step(z, 2).map {|n_ab|
       n_a = [x - n_ab / 2, 0].max
       n_b = [y - n_ab / 2, 0].max
       a * n_a + b * n_b + ab * n_ab
     }.min

　

三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

require "set"

gets
s = gets.chomp.chars

pool = Set.new
s.combination(3) {|code| pool << code.join}

puts pool.size

予想どおり TLE。

考え直す。

gets.to_i
str = gets.chomp

is_included = ->(i) {
  pointer = 0
  table = sprintf("%03d", i).chars
  str.each_char do |c|
    if c == table[pointer]
      pointer += 1
      return true if pointer == 3
    end
  end
  false
}

puts (0..999).map {|i| is_included.(i)}.count(true)

TLE。

考え直す。

n = gets.to_i
str = gets.chomp

check = Array.new(1000, 0)

0.upto(n - 3) do |i|
  (i + 1).upto(n - 2) do |j|
    (j + 1).upto(n - 1) do |k|
      num = (str[i] + str[j] + str[k]).to_i
      check[num] = 1
    end
  end
end

puts check.inject(:+)

TLE。

他の人の答えを見た。すごい工夫だな。たった 8ms。

n = gets.to_i
s = gets.chomp

puts [*"0".."9"].repeated_permutation(3).count {|i, j, k|
       (a = s.index(i, 0)) && (b = s.index(j, a + 1)) && s.index(k, b + 1)
     }

でも、よく考えたらこれ、is_included を使う解法とアルゴリズムは一緒じゃないか。Ruby の組み込みを使うかどうかだけだな。
　

JOI 2007 本選 3 - 最古の遺跡

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

max = 0

pillars.combination(2) do |p1, p2|
  vy = p2[0] - p1[0]
  vx = p1[1] - p2[1]
  calc = ->(x, y) {
    return false unless pillars.include?([p1[0] + x, p1[1] + y])
    return false unless pillars.include?([p2[0] + x, p2[1] + y])
    x * x + y * y
  }
  area = calc.(vx, vy)
  max = area if area && area > max
  area = calc.(-vx, -vy)
  max = area if area && area > max
end

puts max

TLE。Ruby では正解者なし。

高速化。

n = gets.to_i
pillars_str = n.times.map {gets.chomp}

max = 0
pillars = pillars_str.map {|pl| pl.split.map(&:to_i)}

pillars.combination(2) do |p1, p2|
  vy = p2[0] - p1[0]
  vx = p1[1] - p2[1]
  calc = ->(x, y) {
    return false unless pillars_str.include?("#{p1[0] + x} #{p1[1] + y}")
    return false unless pillars_str.include?("#{p2[0] + x} #{p2[1] + y}")
    x * x + y * y
  }
  area = calc.(vx, vy)
  max = area if area && area > max
  area = calc.(-vx, -vy)
  max = area if area && area > max
end

puts max

3/10 AC だったのが、6/10 AC に改善された。でもやはり TLE。
lambda をメソッド呼び出しに変えてもさほど改善しなかった。