schedule2019-04-29

Pythonで解く：AtCoder Beginner Contest 125

競プロPython

AtCoder Beginner Contest 125に参加した記録。コメントや一部修正を加えています。

時間内にABDは解けたが、Cは7/13しか通らなかった。 Cは解説を見ながら解き直したコードです。

使用言語：Python 3.4

A - Biscuit Generator

問題

回答

実行時間 17 ms

import math

A, B, T = list(map(int, input().split()))

print(math.floor(T / A) * B)

B - Resale

問題

回答

$V_i - C_i > 0$ となる宝石を合計すればよい。

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))

    # 価値V - コストC 
    D = [V[i] - C[i] for i in range(N)]
    # V - C > 0のフィルタ
    F = [d for d in D if d > 0]

    if len(F) == 0:
        print(0)
    else:
        print(sum(F))

if __name__ == "__main__":
    main()

C - GCD on Blackboard

問題

回答

解説を見て解き直したもの。解説の数式を再現してある自信作だ！

コメントにある数値は、以下の入力を入れた場合のもの。

# 入力
5
12 15 18 24 12

def gcd(a, b):
    while(b):
        a, b = b, a % b
    return a


def main():
    N = int(input()) # 5
    A = list(map(int, input().split())) # 12 15 18 24 12

    index = list(range(N))
    L = index.copy()
    # L(0) = 0
    L[0] = 0
    for i in index[:-1]:
        L[i+1] = gcd(L[i], A[i])

    R = index.copy()
    # R(N + 1) = 0
    R.append(0)
    for i in reversed(index):
        R[i] = gcd(R[i+1], A[i])
    
    # print(L) [0, 12, 3, 3, 3]
    # print(R) [3, 3, 6, 12, 12, 0]
    
    # Mi = gcd(L(i), R(i+1))
    M = [gcd(f, b) for f, b in zip(L, R[1:])] # Rはi+1になるように1つずらしている
    # print(M) [3, 6, 3, 3, 3]
    
    print(max(M)) # 6


if __name__ == "__main__":
    main()

実行時間 122 ms

関数gcd()はぴよぴよ.pyさんのコードを使用した。

D - Flipping Signs

問題

回答

隣接する２つ値の正負を反転させて合計を最大化する問題。反転する回数に制限はない。

負の値の個数が偶数の場合はすべて正になるため、絶対値の合計となる。
負の値の個数が奇数の場合は、どれか一つ負の値が残る。その一つを絶対値が最小の値にする。

実行時間 53 ms

def main():
    N = int(input())
    A = list(map(int, input().split()))

    # 要素の絶対値
    B = list(map(abs, A))

    # 負の要素の個数
    C = [a for a in A if a < 0]
    if len(C) % 2 == 0:
        print(sum(B))
    else:
        # 最小値を負として計算する
        print(sum(B) - min(B)*2)


if __name__ == "__main__":
    main()