ABC350 with Python (A～F)

ABC350のA~F問題をpythonで解説していきます。

A - Past ABCs

問題

長さ $6$ の文字列 $S$ が与えられます。$S$ の先頭 $3$ 文字は ABC であり、末尾 $3$ 文字は数字であることが保証されます。

$S$ が、このコンテスト開始以前に AtCoder 上で開催され終了したコンテストの略称であるかどうか判定してください。

ただし、文字列 $T$ が「このコンテスト開始以前に AtCoder 上で開催され終了したコンテストの略称」であるとは、以下の $348$ 個の文字列のうちいずれかに等しいことと定めます。

ABC001, ABC002, $\ldots$, ABC314, ABC315, ABC317, ABC318, $\ldots$, ABC348, ABC349

特に ABC316 が含まれないことに注意してください。

考察

素直に今まで開催された会をリストに入れて、文字列Sがそこに含まれているかを確認するのが楽だと思います。ここで、1を001などとするときには、(str型).zfill(長さ)を使うと便利です。

コード

A.py

candi = []
for i in range(1, 350):
    if i == 316:
        continue
    candi.append("ABC" + str(i).zfill(3))
S = input()
if S in candi:
    print("Yes")
else:
    print("No")

B - Dentist Aoki

問題

高橋君には、穴 $1,2,\dots,N$ に $1$ 本ずつ、全部で $N$ 本の歯が生えています。
歯医者の青木君は、これらの歯と穴に対して、 $Q$ 回の治療を行います。
$i$ 回目の治療では、穴 $T_i$ を治療します。治療内容は次の通りです。

• 穴 $T_i$ に歯が生えている場合、穴 $T_i$ から歯を抜く。
• そうでない (穴 $T_i$ に歯が生えていない) 場合、穴 $T_i$ に歯を生やす。

全ての治療が終わった後、高橋君に生えている歯の本数は何本ですか?

考察

歯を抜いたと思ったらまた生やす...といった特殊な問題です。2つの状態を行ったり来たりするので、1のXOR(排他的論理和)をとると楽です。(操作によって、0なら1に、1なら0に変化するため)
最後は元の歯の本数から抜けている部分の個数を引けば答えとなります。

コード

B.py

N, Q = map(int, input().split())
T = list(map(int, input().split()))
hanuke = [0] * (N + 1)
for t in T:
    hanuke[t] ^= 1
print(N - hanuke.count(1))

C - Sort

問題

$(1,2,\ldots,N)$ の並び替えである数列 $A=(A_1,\ldots,A_N)$ が与えられます。
次の操作を $0$ 回以上 $N-1$ 回以下行うことで、$A$ を $(1,2,\ldots,N)$ にしてください。

• 操作：$1\leq i < j \leq N$ を満たす整数の組 $(i,j)$ を自由に選ぶ。$A$ の $i$ 番目と $j$ 番目の要素を入れ替える。

なお、制約の条件下で必ず $A$ を $(1,2,\ldots,N)$ にできることが証明できます。

考察

最初から1,2,...と昇順になるように入れ替えるとすると、最悪でN-1回入れ替えが必要ですが、これは制約を満たすのでそれをそのまま実装すればよいです。
とはいえ、毎回1がどこにあるのか、2がどこにあるのか...とチェックし直していると$O(N^2)$となってしまうので、ある数字がどのインデックスにあるかを保持しておく必要があることに注意が必要です。

コード

C.py

N = int(input())
A = list(map(int, input().split()))
place = [-1] * (N + 1)
for i, a in enumerate(A):
    place[a] = i

ans = []
for i in range(N):
    if A[i] != i + 1:
        targ = place[i + 1]
        A[i], A[targ] = A[targ], A[i] # この書き方大好きです.
        place[A[targ]] = targ
        ans.append((i + 1, targ + 1))
print(len(ans))
for a, b in ans:
    print(a, b)

D - New Friends

問題

1 から $N$ の番号がついた $N$ 人のユーザが利用している SNS があります。

この SNS では $2$ 人のユーザが互いに友達になれる機能があります。
友達関係は双方向的です。すなわち、ユーザ $X$ がユーザ $Y$ の友達であるならば、必ずユーザ $Y$ はユーザ $X$ の友達です。

現在 SNS 上には $M$ 組の友達関係が存在し、$i$ 組目の友達関係はユーザ $A_i$ とユーザ $B_i$ からなります。

以下の操作を行える最大の回数を求めてください。

• 操作：3 人のユーザ $X$, $Y$, $Z$ であって、$X$ と $Y$ は友達、$Y$ と $Z$ は友達であり、$X$ と $Z$ は友達でないようなものを選ぶ。$X$ と $Z$ を友達にする。

考察

この問題のように現実で出来たら、友達100人どころか80億人も夢じゃないと思うと面白いですね(ﾟ∀ﾟ)(六次の隔たりというやつです)。

さて、友達の友達も友達にするということですから、例えばn人の閉じた友達ネットワークがあるなら、友達同士を辺でつないだグラフとしてみたとき、$\binom{n}{2}$本の辺が引けます(全員友達同士になるということ)。今回は、重複せず追加で何本辺を引くことができるかという問題に言い換えられるので、n人からなる閉じた友達ネットワークを見つけたら$\binom{n}{2}$を足し、最後に既に引かれていた辺の本数Mを引けば答えとなります。閉じた友達ネットを見つけるのにはUnionFindを用いました。

