バーチャル参加 ABC126 - Xenous の精進記録

全完1ペナ 65分でした

A - Changing a Character

小文字に置き換えるのは python であれば s を文字列型として s.lower() でできます。該当箇所のみ lower を使って、それ以外はそのまま表示させるようにします。

N, K = map(int, input().split())
S = input()
print(S[:K-1] + S[K-1].lower() + S[K:])

B - YYMM or MMYY

MM として表示できるのは $1 \leq \mathrm{MM} \leq 12$ になります。この範囲内であれば、MM と言えます。そうでない場合は YY です。 MMMM となる場合は AMBIGUOUS となります。片方 MM のパターンはそのままで、それ以外は全て NA です。

S = input()
bf = S[:2]; af = S[2:]
if 1 <= int(bf) <= 12: bf_flag = True
else: bf_flag = False

if 1 <= int(af) <= 12: af_flag = True
else: af_flag = False

if bf_flag and af_flag: print('AMBIGUOUS')
elif bf_flag and not af_flag: print('MMYY')
elif not bf_flag and af_flag: print('YYMM')
else: print('NA')

C - Dice and Coin

1回目の出た目の数によって、何回あと表出し続けないといけないかが変わるのでそれごとに計算します。

1回目は $1$ から $N$ まで等確率で目が出るので、確率は $\frac{1}N$ 。1回目に出た値を $a$ とおくと、そのあとの確率は、表を連続して出す確率なので、 $\left(\frac12\right)^{j}$ （ $k$ は $a \times 2^{j} \geq K$ を満たす最小の整数）と表せます。

これを $1$ から $N$ までのパターン全て計算して足し合わせれば良いです。

N, K = map(int, input().split())
p0 = 1/N; ans = 0.0
for score in range(1, N+1):
    cnt = 0
    while score < K:
        score *= 2
        cnt += 1
    ans += p0 / (2 ** cnt)
print(ans)

D - Even Relation

同じ色に塗られた任意の $2$ 頂点について、その距離が偶数である。

色が先で、その後距離を見ると、頂点どうしの距離が偶数である、という確認の順番です。

思いつきで、根を黒で借り決めして、距離が偶数であるときは親と同じ色、距離が奇数であるときは親と異なる色、とすると、塗り分けが可能で、問題文の状態を満たすことができます。

提出コード

from collections import deque

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

fr = 0
que = deque([fr])
goneset = set([fr])
ans = [-1] * N; ans[fr] = 0
while True:
    fr = que.popleft()
    for to, w in graph[fr]:
        if to in goneset:
            continue
        if w%2 == 0: ans[to] = ans[fr]
        else: ans[to] = (ans[fr]+1)%2
        que.append(to)
        goneset.add(to)
    if len(que) == 0:
        break
print(*ans, sep='\n')

E - 1 or 2

「 $A_{X_i} + A_{Y_i} + Z_i$ が偶数」の情報だけだと $A_{X_i}$ と $A_{Y_i}$ の偶奇を確定できません。このうち片方が分かれば両方を特定できます。この場合はコスト1を使う必要があります。

また、上で明らかになった $A_{k}$ の情報が、他の $A_{X_j} + A_{Y_j} + Z_j$ で使えれば、コストを払う必要がありません。

したがって、コスト 1 払ったときに連鎖的にわかる範囲が管理できていればよく、UnionFind を使って実装できます。

提出コード

class UnionFind():
    """
    unionfind を扱うクラス (0-index)

        Parameters:
        -----------
        n: int
            管理するデータの要素数
    """
    def __init__(self, n:int):
        """
        Parameters:
        -----------
        n: int
            要素数
        parents: list
            各要素が属する親の要素番号
        grouping: set
            親番号の集合
        rank: list
            親の rank を保持するためのリスト
        size: list
            親の size を保持するためのリスト
        """
        self.n = n
        self.parents = [-1]*n
        self.grouping = set(range(n))
        self.rank = [0]*n
        self.size = [1]*n


    def find(self, x:int) -> int:
        """
        要素 x の親の要素を見つけるメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の親の要素番号
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    

    def union(self, x:int, y:int) -> None:
        """
        要素 x, y の属するグループを結合するメソッド
        
        Parameters:
        -----------
        x, y: int
            結合対象の要素番号
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            # rank(x)の方が小さい場合は, xをくっつけて, y を親にする
            self.size[y] += self.size[x]
            self.parents[x] = y
            self.grouping.difference_update(set([x]))
        else:
            # そうでないときは, y をくっつけて, x を親にする
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.grouping.difference_update(set([y]))


    def msize(self, x:int) -> int:
        """
        要素 x の属するグループの大きさを返すメソッド

        Parameters:
        -----------
        x: int
            要素番号
        
        Returns:
        --------
        int
            x の属するグループの大きさ(要素数)
        """
        return self.size[self.find(x)]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        X -= 1; Y -= 1
        uf.union(X, Y)
    ans = len(uf.grouping)
    print(ans)


if __name__ == "__main__":
    main()

F - XOR Matching

XOR の bit 演算は、以下のようになります。

XOR	1	0
1	0	1
0	1	0

演算は、以下のように数字の各 bit どうしを比較して上記演算の結果を返します。

# ^ は XOR
5^13 #8

10進数	2進数
5:	0101
13:	1101
8:	1000

また、結合法則、交換則が成り立ちます。（ $\oplus$ ）

$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
$a \oplus b = b \oplus a$

そして、0 は以下を満たします。

$a \oplus 0 = a$
$a \oplus a = 0$

さて、問題文の状況から、 $0$ 以上 $2^{M}$ 未満の整数が2つずつ使える中で数列を作り、同じ値で囲まれる間の数列の XOR を行うと $K$ になるようにします。

まず、XOR は bit 演算なので、演算した後に bit の最大の桁数が増えることはありません。したがって、 $K \geq 2^{M}$ の場合は XOR して $K$ を作ることができません。

そうでない場合は、数列のなかに $K$ を入れることができます。 $a \oplus a = 0$ が成り立つので、以下のように $K$ を同じ数字で囲むと、問題文の条件を満たせます。

0 2 3 4 K 4 3 2 0

$K$ どうしの場合どうするかですが、次の性質を使うと簡単です。

$1$ から $2^{M}-1$ 以下の整数を全てXORすると、0 になる

よって、ここから一つ $K$ という数字を外すと、XOR は $K$ になります。

ゆえに、数列を作る際は、 $K$ どうしの間は $K$ 以外の $1$ から $2^{M}-1$ 以下の整数を並べれば良いです。

例えば $M = 3$ 、 $K = 5$ の場合は、以下のようにすれば良いです。

0 1 2 3 4 6 7 5 7 6 4 3 2 1 0 5

これで大体答えですが、特殊なケースについて考えておきます。

$K = 0$ の場合は、隣どうし数字を並べたりすることで満たせます。

また、 $M=1$ 、 $K=1$ の場合は、このときは 0 と 1 しか使える数字がなく、どう並び替えても条件を満たす数列を作れません。この時は -1 を出します。

以上で、 $O(2^{M})$ で条件を満たす数列が作れました。

提出コード

from collections import deque

M, K = map(int, input().split())
if 2**M-1 < K:
    print(-1)
    return

if K == 0:
    ans = deque([])
    for i in range(2**M):
        ans.appendleft(i)
        ans.append(i)
    print(*ans)
    return

if M == 1:
    print(-1)
    return

ans = deque([K])
for p in range(0, 2**M):
    if p != K:
        ans.appendleft(p)
        ans.append(p)
ans.append(K)
    
print(*ans)