見出し画像

[ABC293 Python]AtCoder Beginner Contest 293A～D問題Python解説

Kai

前回からスクリプトにコメントアウトで解説文を挿入しています。
前より見にくい等ありましたらご連絡いただけると幸いです。

A問題

# 入力
S = list(input())
# 指示通りに入れ替えを行う
for i in range(1, len(S)//2+1):
    S[2*i-2], S[2*i-1] = S[2*i-1], S[2*i-2]
# リスト型→文字列型にして出力
print("".join(S))

問題文が少し読み取りづらいですが、
入れ替える操作を|S|/2回行った後、
文字列Sを出力します。

入力は文字列型ですが、
Pythonでは文字列型の一部分を入れ替えることができませんので、
入力をリスト型で行い、
最後に文字列型に戻してあげることで、
回答することができます。

B問題

# 入力
N = int(input())
A = list(map(int, input().split()))
# 人_について、呼ばれたか呼ばれてないかを保存するリスト
called = [False for _ in range(N)]
# 人iについて、iが呼ばれていなければ人Aiの番号を呼ぶ
for i in range(N):
    if not called[i]:
        called[A[i]-1] = True

# 呼ばれていない人の人数を出力
print(called.count(False))
# 人iについて、iが呼ばれていなければiの番号を出力
for i in range(N):
    if not called[i]:
        # 空白区切りにはend=" "を使う
        print(i+1, end = " ")

この問題も指示通りにプログラムを作っていきましょう。

まずはcalledというリストにN人分の変数を入れておきます。
これは呼ばれているか呼ばれていないかを表すので、
最初は全員Falseつまり呼ばれていないことになります。

次に、入力されたリストAを見て、
問題文の操作を行います。
先程作ったcalledをその都度確認し、
FalseだったらAiの番号の人をTrueとします。

最後にFalseの人の人数を出力し、
続いてFalseの人の番号も順番に出力することで、
回答することができます。

C問題

# インポート
import itertools
# 入力
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
# 答えans
ans = 0
# 右に移動する回数+下に移動する回数=H+W-2
alllist = [_ for _ in range(H+W-2)]
# alllistの中から下に何回目に下に移動するかを決める
for i in itertools.combinations(alllist, H-1):
    # 通ったマス
    passed = set()
    # 始点
    x = 0
    y = 0
    # 始点は既に通っている
    passed.add(A[x][y])
    # (H+W-2)回移動する中で
    for j in range(H+W-2):
        # j回目が下に移動する回であればx+=1
        if j in i:
            x += 1
        # j回目が右に移動する階であればy+=1
        else:
            y += 1
        # 移動したマスを通ったマスに記録する
        passed.add(A[x][y])  
    # 移動し終えたら、通ったマスと移動した回数を比較し、
    # 通ったマス=移動した回数だったら答えに1加える
    if len(passed) == H+W-1:
        ans += 1
# 最後に答えを出力する
print(ans)

マス目の問題はAtcoderで頻出ですので、
慣れておきましょう。

今回のポイントは
「どのように移動したとしても、右に(W-1)回、下に(H-1)回、合計(W+H-2)回移動する」
ということです。
このポイントを踏まえると、
全(W+H-2)回のうち
「下に移動するのは何回目か？」
を調べることで、
それ以外の時は右に移動することが分かります。

移動はリストalllistに入っている回数分行います。
その中から(H-1)回選び、
その回を下に移動する回とします。
これを全通り試し、
通ったマスに書かれた整数がすべて異なる、
つまり、
通ったマスに書かれた整数の種類=移動回数(W+H-2)
が成り立つ経路の個数を保存し出力します。

D問題

# インポート
from collections import defaultdict

# UnionFind
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())
# 0~Nまでを適用する
UF = UnionFind(N)
# 環状になっているものの個数
ans_loop = 0

for i in range(M):
    # 入力
    A, B, C, D = input().split()
    # AとCはインデックス用に-1して整数型に
    A = int(A) - 1
    C = int(C) - 1
    # ループ判定
    if UF.same(A, C):
        ans_loop += 1
    # グループ併合
    UF.union(A, C)
# 環状になっているものの個数、全体から前者を引いたもの
print(ans_loop, UF.group_count()-ans_loop)

2023/03/12追記しました。

一見初見のように見えますが、
環状・結ばれている…のような表現から、
先週のこの問題が見えてきます。

先週の解説の時にも記載しましたが、
この問題では頂点数と辺数が等しい、
つまり環状が含まれているものをカウントするという問題でした。
今回の問題もこの手法を使って解くことができます。

いつもグラフではDFSを使っていますが、
今回はUnionFindを使ってみたいと思います。

UnionFindは以下の記事を参考にしてください。

UnionFindについて、使い慣れていない方は、
組み込み関数だと思って、先ほどのページからコピペしていただいて構いません。
(私の解答もコピペしてあります。)

それでは実際に環状になっているものの数を数えていきたいと思います。
M個の辺(ロープ)を順番に見ていき、
その辺より前に既に辺が繋がっていれば、
その辺でつなぐことによって、円が完成されるので、
環状になっていると判断することができます。

入力例3で確認してみましょう。

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

辺：
ans_loop = 0
①5と3は繋がってない。
辺：53
ans_loop = 0
②7と4は繋がってない
辺：53,74
ans_loop = 0
③4と1は繋がってない
辺：53,741
ans_loop = 0
④2と3は繋がっていない
辺：532,741
ans_loop = 0
⑤2と5は繋がっている
辺：532,741
ans_loop = 1
⑥1と7は繋がっている
辺：532,741
ans_loop = 2

このようにしてUnionFindで環状を探すことができました。
連結成分の個数は
UF.group_count()
で確認できるので、
環状がない(木である)個数は
UF.group_count()-ans_loop
となります。


いいなと思ったら応援しよう！