Tenka1 Programmer Beginner Contest 2019をPythonで解く

atcoder.jp

A - On the Way（100点）

• 必ずしもA < Bではないことに注意して条件分岐

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

if (A[0] < A[2] < A[1]) or (A[1] < A[2] < A[0]):
    print("Yes")
else:
    print("No")

B - *e**** ********e* *e****e* ****e**（200点）

• 問題文の通りに実装

N = int(input())
S = input()
K = int(input())

ans = ""

for s in S:
    if s == S[K-1]:
        ans += s
    else:
        ans += '*'

print(ans)

C - Stones（300点）

問題文の条件は、左端から連続するいくつかの石を白に、それ以外の石を黒にするという条件

editorial.pdf

• 全ての境目の値を試す
• とある境目を決めたとき「変えるべき個数」=「境目より左にある黒い石の個数」+「右にある白い石の個数」
• 累積和で持っておくと計算量が落とせる

from itertools import accumulate


N = int(input())
S = input()

black = [0]*N
white = [0]*N

for i, s in enumerate(S):
    if s == '#':
        black[i] = 1
    else:
        white[i] = 1

# 累積和
black = [0] + black
black = list(accumulate(black))
white = [0] + white[::-1]
white = list(accumulate(white))[::-1]

ans = []
for i in range(N+1):
    ans.append(black[i] + white[i])

print(min(ans))

D - Three Colors（600点）

• dpっぽいことは分かったが・・・
• 愚直解を書き上げるのも大事だと思ったので、TLEするコードを書いた
• 解説動画を見て勉強する

import itertools


N = int(input())
A = [int(input()) for i in range(N)]
cnt = 0

idx = [i for i in range(3)]
idx_l = [idx for _ in range(N)]
ans = list(itertools.product(*idx_l))
for a in ans:
    first = 0
    second = 0
    third = 0
    if (len(set(a)) == 3):
        for i, v in enumerate(a):
            if v == 0:
                first += A[i]
            elif v == 1:
                second += A[i]
            else:
                third += A[i]
        path = [first, second, third]
        if 2 * max(path) < sum(path):
            cnt += 1
print(cnt)