(ABC287)A-C問題のpythonでの解法

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC287のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム

DFS (深さ優先探索)　　　　　　　・・・　問題C

今回の参加コンテスト(ABC287)
感想

今回の参加コンテスト(ABC287)

AtCoder Beginner Contest 287

A問題：Majority

A – Majority

問題(要約)

N人(奇数)の過半数が賛成か反対かを判定する

解答

# 番号1
n=int(input())
S=[input() for _ in range(n)]

# 番号2
if S.count("For") > n//2:
    print("Yes")
else:
    print("No")

考え方 (下の番号は、コード内のコメント番号と連携している)

入力nを受け取る
- 入力nは整数のため、input()で受け取り、整数型(int)に変換(キャスト)を行っている
- Sは n 行に渡って入力されるため、内包表記を用いて取り込む
  ＊ 1行でfor文を取り込める便利な機能
  - input()で入力を受け取る
  - その後のfor文で input() 動作を n回繰り返し、リスト化[ ] できる
if文を用いて下記の条件式が成り立つかを判断する
- 条件式：配列S内のForの数が、n 割る 2 の商の値より大きいかどうか
  - count関数で配列からカッコ内( For )の数を数える
  - n // 2は、nを2で割った商の部分を指す
  - nの半分よりも大きい、つまり、Forが過半数を占める時条件式が成り立つ
    - 上記の条件式が成り立つときは、
      - print関数で Yes を出力する
    - 成り立たない時、つまり、Against の方が多い時は、
      - print関数で No を出力する

＊内包表記を使わずにリストSを作る方法

S=[]
for _ in range(n):
    S.append(input())

空リストSを準備して、入力を受け取り、Sに追加していく。

3行かかるところを、内包表記なら1行 S=[input() for _ in range(n)] で対応できる

B問題：Postal Card

B – Postal Card

問題(要約)

数字のみからなる長さ6の文字列SがN個と数字のみからなる長さ3の文字列TがM個与えられている。N個の文字列Sの末尾3文字がM個の文字列Tのいずれかと一致する数を数える

解答

# 番号1
n,m=map(int,input().split())
S=[input()[-3:] for _ in range(n)]
T={input() for _ in range(m)}

# 番号2
cnt=0

# 番号3
for s in S:
    if s in T:
        cnt+=1

# 番号4
print(cnt)

考え方(下の番号は、コード内のコメント番号と連携している)

入力を受け取る
- 空白区切りの入力N, M
  - input()で入力を受け取る
  - split()で空白区切りに分割しリスト化する
  - map関数を用いて、各要素に整数型(int)を適用する
  - 1文字目をn, 2文字目をmとする
- N行に渡って入力される文字列S
  - 配列の内包表記 [ ] とスライスを用いる
  - input()で入力を受け取る
  - 必要な箇所は末尾3文字のみのため、文字のスライスを行い末尾3文字のみにする
    - 文字のまま扱う事により、文字のスライスを適用できる
    - スライスは、[開始インデックス：終了インデックス]の構造で抽出できる
    - 開始インデックスのマイナスは、後ろからインデックス指定可能
      ＊ -3だと後ろから3文字目を指定
    - 終了インデックスを省略した場合は、末尾までを示す
      ＊今回の場合だと、後ろから3文字目だけを残す事になる
  - 内包表記により、上記の処理をn行に渡って繰り返し、配列化する
- M行に渡って入力される文字列T
  - 集合の内包表記 { } を用いる
  - input()で入力を受け取る
  - 内包表記により、上記の処理をm行に渡って繰り返し、集合化する
    ＊配列化出なく、集合としてまとめている理由は後に示しています
一致する数をカウントするための変数cntを準備する(初期値は0)
for文を使って配列Sから要素を一つづつ取り出し、要素をsとする
- if文を用いて、要素 s が集合 T に含まれるかを判断する
  - 集合Tに含まれている場合は、cntに1を増やす
print文でcntを出力する

補足

T を配列ではなく、集合で取り扱った理由

まず、配列と集合の主な特徴は下記になります

特徴	配列	集合
重複を許可するか？	はい	いいえ
要素の順序を保持するか？	はい	いいえ
インデックスによる要素のアクセス	はい	いいえ
検索速度	遅い	速い
追加、削除、更新の速度	遅い	速い

＊上記の表は、ChatGPT(3.5)にて作成頂きました (わかりやすい！)

今回の問題では、要素 s が集合 T に入っているかを毎回調べるために検索スピードの向上のため、集合で内包表記を行いました

私の抱いているイメージでは (正確かどうかは別として・・・大枠は合っていると信じています)

配列の検索は、インデックス 0 〜最後まで全検索
集合の検索は、直接要素があるかを検索 (辞書引きのイメージ)

C問題：Path Graph?

C – Path Graph?

問題(要約)

N頂点M辺の単純無向グラフにおいて、パスグラフか判定する

