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

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

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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 288

A問題：Many A+B Problems

A – Many A+B Problems

問題(要約)

N個の整数の組(Ai, Bi)について、Ai + Bi を出力する

解答

# 番号1
n=int(input())

# 番号2
for _ in range(n):
    a,b=map(int,input().split())
    print(a+b)

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

入力nを受け取る
- 入力nは整数のため、input()で受け取り、整数型(int)に変換(キャスト)を行っている
Ai と Bi は、n行に渡って入力する為、for文をn回繰り返す。
カウンタ変数は必要ない為、空白を意味する _ (アンダーバー)を置いておく
( i などを仮置きしても動作上問題ない)
- Ai, Bi の受け取りを行う
  - 空白区切りで入力をinput()で受け取る
  - 上記をsplit()で分割する(リスト化)
  - map関数を用いてリストの要素それぞれに整数型(int)を適用する(キャスト)
  - 上記のリストの0番目をa, 1番目をbに代入する
    ＊左側の項目数と右側のリストの数があっていれば、直接変数に組み込める
- print文を使って、上記の a+b を出力する
  for文で繰り返すことにより、n行の出力を得ることができる

B問題：Qualification Contest

B – Qualification Contest

問題(要約)

N人がコンテストに参加し、上位K人のハンドルネームの辞書順で出力する

解答

# 番号1
n,k=map(int,input().split())

# 番号2,3
S=sorted(input() for _ in range(k))

# 番号4
for s in S:
    print(s)

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

入力N, Kを受け取る
- 空白区切りの入力をinput()で受け取る
- split()で空白区切りに分割を行う(リスト化)
- map関数で整数型(int)に変換(キャスト)する
- リストの0番目をn, リストの1番目をkに代入する
ハンドルネームSiの入力を取り込む。ただし、k番目までの入力を行う。理由は下記
- ハンドルネームは順位順に並んでいる
- 上位k番目の順位の中で、辞書順に並び替えを行う
k番目までのハンドルネームSiの取り込みと並び替えを内包表記とソートを用いて一度に行う
- input()でS1の取り込みを行う
- 内包表記( input()の後のfor文) を用いることにより、input() をk回繰り返す
- 1位からk位までをリストで取り込める
- ソート関数sorted()を用いることにより、リストを辞書順に変換できる
出力の形式は、辞書順に一行づつ出力するため、番号3で作ったリストをfor文で先頭から出力する

C問題：Don’t be cycle

C – Don’t be cycle

問題(要約)

N頂点M辺の単純無向グラフにおいて、0本以上の辺を削除することにより閉路を持たないようにさせる。削除する辺の数を求める

解答

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

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

# 番号3
g=[list() for _ in range(n+1)]

# 番号4
for _ in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)

# 番号5
# 番号6
cnt=[]

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

# 番号8
def dfs(pos,g,visited,cnt):
    for next in g[pos]:
        if visited[next]==0:
            visited[next]=visited[pos]+1
            dfs(next,g,visited,cnt)
        elif visited[next] - visited[pos] >=2:
            cnt.append(next)

# 番号9
for i in range(1,n+1):
    if visited[i]==0:
        visited[i]=1
        dfs(i,g,visited,cnt)
print(len(cnt))

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

再帰関数の上限を上げる
- システムパラメータ(sys)をインポートする
- sys.setrecursionlimit で再帰関数の上限を()の数に増やす
  ＊現在の再帰関数の上限は、print(sys.getrecursionlimit()) で確認できる
入力n,mをmap関数を用いて整数型に変換しながら取り込む
各頂点ごと隣接リストの空配列gを作成する
- list関数を用いて空のリストを作成する (list())
- 内包表記を用いて空のリストを n+1 を作成する
  ＊頂点番号が1始まりのため、n+1 にしている。0番目は空になる
- 空の二次元配列gは、[ [ ], [ ], [ ], … , [ ] ] の形をしている
No. 3で作成した隣接リストgに辺情報を登録する
- 辺数はM個あるため、for文をm回繰り返す。カウンタは空白( _ )で設定する
  - 辺に繋がる頂点A, Bをmap関数を用いて整数型に変換しながら取り込む
  - 二次元配列の隣接リストgに辺を登録する
  - 無向グラフのため、A → B, B → A も行き来可能であるため両方向を登録する
  - g[a].append[b] は、配列gのa番目のリストに b を加える(2次元配列)
  - 例：a: 1, b: 2 の場合、g = [ [ ], [2], [1], … ,[ ] ] になる
深さ優先探索(DFS: Depth-First Search)を用いて下記の考えを用いる
- DFSを用いて各頂点に最短距離順の番号を付ける
- 隣接せずに既に訪れた頂点がある場合は閉路が存在することになる
- つまり、最短距離順が2以上離れている訪問済み頂点の数を数え上げる
No. 5の条件にあてはまる条件を保存するための空のリストcntを準備する
訪問済みか、最短距離の保管を行うためのvisited配列を0で初期化する
頂点数はnだが、1〜N を使用するため n+1 までの配列を準備する
深さ優先探索(DFS)の関数を定義する
- 関数への入力値として以下の４つを入力する
  - 現在位置：pos
  - 隣接リスト：g
  - 訪問済みリスト(最短距離も兼ねる)：visited
  - 閉路リスト：cnt
- 現在の頂点位置における接続先、つまりg[pos]の要素、を一つづつfor文でカウンタ next として取り出す
  - まだ訪問していない頂点の場合、つまり、visited[next] == 0
    - 現在の頂点の距離visited[pos]の値に1を加算する
    - next の点を元にDFS(深さ優先探索)を行う（再起）
  - 既に訪問済みの頂点の場合(visited[next] != 0 )、かつ、現頂点と隣同士ではない
    ( 元頂点の距離 – 次の頂点の距離 >= 2 )の場合
    - 閉路になっているため、配列cntに頂点番号(next)を記憶する
頂点1から順番にDFSを行う
頂点が1始まりのNまでの頂点があるため、カウンタ i を1〜n+1まで繰り返す
- 頂点 i が未訪問かを確かめる ( 未訪問時は visited[i] == 0 となる )
  - 未訪問時は、その頂点を訪問済みで距離1に設定する
  - 現在の頂点 i、隣接グラフ g、訪問リスト visited、閉路カウント cnt を自作関数DSFにわたす
  - 関数DFSを実行する