鴨川η

abc055

はじめに

Juliaを書いていく気持ちになったので以前開催された競プロの問題を解いた.初心者なのでatocoderのABC 055


A

標準入力 readline() からググった.

N = parse(Int64, chomp(readline()))
println(800*N - div(N, 15)*200)

この時点で実行時間がやたら遅いので,juliaで解くのは厳しいのではと思い始めた.


B

factorial だと Int64 で表現できない値になるので forの中で余りを求める.

N = parse(Int64, chomp(readline()))
m = 10^9 + 7
s = 1

for i in 1:N
    s *= i
    s %= m
end

println(s)

C

Mが奇数だとめんどうだったので小さい方の偶数に合わせた.

N, M = map(x -> parse(Int64, x), split(chomp(readline())))
if M % 2 == 1
    M -= 1
end
nb_scc = 0

if N <= div(M, 2)
    nb_scc += N
    M -= 2*N
    nb_scc += div(M, 4)
else
    nb_scc = min(div(M, 2), N)
end

println(nb_scc)

D

わからないなと思って解説を読んだけどよくわからなかった問題. 解説から推測するに, 番目は 番目の動物の種類と s[i] から自動的に決定できる.よって

  1. 1番目と2番目の全組み合せ4つのうち1つ選んで,輪全体を構築
  2. 1番目とN番目について s とあっているかチェック
  3. あっていればその時の輪を出力,そうでなければ別の輪を試す

という感じだと思う.

juliaの書き方が悪いのか s が長いとTLEになる.

const N = parse(Int64, chomp(readline()))
const s = chomp(readline())
const types = ["S", "W"]

res = ""

function check(a::Char, b::Char, c::Char, s::Char)
    if s == 'o'
        if b == 'W'
            return a != c
        else
            return a == c
        end
    else
        if b == 'W'
            return a == c
        else
            return a != c
        end
    end
end

for t = types
    circle = ""
    for tt in types
        circle = t*tt
        for i in 2:N-1
            pre_a = circle[i-1]
            now_a = circle[i]
            if s[i] == 'o'
                if pre_a == now_a
                    circle *= "S"
                  else
                    circle *= "W"
                end
            else
                if pre_a == now_a
                  circle *= "W"
                else
                  circle *= "S"
              end
            end
        end
        is_ok = true
        is_ok *= check(circle[end], circle[1], circle[2], s[1])
        is_ok *= check(circle[N-1], circle[end], circle[1], s[end])
        if is_ok
            println(circle)
            quit()
        end
    end
end

println(-1)

Pythonだと通る.

N = int(input())
s = input().strip()

types = ["S", "W"]

res = ""

def check(a, b, c, s):
    if s == 'o':
        if b == 'W':
            return a != c
        else:
            return a == c
    else:
        if b == 'W':
            return a == c
        else:
            return a != c

for t in types:
    circle = ""
    for tt in types:
        circle = t+tt
        for i in range(1, N-1):
            pre_a = circle[i-1]
            now_a = circle[i]
            if s[i] == 'o':
                if pre_a == now_a:
                    circle += "S"
                else:
                    circle += "W"
            else:
                if pre_a == now_a:
                    circle += "W"
                else:
                    circle += "S"
        is_ok = True
        is_ok *= check(circle[-1], circle[0], circle[1], s[0])
        is_ok *= check(circle[-2], circle[-1], circle[0], s[-1])

        if is_ok:
            print(circle)
            exit()

print(-1)