レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
全探索：全列挙
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
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 をメソッド呼び出しに変えてもさほど改善しなかった。