diverta 2019 Programming Contest

posts/2019-05-14diary

A, B, C, Dの4完。
得点1200パフォ1317.25はhighestだったが、
残念ながらジャッジサーバーのトラブルでunratedに。

今回初めてRubyで本番コンテストに参加した。

A - Consecutive Integers

n個のうち、長さ$$n$$の区間の末尾として何個選べるか？と考えられる。
なので、$$n - k + 1$$個。

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

puts n - k + 1

B - RGB Boxes

最初問題を誤読していた。

制約が $$1≤R,G,B,N≤3000$$なので、$$3000 ^ 3$$のr, g, bの3重ループは書けない。
なのでr, gを回す2重ループにして、nから引いた残りがbで割り切れるかを判定すればよい。

r, g, b, n = gets.strip.split.map(&:to_i)

ans = 0
(0..n).each do |i|
    (0..n).each do |j|
        rest = n - (r * i + g * j)
        if rest >= 0 && rest % b == 0 && rest / b <= 3000
            ans += 1
        end
    end
end

puts ans

C - AB Substrings

とんでもなく泥臭いコードを書いた(コンテスト中必死だったので)。恥ずかしいけど載せる。

最初それぞれの文字列に含まれるABの個数を数える。
そのあと並び替えて連結したあと新たに作られるABを数える。

並び替えに関しては、

先頭がBで末尾がA(BA)
末尾がA(XA)
先頭がB(BX)

この3種類の文字列をどう並べるのが最適かを考える。まず最初はXAがあればXAにする。
次からは、BAがあればBAを全てもってくる。
BAがなくなったあとは、ひとつ前がAで終わっていればXA(あれば)、
Aで終わってなければBAをもってくるという感じ。

n = gets.strip.to_i
ss = n.times.map { gets.strip }

count = 0
xa = 0
ba = 0
bx = 0

ss.each do |s|
    (0..s.length-2).each do |i|
        if s[i] + s[i+1] == "AB"
            count += 1
        end
    end

    if s.start_with?("B") && s.end_with?("A")
        ba += 1
        next
    end
    if s.end_with?("A")
        xa += 1
        next
    end
    if s.start_with?("B")
        bx += 1
        next
    end
end

s2 = ""
while xa > 0 || ba > 0 || bx > 0
    if s2 == ""
        if xa > 0
            s2 += "XA"
            xa -= 1
        elsif ba > 0
            s2 += "BA"
            ba -= 1
        elsif bx > 0
            s2 += "BX"
            bx -= 1
        end
    else
        if s2.end_with?("A")
            if ba > 0
                s2 += "BA"
                ba -= 1
            elsif bx > 0
                s2 += "BX"
                bx -= 1
            elsif xa > 0
                s2 += "XA"
                xa -= 1
            end
        else
            if ba > 0
                s2 += "BA"
                ba -= 1
            elsif xa > 0
                s2 += "XA"
                xa -= 1
            elsif bx > 0
                s2 += "BX"
                bx -= 1
            end
        end
    end
end

count2 = 0
(0..s2.length-2).each do |i|
    if s2[i] + s2[i+1] == "AB"
        count2 += 1
    end
end

puts count + count2

D - DivRem Number

制約が$$1≤N≤10^{12}$$なので明らかに全探索はできない。とりあえず小さい$$n$$で実験してみる。
すると、どうも約数-1の数が求める$$m$$になるっぽいことがわかった。
つまり約数を列挙して、それで実際に「商 = 余り」になっているかを試せばいい。
WAだったらもっとちゃんと考えるかと思って、約数を列挙するコードをとりあえずネットで探して提出してみたらACだった。

ちゃんと考えると、
商と余りを$$k$$とすると、$$N = km + k = k(m + 1)$$になるので、
約数-1を全探索すればよいことがわかる。

これ、500点問題にしてはめちゃくちゃ簡単だったのでは。

require 'prime'

n = gets.to_i

class Integer
    def divisor_list
        return [] if self <= 0
        return [1] if self == 1
  
        prime_division.map.with_index { |(base, k), i|
            s = i.zero? ? 0 : 1
            (s..k).map { |n| base ** n }
        }.inject { |res, e| res + res.flat_map { |t| e.map { |v| t * v } } }.sort
    end
end
  
ans = 0
list = n.divisor_list
list.each do |i|
    m = i - 1
    if m != 0
        if n / m == n % m
            ans += m
        end
    end
end

puts ans