【Atcoder解法検討】ABC126 A~E Python

A - Changing a Character

問題ページ : A - Change a Character

考察

入力値を受け取り加工して出力、という典型。
文字列の指定位置を変更するため入力文字列をリストで受け取るのが楽。このときリストのインデックスは0~N-1になることに注意。つまりK文字目に相当するインデックスはK-1。
アルファベット大文字の小文字への変化はlowercase()を使用する、

コード

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

S[K-1] = S[K-1].lower()
print("".join(S))

B - YYMM or MMYY

問題ページ : B - YYMM or MMYY

考察

入力値を受け取り条件分岐して出力。
まず受けた数字を上二桁と下二桁に分離します。
分離した数字それぞれの数字がMM（月）に相当するか判定します。数字が01~12の範囲であればMMとなり得ますがが、それ以外ではなり得ません。なお任意の二桁数字(00~99)はYYに相当できることに留意。
　上二桁、下二桁それぞれのMMになり得る（真）、なり得ない（偽）の4つの組み合わせがあり、その組み合わせに対応する出力は以下の表のようになります。

	上二桁 : 真	上二桁 : 偽
下二桁 : 真	AMBIGUOUS	YYMM
下二桁 : 偽	MMYY	NA

コード

S = int(input())

# 上二桁、下二桁に分離
S1 = S // 100    # 上二桁
S2 = S % 100     # 下二桁

F1 = 1 <= S1 <= 12     # 上二桁がMMとなりうるか
F2 = 1 <= S2 <= 12     # 下二桁がMMとなりうるか

# 組み合わせにより出力
if F1 == F2 == True:                # 上二桁、下二桁両方ともMMになり得る
    print("AMBIGUOUS")
elif F1 == True and F2 == False:    # 上二桁のみMMになりうる
    print("MMYY")
elif F1 == False and F2 == True:    # 下二桁にみMMになりうる
    print("YYMM")
elif F1 == F2 == False:             # 上二桁、下二桁ともにMMになり得ない 
    print("NA")

C - Dice and Coin

問題ページ : C - Dice and Coin

考察

確率計算。ループを使って実直に計算できる。
求められている確率は、最初にi(1~N)の目が出たときに勝利する確率は足し合わせた結果となる（for文で処理）。
最初にiの目をだして処理する確率は
「最初にiの目をだす確率」に「最初の目から2倍を繰り返しKを超える回数1/2を掛ける」ことによって求まる（条件付きループであるwhile分で処理）
計算量はO(N・logK)。

コード

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

ans = 0
for i in range(1, N + 1):       #　最初の目iが1~N
    score = i
    tmp = 1 / N                 # 最初の目がi毎に勝利する確率tmpを計算する
    while score < K:            # scoreがKより小さい間繰り返す
        score *= 2
        tmp /= 2
    ans += tmp

print(ans)

D - Even Relation

問題ページ : D - Even Relation

考察

　グラフ（木）の問題。
　最初の発想として任意の頂点（ここでは頂点１）を根として、各頂点の根からの距離を求めれば解に近づくのではないかということ。イメージしやすくするために以下のようなグラフを描いて考えてみる。
グラフからのイメージで以下のことがいえる。

[２頂点の距離]=[根から各頂点への距離の和]-[根から各頂点への共通パス部分の長さ]×2

[根から各頂点への共通部分の長さ」は自明ではないが、式中では2倍して差し引かれているため偶奇には影響しない。よって

[2頂点の距離の偶奇]=[根から各頂点への距離の和の偶奇]

となる。足し合わせて偶数となるのは偶数どうしまたは奇数どうしでそれ以外の組み合わせの和は奇数となる。よって根からの距離の偶奇によって塗り分ければ良いことがわかった。
根から各頂点への距離はBFSで求めることができる。

コード

from collections import deque

N = int(input())

# 重み付き隣接リスト作成
G = [ [] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v,w))
    G[v].append((u,w)) 

