🔙
🔝

【paiza問題集 解説】
paizaの森練習問題コンテスト過去問題セット13

先頭が一致

先頭が一致

  • 例１

    • a = input()
b = input()

print('Yes' if b[:len(a)] == a else 'No')
print('Yes' if a[:len(b)] == b else 'No')

  • 例２

    • import re

a = input()
b = input()

ans1 = re.search(rf"^{a}", b)
print('Yes' if ans1 else 'No')

ans2 = re.search(rf"^{b}", a)
print('Yes' if ans2 else 'No')

    問題の途中の a というのが 文字列 a のことで、勝手に 'a' かと勘違いし、問題の意味がよくわからずに一匹悩んでいました。😹

    r"" と f"" の両方を合わせて rf"" と書くと、２つの機能が使えるようになります。パターンの書き方が複雑になりますけど。😅

合計と平均

合計と平均

    n = int(input())
a = [int(input()) for _ in range(n)]

sum_ = sum(a)

print(sum_)
print(int(sum_ / n))
# print(sum_ // n)
二等辺三角形

二等辺三角形

    a = int(input())
b = int(input())
c = int(input())

print('Yes' if a == b or a == c or b == c else 'No')

    「正三角形」も二等辺三角形に含まれます。

飽き性

飽き性

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

case1 = min(a, b)
case2 = abs(a - b) // 2

print(case1, case2)

    条件に『 a + b は偶数』とありますので、余りの心配をすること無く求められます。


    奇数だったら食料廃棄になるプログラム。😅

占い - その 2

占い - その 2

    n = int(input())
m_sum = sum(map(int, input().split()))

print('Yes' if m_sum % 7 == 0 else 'No')

    『総和』 → 全部足す
    『７の倍数』 → 7 で割った余りが 0

連結判定

連結判定

    import sys

def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

# 再帰制限 1000回 → 100000回
sys.setrecursionlimit(10**5)

n, m = map(int, input().split())
graph = {i+1: [] for i in range(n)}

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

unvisited = {i+1 for i in range(n)}
dfs(min(graph.keys()))

print('No' if unvisited else 'Yes')

    ※ 再帰回数制限を１０万回以上に変更しないと100点取れません。💦

    まずは大まかな手順から。

    1. 入力データからグラフを作成する
    2. 一番若い番号の頂点から再帰を開始する
    3. 辺を順番に通り、訪問した頂点を訪問リストから削除していく
    4. 全ての行き止まりを訪問したら再帰を終了する
    5. 訪問リストが空なら連結

    分岐に分岐を重ねられるとイメージするのが難しくなりますね。😓

    1.【入力データからグラフを作成する】

    n, m = map(int, input().split())
graph = {i+1: [] for i in range(n)}

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    n = 頂点の総数
    m = 辺の総数

    a = 頂点の番号
    b = a に隣接する頂点の番号
    graph = {頂点の番号: 隣接する頂点の番号}

    これらを基に隣接リストでグラフを作ります。


    graph = {i+1: [] for i in range(n)}

    グラフの空の情報を辞書で作っておきます。


    for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

    入力を基にグラフを作っていきます。入力は辺の情報です。頂点 a から 頂点 b に向かって辺で繋がれているということです。

    a → b

    graph = {a: [b]}

    無向グラフを作るので、どちらからでも通行できるようにします。

    a → b graph[a].append(b)
    b → a graph[b].append(a)

    graph = {a: [b], b: [a]}

    これを問題の入力例を使って作ると次のようになります。


    1
    4 3 ← n m
    1 2
    2 3
    3 4

    graph = {頂点の番号: 隣接する頂点の番号}
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    １─２
    　／
    ３─４


    2
    4 3 ← n m
    1 2
    2 3
    4 4

    graph = {頂点の番号: 隣接する頂点の番号}
    graph = {1: [2], 2: [1, 3], 3: [2], 4: [4]}

    １─２
    　／
    ３　４


    作成したこの隣接リストを使ってこの後から、頂点を踏み荒らしていきます。👿

    2.【一番若い番号の頂点から再帰を開始する】

    unvisited = {i+1 for i in range(n)}
