見出し画像

[ABC277 Python]大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277) A～C問題Python解説

Kai

ABC277のPython解説記事です。
ミス等ありましたらコメントにてご連絡いただけますと幸いです。

A問題

N, X = map(int, input().split())
P = list(map(int, input().split()))

for i in range(N):
    if P[i] == X:
        print(i+1)

1~Nの整数を並び替えたリストPの中で、
整数Xが何番目にあるか答えてね、
という問題でした。

リストPを先頭から見ていき、
整数Xが見つかったら、
何番目か出力すればいいです。
インデックス番号の扱いに注意して+1することを忘れないでくださいね。


B問題

N = int(input())
s1 = ["H", "D", "C", "S"]
s2 = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K",]
l = []
for i in range(N):
    S = list(input())
    if S[0] in s1 and S[1] in s2 and S not in l:
        l.append(S)
    else:
        print("No")
        exit()
print("Yes")

基本的にはNこの文字列について
3つの条件を満たすかどうかを全て見ていくことで解決できます。

では、3つの条件を見ていきましょう。

①すべての文字列に対して、1文字目はH , D , C , S のどれかである。

これは1文字目を取り出して、
H , D , C , Sのどれかに当てはまるかどうか判定します。
方法としてはリストs1にH , D , C , Sを入れておいて、
1文字目がs1に含まれるか？を判定すればいいでしょう。

②すべての文字列に対して、2文字目は A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , K のどれかである。

問題文からわかるように、①と同じですね。
リストs2に A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , T , J , Q , Kを入れておいて、
2文字目がs2に含まれるか？を判定すればいいでしょう。

③すべての文字列は相異なる。

これについては少し工夫が必要ですが、
文字列を読み込んだ時に、リストlに文字列を保存していきます。
それと同時に読み込んだ文字列がリストlにあるかどうか
を確認する必要があります。
もしリストlに存在していれば、③に反するのでNoを出力します。

①、②、③をすべて満たせば最後にYesを出力して終了です。

C問題

from collections import defaultdict, deque

N = int(input())
ladder = defaultdict(list)
for i in range(N):
    A, B = map(int, input().split())
    ladder[A].append(B)
    ladder[B].append(A)

reached = {1}
que = deque({1})

while que:
    now = que.pop()
    for i in ladder[now]:
        if i not in reached:
            reached.add(i)
            que.append(i)
print(max(reached))

所謂BFS・DFSと呼ばれる問題です。
AtCoderではよく出題される問題ですので、
注意が必要です。

まずは辞書型で、梯子の繋がりを保存していきましょう。
辞書型はdifaultdictで作っていきます。
梯子は双方向へ移動できますので、
梯子Aから移動できる階、梯子Bから移動できる階
をそれぞれ保存することで、
ある整数Xを用意すると、
X階から移動できる階を保存することができます。

続いて、実際に梯子を使いながら、
到達できる階を求めていきましょう。
先に言っておきますが、高橋君は1回から出発しますので、
梯子がかかっていたとしても必ずしも到達できるとは限りません。
その中で到達できる階の中で最大のものを出力するで回答となります。

まずはset()でreachedを作っておきます。
文字通り到達した階を表すもので、
先ほども言った通りこの中から最大のものを出力すればいいのですね。

次にdeque()を使って、
次に進む階を保存します。
deque()に関しては以下を参考にしてください。

例えば入力例2をご覧ください。
1回からスタートし、次に進める階は、
3,5,12となります。
この3つがqueに入ります。
これをqueをひとつずつ取り出して、
whileでqueがなくなるまで続けます。
次に3を取り出します。
3の次に進める階は、
1,5,12となります。
ただ、1は既に到達している(reachedに入っている)ので
実際にqueに追加するのは5と12です。

これを続けますと、到達した階reachedは増えていき、
queに追加する階は減っていきます。

最後に到達した階の中で、
最高のものをmax(reached)で出力します。

この記事が気に入ったらサポートをしてみませんか？