# 各頂点の頂点１からの距離をBFSで計算
Q = deque()
dist = [-1] * (N + 1)
Q.append(1)
dist[1] = 0
while len(Q) > 0:
    x = Q.popleft()
    for nx, w in G[x]:
        if dist[nx] != -1:continue
        dist[nx] = dist[x] + w
        Q.append(nx)

# 各頂点の頂点１からの距離の偶奇を0,1で出力
for i in range(1,N + 1):
    print(dist[i] % 2)

　このコードでACとなるが、根からの距離（コード中のdist）がとても大きな値となりうることも考慮し、根から距離自体も偶奇だけ扱うように修正してみた。

from collections import deque

N = int(input())

# 重み付き隣接リスト作成
G = [ [] for _ in range(N+1)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    G[u].append((v,w % 2))
    G[v].append((u,w % 2)) 

# 各頂点の頂点１からの距離の偶奇をBFSで計算
Q = deque()
dist = [-1] * (N + 1)
Q.append(1)
dist[1] = 0
while len(Q) > 0:
    x = Q.popleft()
    for nx, w in G[x]:
        if dist[nx] != -1:continue
        dist[nx] = (dist[x] + w) % 2
        Q.append(nx)

# 各頂点の頂点１からの距離の偶奇を0,1で出力
for i in range(1,N + 1):
    print(dist[i])

もちろんこちらでもACとなる。

E - 1 or 2

問題ページ : E - 1 or 2

考察

ぱっと見では方針がたてづらい、入力例で具体的に考えてみよう。

入力例1

入力例１の条件は

A_1+A_2+1=偶数

すなわち

A_1+A_2=奇数

　この式から$(A_1, A_2) = (1, 2)$もしくは$(2, 1)$で$A_1,A_2$どちらかを魔法で知ることができれば、もう一方は自動的に判明します。
また$A_3$は任意となりますので魔法で知る必要があります。
よって最小コスト2で$A_1$から$A_3$全てをしることができます。

入力例2

入力例2も同様に数式であらわすと、

\left\{ \,
    \begin{aligned}
    & A_1 + A_2 + 1 = 偶数 \\
    & A_2 + A_3 + 2 = 偶数 \\
    & A_1 + A_3 + 3 = 偶数
    \end{aligned}
\right.

\left\{ \,
    \begin{aligned}
    & A_4 + A_5 + 4 = 偶数 \\
    & A_5 + A_6 + 5 = 偶数
    \end{aligned}  
\right.

すなわち

\left\{ \,
    \begin{aligned}
    & A_1 + A_2 = 奇数 \\
    & A_2 + A_3 = 偶数 \\
    & A_1 + A_3 = 奇数
    \end{aligned}
\right.

\left\{ \,
    \begin{aligned}
    & A_4 + A_5 = 偶数 \\
    & A_5 + A_6 = 奇数
    \end{aligned}  
\right.

と二組の連立方程式が得られ、$A_1, A_2, A_3$のうち一つを魔法で知ることができれば、残り二つは自動的に判明します。同様に$A_4, A_5, A_6$のうち一つを魔法で知ることができれば、残り二つは自動的に判明します。
よって最小コストは2となります。

　これらの例から数式であらわされた二つのカードをグラフとして連結させたときに、連結成分の個数が求めるべき最小コストであると推定されます。
　連結成分数を数える方法はDFS,BFS,UnionFindがありますが、atcoder libraryのUnionFind(DSU)を使用するのが楽でしょう。

コード

from atcoder.dsu import DSU

N, M = map(int, input().split())
Q = [ tuple(map(int, input().split())) for _ in range(M)]

U = DSU(N)

# 数式で表されたカードを0-indexに変換してＵnionＦind上で連結
for x,y,z in Q:
    x -= 1
    y -= 1
    U.merge(x,y)

# UnionＦind上の連結成分を出力
print(len(U.groups()))

F - XOR Matching

問題ページ : F - XOR Matching

青色diff以上の難易度は保留