dfs(min(graph.keys()))

    unvisited は未踏の頂点のリスト(set型)を意味しています。頂点を踏んだら消していきます。最終的にこの中身が空になったら、全ての頂点が連結しているということになります。

    今回は隣接リストを１番から作っていますので、この様に書いても１番確定なのですが、一応。😅


    dfs(1)

    でもOK。


    いよいよ再帰関数が始まります。

    3.【辺を順番に通り、訪問した頂点を訪問リストから削除していく】

    import sys

def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

# 再帰制限 1000回 → 100000回
sys.setrecursionlimit(10**5)

    sys モジュールをインポートして再帰の回数制限をデフォルトの1000回から１０万回に引き上げます。

    引数の v は、現在踏んでいる頂点の番号です。

    初めに訪問した現在の頂点番号を unvisited から除去します。


    for i in graph[v]:
    if i in unvisited:
        dfs(i)
    return

    ここが再帰する所です。現在いる頂点と隣接する頂点を 文で順番に訪問していきます。unvisited に、次に訪問する頂点 i が含まれる、つまり頂点 i が踏んだことのない頂点の時は、次にその頂点へ向かいます。ここで dfs(i) を呼びます。


    graph = {頂点の番号: 隣接する頂点の番号}
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    １─２
    　／
    ３─４


    v = 1
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    😺─２
    　／
    ３─４

    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):
    unvisited.remove(1)  ← 今ココ
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return
    ↓ unvisited = {1, 2, 3, 4}
    def dfs(1):
    unvisited.remove(1)
    for i in graph[1]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ graph[1] = [2]
    def dfs(1):
    unvisited.remove(1)
    for 2 in [2]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ 2 は未訪問？
    def dfs(1):
    unvisited.remove(1)
    for 2 in [2]:
        if 2 in {2, 3, 4}:  ← 今ココ
            dfs(i)
    return
    ↓ 2 は未訪問
    def dfs(1):
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)  ← 今ココ
    return
    ↓ dfs(2) を呼び出す


    v = 2
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    １─😺
    　／
    ３─４

    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 待機中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)
    return

    def dfs(2):            # 実行中
    unvisited.remove(2)  ← 今ココ
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return
    ↓ unvisited = {2, 3, 4}
    def dfs(2):
    unvisited.remove(2)
    for i in graph[2]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ graph[2] = [1, 3]
    def dfs(2):
    unvisited.remove(2)
    for 1 in [1, 3]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ 1 は未訪問？
    def dfs(2):
    unvisited.remove(2)
    for 1 in [1, 3]:
        if 1 in {3, 4}:  ← 今ココ
            dfs(i)
    return
    ↓ 1 は訪問済みなので False
    def dfs(2):
    unvisited.remove(2)
    for 1 in [1, 3]:
        if False:  ← 今ココ
            dfs(i)
    return
    ↓
    def dfs(2):
    unvisited.remove(2)
    for 3 in [1, 3]:  ← 今ココ
        if i in {3, 4}:
            dfs(i)
    return
    ↓ 3 は未訪問？
    def dfs(2):
    unvisited.remove(2)
    for 3 in [1, 3]:
        if 3 in {3, 4}:  ← 今ココ
            dfs(i)
    return
    ↓ 3 は未訪問
    def dfs(2):
    unvisited.remove(2)
    for 3 in [1, 3]:
        if True:
            dfs(3)  ← 今ココ
    return
    ↓ dfs(3) を呼び出す


    v = 3
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    １─２
    　／
    😺─４

    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 待機中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)
    return

    def dfs(2):            # 待機中
    unvisited.remove(2)
    for 3 in [1, 3]:
        if True:
            dfs(3)
    return

    def dfs(3):            # 実行中
    unvisited.remove(3)  ← 今ココ
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return
    ↓ unvisited = {3, 4}
    def dfs(3):
    unvisited.remove(3)
    for i in graph[3]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ graph[3] = [2, 4]
    def dfs(3):
    unvisited.remove(3)
    for 2 in [2, 4]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ 2 は未訪問？
    def dfs(3):
    unvisited.remove(3)
    for 2 in [2, 4]:
        if 2 in {4}:  ← 今ココ
            dfs(i)
    return
    ↓ 2 は訪問済みなので False
    def dfs(3):
    unvisited.remove(3)
    for 2 in [2, 4]:
        if False:  ← 今ココ
            dfs(i)
    return
    ↓
    def dfs(3):
    unvisited.remove(3)
    for 4 in [2, 4]:  ← 今ココ
        if i in {4}:
            dfs(i)
    return
    ↓ 4 は未訪問？
    def dfs(3):
    unvisited.remove(3)
    for 4 in [2, 4]:
        if 4 in {4}:  ← 今ココ
            dfs(i)
    return
    ↓ 4 は未訪問
    def dfs(3):
    unvisited.remove(3)
    for 4 in [2, 4]:
        if True:
            dfs(4)  ← 今ココ
    return
    ↓ dfs(4) を呼び出す


    v = 4
    graph = {1: [2], 2: [1, 3], 3: [2, 4], 4: [3]}

    １─２
    　／
    ３─😺

    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 待機中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)
    return

    def dfs(2):            # 待機中
    unvisited.remove(2)
    for 3 in [1, 3]:
        if True:
            dfs(3)
    return

    def dfs(3):            # 待機中
    unvisited.remove(3)
    for 4 in [2, 4]:
        if True:
            dfs(4)
    return

    def dfs(4):            # 実行中
    unvisited.remove(4)  ← 今ココ
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return
    ↓ unvisited = {4}
    def dfs(4):
    unvisited.remove(4)
    for i in graph[4]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ graph[4] = [3]
    def dfs(4):
    unvisited.remove(4)
    for 3 in [3]:  ← 今ココ
        if i in unvisited:
            dfs(i)
    return
    ↓ 3 は未訪問？
    def dfs(4):
    unvisited.remove(4)
    for 3 in [3]:
        if 3 in {}:  ← 今ココ
            dfs(i)
    return
    ↓ 3 は訪問済みなので False
    def dfs(4):
    unvisited.remove(4)
    for 3 in [3]:
        if False:
            dfs(i)
    return  ←←←←←← 今ココ
    ↓ return で呼び出し元に戻る

    4.【全ての行き止まりを訪問したら再帰を終了する】

    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 待機中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)
    return

    def dfs(2):            # 待機中
    unvisited.remove(2)
    for 3 in [1, 3]:
        if True:
            dfs(3)
    return

    def dfs(3):            # 実行中
    unvisited.remove(3)
    for 4 in [2, 4]:
        if True:
            None    ← ココ
    return

    --- dfs(4) は破棄された ---

    １─２
    　／
    😺─４

    ↓


    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 待機中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            dfs(2)
    return

    def dfs(2):            # 実行中
    unvisited.remove(2)
    for 3 in [1, 3]:
        if True:
            None    ← ココ
    return

    --- dfs(3) は破棄された ---

    １─😺
    　／
    ３─４

    ↓


    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    def dfs(1):            # 実行中
    unvisited.remove(1)
    for 2 in [2]:
        if True:
            None    ← ココ
    return

    --- dfs(2) は破棄された ---

    😺─２
    　／
    ３─４

    ↓


    def dfs(v):
    unvisited.remove(v)
    for i in graph[v]:
        if i in unvisited:
            dfs(i)
    return

    unvisited = {}
None  # ← 最後はココに戻る

    --- dfs(1) は破棄された ---

    🐈
    １─２
    　／
    ３─４

    5.【訪問リストが空なら連結】

    unvisited = {}  # ← 空は False
None

print('No' if unvisited else 'Yes')
    Yes

    unvisited が空なので False となり、画面に Yes が出力されます。



    入力例2 の場合は、頂点４が残るので No になります。

    unvisited = {4}

    🐈
    １─２
    　／
    ３　４

    以上です。

    再帰のところを長々と書いたせいで却ってわかりにくくなってしまったかもしれませんが😅、こんな感じで処理をします。