ABC152 - Marginalia

A

n, m = gets.split.map(&:to_i)
puts (n == m) ? "Yes" : "No"

B

a, b = gets.split.map(&:to_i)
result = a.to_s * b
tmp = b.to_s * a
result = tmp if result > tmp
puts result

C

これはすぐに思いついた。

n = gets.to_i
ps = gets.split.map(&:to_i)
min = ps.first
count = 0

ps.each do |p0|
  if p0 <= min
    count += 1
    min = p0
  end
end

puts count

D

とりあえず総当り。もちろんこれは提出していない。

n = io.gets.to_i
count = 0

(1..n).each do |i|
  il, ir = i.to_s[0], i.to_s[-1]
  (1..n).each do |j|
    jl, jr = j.to_s[0], j.to_s[-1]
    count += 1 if il == jr && ir == jl
  end
end

puts count

これで 1~200 を計算してみる。

[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 9], [11, 12], [12, 12], [13, 12], [14, 12], [15, 12], [16, 12], [17, 12], [18, 12], [19, 12], [20, 12], [21, 14], [22, 17], [23, 17], [24, 17], [25, 17], [26, 17], [27, 17], [28, 17], [29, 17], [30, 17], [31, 19], [32, 21], [33, 24], [34, 24], [35, 24], [36, 24], [37, 24], [38, 24], [39, 24], [40, 24], [41, 26], [42, 28], [43, 30], [44, 33], [45, 33], [46, 33], [47, 33], [48, 33], [49, 33], [50, 33], [51, 35], [52, 37], [53, 39], [54, 41], [55, 44], [56, 44], [57, 44], [58, 44], [59, 44], [60, 44], [61, 46], [62, 48], [63, 50], [64, 52], [65, 54], [66, 57], [67, 57], [68, 57], [69, 57], [70, 57], [71, 59], [72, 61], [73, 63], [74, 65], [75, 67], [76, 69], [77, 72], [78, 72], [79, 72], [80, 72], [81, 74], [82, 76], [83, 78], [84, 80], [85, 82], [86, 84], [87, 86], [88, 89], [89, 89], [90, 89], [91, 91], [92, 93], [93, 95], [94, 97], [95, 99], [96, 101], [97, 103], [98, 105], [99, 108], [100, 108], [101, 113], [102, 115], [103, 117], [104, 119], [105, 121], [106, 123], [107, 125], [108, 127], [109, 129], [110, 129], [111, 136], [112, 138], [113, 140], [114, 142], [115, 144], [116, 146], [117, 148], [118, 150], [119, 152], [120, 152], [121, 161], [122, 163], [123, 165], [124, 167], [125, 169], [126, 171], [127, 173], [128, 175], [129, 177], [130, 177], [131, 188], [132, 190], [133, 192], [134, 194], [135, 196], [136, 198], [137, 200], [138, 202], [139, 204], [140, 204], [141, 217], [142, 219], [143, 221], [144, 223], [145[152, 250], [153, 252], [154, 254], [155, 256], [156, 258], [157, 260], [158, 26, 289], [166, 291], [167, 293], [168, 295], [169, 297], [170, 297], [171, 316], [172, 318], [173, 320], [174, 322], [175, 324], [176, 326], [177, 328], [178, 330], [179, 332], [180, 332], [181, 353], [182, 355], [183, 357], [184, 359], [185, 361], [186, 363], [187, 365], [188, 367], [189, 369], [190, 369], [191, 392], [192, 394], [193, 396], [194, 398], [195, 400], [196, 402], [197, 404], [198, 406], [199, 408], [200, 408]]

　
これを眺めていて、漸化式を計算すればよいことがわかった。つまり、n が 1 増えるときに結果がいくつ増えるか考える。O(n)。

def calc(n)
  result = 0
  (1..n).each do |i|
    if i < 10
      result += 1
    else
      str = i.to_s
      digits = str.length - 2
      next if str[-1] == "0"
      if str[0] < str[-1]
        #i=1263だったら、13, 1_3みたいなやつ
        result += [0, 1, 11, 111, 1111][digits] * 2
      elsif str[0] > str[-1]
        #i=4321だったら、14, 1_4, 1__4みたいなやつ
        result += [1, 11, 111, 1111, 11111][digits] * 2
      else
        #i=1321だったら、1, 11, 1_1みたいなやつ
        result += [1, 2, 12, 112, 1112][digits] * 2
        #i=1321だったら、1001 ~ 1__1 ~ 1321みたいなやつで、1321は重複するので-1する
        result += (str[1..-2].to_i + 1) * 2 - 1
      end
    end
  end
  result
end

puts calc(gets.to_i)

まずまずうまく解けたと思う。207ms。
　

E

全体の最小公倍数を求める。あとはそれぞれの a で割って足すだけ。

LIMIT = 10 ** 9 + 7

n = gets
as = gets.split.map(&:to_i)
result = 0

lcm0 = as.inject(1) {|acc, i| acc.lcm(i)}
as.each {|ai| result += lcm0 / ai}

puts result % LIMIT

誰でも思いつく凡庸な方法ですぐにクリア。大きな数を簡単に扱えるのは Ruby の恩恵である。でも、時間は 1319 ms で全然よくない感じだが、調べてみると Ruby だとまあ皆んな同じようなものか。