解答

# 番号1
import sys
sys.setrecursionlimit(10**7)

# 番号2
n,m=map(int,input().split())

# 番号3
G=[list() for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    G[u].append(v)
    G[v].append(u)

# 番号4
# 番号5
if n != m+1: exit(print("No"))

# 番号6
for g in G:
    if len(g) > 2:
        exit(print("No"))

# 番号7
visited=[1] + [0] * (n)

# 番号8
def dfs(i):
    if visited[i]==0:
        visited[i]=1
        for next in G[i]:
            dfs(next)

# 番号9
dfs(1)
if sum(visited) != n+1:
    exit(print("No"))

# 番号10
print("Yes")

考え方(下の番号は、コード内のコメント番号と連携している)

再帰関数の上限を上げる
- システムパラメータ(sys)をインポートする
- sys.setrecursionlimit で再帰関数の上限を()の数に増やす
  ＊現在の再帰関数の上限は、print(sys.getrecursionlimit()) で確認できる
入力n,mをmap関数を用いて整数型に変換しながら取り込む
辺情報を取り込む
- 辺情報を格納するための変数を2次元配列Gとして準備する
- 列番号部分(内側の [ ] ) に関しては n+1 の空配列を設ける
  ＊配列の初期値は 0 番はじまりだが、与えられた番号は 1 番始まりのため、要素を一つ増やして準備する事により対応している
- m行に渡って入力される辺情報 u, v をfor文を用いて取り込む
  - 空白区切りで入力される u, v をmap関数を用いて整数型(int)にキャストする
  - 2次元配列Gに次に繋がる頂点番号を格納する
  - 単純無向グラフであるため、頂点間は双方向に行き来ができるため、u → v, v → v の双方向を配列Gに登録する
  - 例) 配列G = [ [ ], [ 第1頂点からの接続先 ], [ 第2頂点からの接続先], … ]
    　入力例1では、 G = [ [ ], [3], [4, 3], [1, 2], [2] ] となる
    　頂点1は、頂点3と接続、頂点2は、頂点4, 3と接続していることがわかる
パスグラフになるための下記の３つの条件が満たすかどうかを確認する
＊パスグラフの十分条件になる理由は、公式解説を参考にしてください
　参考：公式解説　・・・条件は想像できましたが、証明の所は理解に苦しむ。。。
1. 辺がちょうど N-1 本
2. 全ての頂点の次数が2以下 (頂点に接続されている辺が2本以下)
3. グラフが連結
条件1が満たしているかを確認する
- if文を用いて、n ≠ m+1 が成り立つかを確認する
  Not イコールは、!= を用いる
  - 条件が成り立つ場合は、パスグラフではないため、No を出力しながらプログラムを終了させる (exit 関数を用いる)
条件2が満たしているかを確認する
- 配列Gの列部分(内側の[ ])には、各頂点から次の接続先が入っているため、配列Gの各要素数が2つ以下になっていないかを確認する
  - for文を用いて、2次元配列Gから列番号部分を一つづつ取り出す
    - if文とlen関数を用いて、配列Gから取り出した要素数が2より大きいかを確認する
      - 条件が当てはまる場合は、exit関数を用いて、No を出力しながらプログラムを終了させる
深さ優先探索(DFS)を用いて、各要素が連結しているかを確認する
- DFSで探索済みかを確認するための変数visitedを準備する
  - 未検索の部分を 0とする。また、配列の0番目は使用しないため、1を代入し検索済みとする
自作関数DFSを定義する
- 引数を i (頂点番号) とする
- visitedも関数内で使用するが、関数の定義をvisitedの変数を設定した後で行っているため、引数として設定しなくても使用できる
- DFS自体は再帰を用いた関数である。主な流れは下記
  - 頂点 i が既に探索したかを調べる
    if visited[i] == 0 部分、0は未探索。1は探索済み
  - 未探索だった場合は、探索済みにする
    visited[I] = 1 部分、1は探索済み
  - 頂点 i の次数(接続先) をfor文を使って取り出す。for next in G[i] の部分
    - 次数を用いてDFSを実行する(再帰)
条件3が満たされているか確認する
- 自作関数のDFSを実行する
  - パスグラフになるためには連結する必要があるため、引数に1 (頂点1) とする
    ＊引数は、どの頂点から始めても問題ないが、頂点の数は1以上であるため 1 で設定している
- DFSを実行後にvisited配列を確認し、連結であるかを確認する
  - 関数dfs内で探索済み箇所を 1 に設定、visited配列の0番目を 1 に設定している。すべでの頂点が連結時は、visitedの合計値が n+1 と等しくなる
  - if文を使って、上記の条件が成り立たないかを確認し(sum(visited) != n+1)、無立たない場合は、exit関数で No を出力しながらプログラムを終了させる
上記3つの条件でプログラムを終了しなかった、つまり、条件を満たしているため、print文で Yes を出力する