見出し画像

[ABC285 Python]AtCoder Beginner Contest 285 A～D問題Python解説

Kai

A問題

a, b = map(int, input().split())

lis = [(1,2),(2,4),(4,8),(4,9),(2,5),(5,10),(5,11),(1,3),(3,6),(6,12),(6,13),(3,7),(7,14),(7,15)]
if (a, b) in lis:
    print("Yes")
else:
    print("No")

繋がっている辺は14本しかありませんので、
全部列挙したほうがいいと思います。

繋がっている点を(小さい番号、大きい番号)でリストに保存し、
(a,b)がそのリストに存在するかどうかを確認します。

B問題

N = int(input())
S = input()

for i in range(1, N):
    ans = 0
    judge = False
    for k in range(N-i):
        # print(i,j)
        if S[k] != S[k+i]:
            ans = k+1
        else:
            break
    print(ans)

B問題にしては少し難しい問題ですね。

確認する変数はlとkの2つです。
まずはlについて。
問題文にも書いてありますが、
文字列Sのi番目とi+k(1<=k<=l)番目を比較することになりますので、必然的にkとlの値は決まってきます。

全てのiについて、lの値を考えていく訳ですが、
比較した文字が違うときのlの最大値なので、
比較した文字が等しいときにlの値を出力すれば、
題意を満たすlの値を出力できます。
比べる文字はS[k]とS[k+i]になります。

C問題

S = input()

string = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
# print(len(string))#26
ans = 0
# for i in range(1, len(S)):
#     ans += 26**i
# print(ans)
for i in range(len(S)):
    s = string.index(S[i])+1
    # print(s)
    ans += s*26**(len(S)-i-1)

print(ans)

文字列Sは英大文字のみから構成されているため、
文字列の長さから何問目かを考えていきましょう。

例えば入力例1のABであれば、
まず1文字目をA~Zまでカウントし、
次に2文字目をAA、ABとカウントすることでSにたどり着きます。

1文字目は26^1回、
2文字目は26^2回、
3文字目は26^3回…
となるので、
Sの長さがnだとすると、
最後の文字(ABだとしたらB)にたどり着くまでに、
26^(n-1)回かかるということになるわけです。

後は文字がA,B,Cと後ろに行くにつれ1回ずつ増えていくので、
各文字について、
「その文字がAから数えて何文字目か」×「26^(n-1)」を計算し、
答えに加算していくことで、求めることができます。

D問題

from collections import defaultdict

N = int(input())
d = defaultdict(str)
start = set()
for i in range(N):
    S, T = input().split()
    d[S] = T
    start.add(S)

visited = set()
for start_step in start:
    next_step = d[start_step]
    while next_step not in visited:
        visited.add(next_step)
        if next_step == "":
            break
        next_step = d[next_step]
        if next_step == start_step:
            print("No")
            exit()
print("Yes")

2023/01/21大変遅くなりましたが、追記しました。

ユーザー名を希望通り変更できない条件を見つけることが難しいですが、入力例2にNoとなる例が載っています。

3
a b
b c
c a

入力例2を見てみると、
a→b、b→c、c→aのように
どうやらa→aという感じでループすると条件を満たさないようです。

つまり、全てのユーザーから名前の変更をはじめて、
もしループになるような回があればNoと出力するということになります。

ループを探す手法は様々ありますが、
今回はシンプルにwhileのみで書いていきます。

先程記載した通り、すべてのユーザーを見ていけばいいのですが、
もちろんこれではTLEになりますので、工夫が必要です。

工夫する箇所を説明します。
入力例3をご覧ください。

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

まずはユーザー1から見ていくと
aaa→bbb→ccc→ddd
となります。
ここまでループはなさそうです。
次にちょっと飛ばしてユーザー5をご覧ください。
ユーザー5は
bbb→ccc→ddd
となりますね。

お気づきになったかもしれませんが、
ユーザー5は既にユーザー1の時に見ているので、
別に調べなくていいということが分かります。

つまり、よくDFS等で見られますが、
既に見たユーザー名は保存しておいて、
二重で調べないようにするというのが今回の工夫する点です。

では、実際にスクリプトに書き起こします。
ユーザー名の変更希望は辞書型で保存しておきましょう。
そして元のユーザー名を全て調べるので、start変数に保存しておきます。

さらに、先ほどお伝えした既に見たユーザー名を保存するために
変数visitedをset型で作っておきます。

あるユーザー名start_stepを取得し、
取得したユーザー名のユーザーが希望する新ユーザー名next_stepも同時に取得します。
next_stepはこれから調べるので、visitedに追加します。
ここで、next_stepがユーザー名のユーザーいなければ、終了します。
次のユーザがいれば、新たにnext_stepを更新します。

最後に最初に取得したstart_stepと一致しているかを確認し、
一致している場合はループが確認できるので、Noと判断するというプログラムになります。


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