AtCoder Beginner Contest 126をPythonで解く
AtCoder Beginner Contest 126をPythonで解きました(A〜E)。
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した回数を持たせた
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')