[ABC287 Python]ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287) A～D問題Python解説

A問題

A - Majority

N = int(input())
S = [input() for _ in range(N)]
if S.count("For") > S.count("Against"):
    print("Yes")
else:
    print("No")

N人の賛成反対それぞれの人の数を数えればいいので、
リスト.count(要素)
を使います。
賛成の人 = S.count("For")
反対の人 = S.count("Against")
を比較して賛成の人の方が多いときにYesと出力します。
制約からNは奇数なので同点がないことに注意が必要です。

B問題

B - Postal Card

N, M = map(int, input().split())
S = [input() for _ in range(N)]
T = [input() for _ in range(M)]
ans = 0
for i in S:
    if i[-3:] in T:
        ans += 1
print(ans)

文字列の比較は計算量がかかりますが、
今回は制約が少ないので、
単純に比較で実装できそうです。

問題文より
Sの末尾3文字がTのいずれかになっている個数を出力しろ
ということだったので、
その条件を満たす場合はansという変数を+= 1することで、
個数をカウントすることができます。

末尾3文字をどのように表記するかには
いろいろな考え方がありますが、
インデックスの特性から、
文字列の一番最後がindex = -1になるので、
末尾3文字は「文字列[-3:]」と表せますね。

C問題

C - Path Graph?

import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
rode = [[] for _ in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    rode[u].append(v)
    rode[v].append(u)

# グラフが連結かどうか
visited = [False for _ in range(N)]
def dfs(now):
    visited[now] = True
    for i in rode[now]:
        if not visited[i]:
            dfs(i)
dfs(0)
if not all(visited):
    print("No")
    exit()

# 頂点の次数が2以下、1が2個
c = 0
for i in rode:
    if len(i) == 1:
        c += 1
    elif len(i) != 2:
        print("No")
        exit()

if c == 2:
    print("Yes")
else:
    print("No")

リストrodeに辺の情報を保存しておきます。

パスグラフというのはグラフが一直線になるものをいうみたいです。
そこで、パスグラフとなる条件は以下の3つが考えられます。

①すべての辺が連結している。
これはグラフの条件ですね。

②すべての頂点に対して辺が2本以下である。
①よりすべての頂点に対して辺は1本以上であることは確定です。
もし3本以上だと、グラフが一直線にはならないので、この条件が必要です。

③辺の数が1本の頂点が2点ある。
これは入力例3のようなサイクルにならないようにするための条件です。
グラフの端の2点が辺の数が1本になります。

では、1つずつ条件を見てみましょう。
①
連結かどうかはDFSやBFS、UnionFindなど様々やり方がありますが、
ABCでは頻出なのでよく復習しておくことをお勧めします。

スクリプトのDFSでは、
頂点０(インデックスの関係で1→0となります。)から、
到達した地点をTrueにして、全ての地点に到達できたかを
確認します。
これで到達できない地点があったとすると、
連結ではないので、この時点でNoと出力します。

②
rodeからlen(rode[i])で頂点iから伸びている辺の数を取得できます。
全ての頂点に対して、
辺の数が1であれば、変数cにカウントアップします。
それ以外で、辺の数が2でない場合、
3以上であることが確定するので、
この時点でNoと出力します。

③
ここまでの条件を満たしていれば、
最後にcの値を確認します。
cの値が2であればYes、それ以外はNoです。

D問題

D - Match or Not

S = input()
T = input()
 
start = [False for _ in range(len(T)+1)]
end = [False for _ in range(len(T)+1)]
start[0] = True
end[0] = True
 
for i in range(len(T)):
    if S[i] == T[i] or S[i] == "?" or T[i] == "?":
        start[i+1] = True
    else:
        break
 
for i in range(1, len(T)+1):
    if S[-i] == T[-i] or S[-i] == "?" or T[-i] == "?":
        end[i] = True
    else:
        break
 
for i in range(len(T)+1):
    if start[i] and end[-i-1]:
        print("Yes")
    else:
        print("No")

2023/01/31掲載しました。

実際に文字列を移動させたりするとTLEになりますので、
工夫する必要があります。

入力例1だと少し文字列の長さが足りないので、
入力例3を見ていきましょう。

S = beginner
T = contest

まずは問題文のとおりに考えていきます。
S′を作るんでしたね。
x = 0,1,….|T|に対して、x番目のS′をS'xとします。

S'0 = ginner
S'1 = binner
S'2 = benner
S'3 = begner
S'4 = begier
S'5 = beginr
S'6 = beginn

ここまではよろしいでしょうか？
次にS'xの文字列をインデックスで表したいと思います。
問題文からSの先頭のx文字として取ったものと、
末尾の|T|-x文字として取ったものがありますが、
後者の方は-i、つまり文字列の後方からとったものとして、
インデックスで表していきます。
わかりやすいように","で区切りますね。

S'0 = -6,-5,-4,-3,-2,-1
S'1 = 0,-5,-4,-3,-2,-1
S'2 = 0,1,-4,-3,-2,-1
S'3 = 0,1,2,-3,-2,-1
S'4 = 0,1,2,3,-2,-1
S'5 = 0,1,2,3,4,-1
S'6 = 0,1,2,3,4,5

ここで1つ気付くことがあります。
S'xをインデックスで表すと、
「-|T|~|T|」の間の整数のみで表すことができました。

このことから、
-|T|~|T|の間で、SとTを比較して、
一致させることができるかどうかを保存しておけば、
問題なく答えにたどり着けそうです。

それでは、スクリプトを見ていきましょう。
startは前から見たもの、
endは後ろから見たもの、
と考えてください。

まずは、i = 0~|T|の範囲を前から見ていきます。
S[i]とT[i]が同じ、もしくはどちらかが？の時、
一致させることができるので、Trueに変換しておきます。

ここで、start[0]は
文字列の0番目ということではなく、
前からは1文字もとらなかったということです。
(先ほどの例で言えば、S'0が当てはまります。）

もしここで、上記の条件を満たさない箇所があったとすれば、
ここで終了します。
S = abaa
T = aaa
でS[i]!=Tとなった時点で、
このSとTは変換不可能となるからです。

同じようにi = -1~-|T|の範囲についても見ていきます。
この説明は省略します。

最後にYesNo判定です。
startつまり前から取ってきたものと
endつまり後ろから取ってきたものの全てが
Trueつまり変換可能であれば、
S'とTがマッチします。
それ以外はマッチしません。