コード

D.py

from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, 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, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):  # 多用すると重い
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return "\n".join(f"{r}: {m}" for r, m in self.all_group_members().items())


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
ans = 0
for key, val in uf.all_group_members().items():
    num = len(val)
    ans += num * (num - 1) // 2
print(ans - M)

E - Toward 0

問題

整数 $N$ が与えられます。あなたは次の $2$ 種類の操作を行うことができます。

• $X$ 円払う。$N$ を $\left\lfloor\frac{N}{A}\right\rfloor$ に置き換える。
• $Y$ 円払う。$1$ 以上 $6$ 以下の整数が等確率で出るサイコロを振る。その出目を $b$ としたとき、$N$ を $\left\lfloor\frac{N}{b}\right\rfloor$ に置き換える。

ここで $\lfloor s \rfloor$ は $s$ 以下の最大の整数を表します。例えば $\lfloor 3 \rfloor=3$、$\lfloor 2.5 \rfloor=2$ です。

適切に操作を選択したとき、$N$ を $0$ にするまでに払う必要がある金額の期待値の最小値を求めてください。
なお、サイコロの出目は操作ごとに独立であり、操作の選択はそれまでの操作の結果を確認してから行うことができます。

考察

これはぱっと見再帰で解けそうですが、出目が1のときループしてしまう点に注意が必要です。こういう時は、1回あたりのお値段を少し高くして、出目1がでないサイコロにしてしまうと楽です。(下記のリンクを参照)

コード

E.py

from functools import lru_cache

N, A, X, Y = map(int, input().split())
Y = Y * 6 / 5


@lru_cache(maxsize=None)
def dfs(n):
    if n == 0:
        return 0
    res = dfs(n // A) + X
    tmp = 0
    for b in range(2, 7):
        tmp += (dfs(n // b) + Y) / 5
    res = min(res, tmp)
    return res

print(dfs(N))

F - Transpose

問題

英大小文字と ( ) からなる文字列 $S=S_1 S_2 S_3 \dots S_{|S|}$ が与えられます。
文字列 $S$ 中の括弧は、対応が取れています。

次の操作を、操作ができなくなるまで繰り返します。

1. まず、以下の条件を全て満たす整数組 $(l,r)$ をひとつ選択する。
   • $l < r$
   • $S_l = ($
   • $S_r = )$
   • $S_{l+1},S_{l+2},\dots,S_{r-1}$ は全て英大文字または英小文字である
2. $T=\overline{S_{r-1}S_{r-2} \dots S_{l+1}}$ とする。
   • 但し、 $\overline{x}$ は $x$ の大文字と小文字を反転させた文字列を指す。
3. その後、 $S$ の $l$ 文字目から $r$ 文字目までを削除し、削除した位置に $T$ を挿入する。

詳細は入出力例を参照してください。

上記の操作を使って全ての ( ) を除去することができ、最終的な文字列は操作の方法や順序によらないことが証明できます。
このとき、最終的な文字列を求めてください。

「 $S$ 中の括弧の対応が取れている」とは?

まず、正しい括弧列を次の通り定義します。

• 正しい括弧列とは、以下のいずれかの条件を満たす文字列です。
  • 空文字列
  • ある正しい括弧列 $A$ が存在して、 ( , A, ) をこの順に連結した文字列
  • ある空でない正しい括弧列 $A,B$ が存在して、 $A,B$ をこの順に連結した文字列

$S$ 中の括弧の対応が取れているとは、 $S$ 中の ( ) を順序を保って抜き出した時、それが正しい括弧列となることを指す。

考察

( )に囲まれた部分の中身を順番・大文字小文字ともに入れ替えるので、偶数回( )に囲まれた文字はそのままに、奇数回囲まれた文字のみ一度この入れ替えの操作を行えばよいです。逆に、何度もこの操作をするとTLEしてしまいます。今回は再帰で実装し、今どの範囲を見ているかと、XORを使って今( )に何回囲まれたかをチェックしました。ここで、大文字と小文字を入れ替える操作には(str型).swapcase()を使うと楽に実装できます。また、事前計算でどの位置の(がどの位置の)と対応しているかをdequeを使って求めています。

コード

F.py

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(int(1e7))

S = list(input())
pare = defaultdict(int)
r_pare = defaultdict(int)
q = deque()
for i, s in enumerate(S):
    if S[i] == "(":
        q.append(i)
    elif S[i] == ")":
        pre = q.pop()
        pare[pre] = i
        r_pare[i] = pre

ans = []


def dfs(l, r, d):
    if d == 0:
        i = l
        while i <= r:
            if S[i] == "(":
                dfs(i + 1, pare[i] - 1, d ^ 1)
                i = pare[i] + 1
            else:
                ans.append(S[i])
                i += 1
    else:
        i = r
        while l <= i:
            if S[i] == ")":
                dfs(r_pare[i] + 1, i - 1, d ^ 1)
                i = r_pare[i] - 1
            else:
                ans.append(S[i].swapcase())
                i -= 1


dfs(0, len(S) - 1, 0)
print("".join(ans))