ABC152
https://atcoder.jp/contests/abc152
過去問。
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 だとまあ皆んな同じようなものか。