ABC161 - Marginalia

A: ABC Swap

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

a, b = b, a
a, c = c, a

puts "#{a} #{b} #{c}"

B: Popular Vote

n, m = gets.split.map(&:to_i)
votes = gets.split.map(&:to_i)

limit = Rational(votes.inject(&:+), 4 * m)
num = votes.reject {|v| v < limit}.size

puts (m <= num) ? "Yes" : "No"

C: Replacing Integer

最初、以下でやってひとつだけ WA になった。

def solve(x, k, tmp_min)
  tmp_min0 = [x, tmp_min].min
  return tmp_min if tmp_min0 == tmp_min
  solve((x - k).abs, k, tmp_min0)
end

n, k = gets.split.map(&:to_i)
puts solve(n % k, k, n)

　
解説を見ると、実際は

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

t = n % k
puts [k - t, t].min

でいい。これはわかったのだが、上の何がいけなかったのだろう。
　

D: Lunlun Number

とりあえず最初の500個を出力してみる。

def lunlun?(x)
  return true if x < 10
  str = x.to_s
  pred = str[0].to_i
  str[1..-1].each_char do |c|
    tmp = c.to_i
    return false unless (pred - tmp).abs <= 1
    pred = tmp
  end
  true
end

result = []
count = 0
1.step do |i|
  if lunlun?(i)
    result << i
    count += 1
    break if count >= 500
  end
end
p result

すると、こんな感じ。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 332, 333, 334, 343, 344, 345, 432, 433, 434, 443, 444, 445, 454, 455, 456, 543, 544, 545, 554, 555, 556, 565, 566, 567, 654, 655, 656, 665, 666, 667, 676, 677, 678, 765, 766, 767, 776, 777, 778, 787, 788, 789, 876, 877, 878, 887, 888, 889, 898, 899, 987, 988, 989, 998, 999, 1000, 1001, 1010, 1011, 1012, 1100, 1101, 1110, 1111, 1112, 1121, 1122, 1123, 1210, 1211, 1212, 1221, 1222, 1223, 1232, 1233, 1234, 2100, 2101, 2110, 2111, 2112, 2121, 2122, 2123, 2210, 2211, 2212, 2221, 2222, 2223, 2232, 2233, 2234, 2321, 2322, 2323, 2332, 2333, 2334, 2343, 2344, 2345, 3210, 3211, 3212, 3221, 3222, 3223, 3232, 3233, 3234, 3321, 3322, 3323, 3332, 3333, 3334, 3343, 3344, 3345, 3432, 3433, 3434, 3443, 3444, 3445, 3454, 3455, 3456, 4321, 4322, 4323, 4332, 4333, 4334, 4343, 4344, 4345, 4432, 4433, 4434, 4443, 4444, 4445, 4454, 4455, 4456, 4543, 4544, 4545, 4554, 4555, 4556, 4565, 4566, 4567, 5432, 5433, 5434, 5443, 5444, 5445, 5454, 5455, 5456, 5543, 5544, 5545, 5554, 5555, 5556, 5565, 5566, 5567, 5654, 5655, 5656, 5665, 5666, 5667, 5676, 5677, 5678, 6543, 6544, 6545, 6554, 6555, 6556, 6565, 6566, 6567, 6654, 6655, 6656, 6665, 6666, 6667, 6676, 6677, 6678, 6765, 6766, 6767, 6776, 6777, 6778, 6787, 6788, 6789, 7654, 7655, 7656, 7665, 7666, 7667, 7676, 7677, 7678, 7765, 7766, 7767, 7776, 7777, 7778, 7787, 7788, 7789, 7876, 7877, 7878, 7887, 7888, 7889, 7898, 7899, 8765, 8766, 8767, 8776, 8777, 8778, 8787, 8788, 8789, 8876, 8877, 8878, 8887, 8888, 8889, 8898, 8899, 8987, 8988, 8989, 8998, 8999, 9876, 9877, 9878, 9887, 9888, 9889, 9898, 9899, 9987, 9988, 9989, 9998, 9999, 10000, 10001, 10010, 10011, 10012, 10100, 10101, 10110, 10111, 10112, 10121, 10122, 10123, 11000, 11001, 11010, 11011, 11012, 11100, 11101, 11110, 11111, 11112, 11121, 11122, 11123, 11210, 11211, 11212, 11221, 11222, 11223, 11232, 11233, 11234, 12100, 12101, 12110, 12111, 12112, 12121, 12122, 12123, 12210, 12211, 12212, 12221, 12222, 12223, 12232, 12233, 12234, 12321, 12322, 12323, 12332, 12333, 12334, 12343, 12344, 12345, 21000, 21001, 21010, 21011, 21012, 21100, 21101, 21110, 21111, 21112, 21121, 21122, 21123, 21210, 21211, 21212, 21221, 21222, 21223, 21232, 21233, 21234, 22100, 22101, 22110, 22111, 22112, 22121, 22122, 22123, 22210, 22211, 22212, 22221, 22222, 22223, 22232, 22233, 22234, 22321, 22322, 22323, 22332, 22333, 22334, 22343, 22344, 22345, 23210, 23211, 23212, 23221, 23222, 23223, 23232, 23233, 23234, 23321, 23322, 23323, 23332, 23333, 23334, 23343, 23344, 23345, 23432, 23433, 23434, 23443, 23444, 23445, 23454, 23455, 23456, 32100, 32101, 32110, 32111, 32112, 32121, 32122, 32123, 32210, 32211, 32212, 32221, 32222, 32223, 32232, 32233, 32234, 32321, 32322, 32323, 32332, 32333, 32334, 32343, 32344, 32345, 33210, 33211, 33212, 33221, 33222, 33223, 33232, 33233, 33234, 33321, 33322]

ふーむ。

よくわからないので、他の人の解答を参考にしてみる。

def solve(k)
  q = [*1..9]
  cnt = 0
  loop do
    return q[k - 1] if k < 10
    
    x = q[cnt]
    3.times do |i|
      return q.last if q.length == k
      
      d = x % 10 + (i - 1)
      next if d < 0 || d > 9
      
      q << x * 10 + d
    end
    cnt += 1
  end
end

puts solve(gets.to_i)

うーん、かしこい。これだと計算量は O(n) かあ。
　

E: Yutori

全然わからない。解答例。

n, k, c = gets.split.map(&:to_i)
str = gets.chomp

left  = Array.new(k)
right = Array.new(k)
l, r = 0, n - 1

k.times do |i|
  l += 1 while str[l] == "x"
  r -= 1 while str[r] == "x"
  left[i] = l
  right[k - i - 1] = r
  l += c + 1
  r -= c + 1
end

result = []
k.times do |i|
  if left[i] == right[i]
    result << left[i] + 1
  end
end

puts result

かしこいなあ。