u++の備忘録

AtCoder Beginner Contest 126をPythonで解く

AtCoder Beginner Contest 126をPythonで解きました(A〜E)。

atcoder.jp

A - Changing a Character(100点)

  • いろんなやり方はあると思うが、計算量も余裕があるので愚直に
  • マッピング用のdictを用意し、K番目のときだけ適用する
N, K = list(map(int, input().split()))
S = input()

convert_dict = {
    'A': 'a',
    'B': 'b',
    'C': 'c'
}

ans = ''

for i, s in enumerate(S):
    if i != (K - 1):
        ans += s
    else:
        ans += convert_dict[s]

print(ans)

B - YYMM or MMYY(200点)

  • もっと綺麗に書ける気もするが、前半・後半がMMになり得るかをそれぞれ確認する
S = input()

month_flg0 = True
month_flg1 = True

if (S[:2] > '12' or S[:2] < '01'):
    month_flg0 = False

if (S[2:] > '12' or S[2:] < '01'):
    month_flg1 = False

if month_flg0 and month_flg1:
    print('AMBIGUOUS')
elif not(month_flg0) and not(month_flg1):
    print('NA')
elif month_flg0:
    print('MMYY')
else:
    print('YYMM')

C - Dice and Coin(300点)

  • 数学だった
  • 「何回連続でコインが表を出す必要があるか」を計算する(コードのコメント参照)
import math


N, K = list(map(int, input().split()))

ans = 0

for n in range(1, N+1):
    # 2^(num_success) * n >= K なる num_success
    # 2^(num_success) >= K/n
    # num_success >= log_2(K/n)
    num_success = max(0, math.ceil(math.log2(K/n)))
    ans += (1/2) ** num_success

print(ans/N)

D - Even Relation(400点)

  • editorial.pdf の解説が分かりやすい
  • sys.setrecursionlimit(20000000) 忘れでREが出て辛かった提出
import sys
sys.setrecursionlimit(20000000)


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')

E - 1 or 2(500点)

  • ABC120 Dでも使ったUnionFindTreeクラスを貼った
  • uniteした回数を持たせた

upura.hatenablog.com

import sys
sys.setrecursionlimit(20000000)


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')