こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC311のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- Pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
- DFS (深さ優先探索) ・・・ 問題C
今回の参加コンテスト(ABC311)
A問題：First ABC
問題(要約)
A, B, C からなる文字列 S が与えられ、Sは A, B, C を必ず含んでいる。S を左から1文字ずつ見ていった場合に、初めて下記の条件が満たした状態になるのは、左から何文字目かを求める
- A, B, C が必ず1回以上出現している
解答
# 番号1
n=int(input())
setS=set()
# 番号2
for i, s in enumerate(input()):
setS.add(s)
if len(setS)==3:
exit(print(i+1))考え方 (下の番号は、コード内のコメント番号と連携している)
集合として考え、集合の数が３つになった場合がA, B, C の３種類が出現したときになる。
＊集合は、同じ文字は同じものとして扱われるため、このような考え方ができる
以下、プログラム内容詳細
- 入力nを受け取り、空集合のsetSを定義する
- n: 整数型で受け取る
- setS: 空集合を準備する
- ＊ 入力Sについては、for文を作成するときに受け取りを行う
（少しこなれた風の書き方をしてみたかっただけです^^;）
- 入力Sの文字列を一つづつ調べていく
- enumerateを用いる事により、index番号と要素を同時に取得できる
- 取り出した要素 s (文字列Sの一文字) を空集合に追加する
- if文を用いて、空集合の数 = 3 が成り立つかを確認する
- 上記が成り立つ場合は、enumerateで設定した index番号 + 1 (0始まり対応）を出力しプログラムを終了させる
- for文を用いて１品料理のそれぞれの値段を取り出す
B問題：Vacation Together
問題(要約)
N人の人がいる。N人の今後D日間の予定が与えられる。D日間のうち全員が暇である日が何日あるかを求める
解答
# 番号1
n, d = map(int,input().split())
S=[list(input()) for _ in range(n)]
# 番号2
schedule=[]
# 番号3
for j in range(d):
for i in range(n):
if S[i][j]=='x':
schedule.append(0)
break
else:
schedule.append(1)
# 番号4
maxDay,tmpDay=0,0
# 番号5
for i in range(d):
if schedule[i]==1:
tmpDay+=1
else:
maxDay=max(maxDay, tmpDay)
tmpDay=0
# 番号6
maxDay=max(maxDay, tmpDay)
print(maxDay)考え方(下の番号は、コード内のコメント番号と連携している)
N人が予定が空いている o の日付を1, そうではない場合を 0 として、D日間の全員のトータルの日程を求める。1 が続いている日にちを数える
以下詳細
- 入力 n, d, S を受け取る
- n, d: 整数型で受け取る
- S: 内包表記をもちいて2次元配列で入力を受け取る
- N人の合算の予定を格納するためのリスト schedule を準備する
- for文のネスト(ここでは２重のfor文) を行いN人の予定を確認する
- 外側のfor文では、D日間を示す
- 内側のfor文では、N人を示す
- S[i][j] == ‘x’ の時は、scheduleに 0 を追加し内側のfor文をbreakで抜ける
- 内側のfor文がbreakで抜けなかった場合は、scheduleに 1 を追加する
- 内側のfor文では、N人を示す
- 上記の組み合わせでD日間のN人の予定を考慮した予定を作ることができる
- 外側のfor文では、D日間を示す
- 予定が空いている最大日を格納するmaxDay, 一時保管のtmpDayを準備する。初期値は0とする
- for文を用いて、schedule を1日づつ調べる
- schedule[i] == 1の時は、tmpDayに1を加算する
- schedule[i] == 0の時は、maxDayを必要に応じて更新する
- maxDayとtmpDayを比較し、大きい方をmaxDayとする
- schedule[i] == 1でfor文を終了した場合は、maxDayが更新されないため、maxDayを更新する。その後にmaxDayを出力する
C問題：Find it!
問題(要約)
N頂点N辺の有向グラフがある。同一頂点を含まない有向閉路を求める
解答
# 番号1
import sys
sys.setrecursionlimit(10 ** 8)
# 番号2
n=int(input())
A=[0] + list(map(int,input().split()))
# 番号3
g = [[0]] + [list() for _ in range(n)]
for i in range(1,n+1):
g[i].append(A[i])
# 番号4
def dfs(pos,visited,order,dup):
#番号4-1
if visited[pos]==0:
visited[pos]=1
order.append(pos)
for next in g[pos]:
dfs(next,visited,order,dup)
else:
dup.append(pos)
return
# 番号5
for i in range(1,n+1):
#番号5-1
visited=[0 for _ in range(n+1)]
order=[]
dup=[]
dfs(i,visited,order,dup)
#番号5-2
if len(dup) != 0:
idx = order.index(dup[0])
print(len(order[idx:]))
print(*order[idx:])
exit()考え方(下の番号は、コード内のコメント番号と連携している)
深さ優先探索(DFS)を用いて解く。ポイントは、同じ点を２度訪れた場合にその区間が閉路になることを利用している
以下詳細
- 深さ優先探索は、再起を伴うプログラムのため、再起の制限を拡大しておく
＊再起を行うときの決まり文句 (っと考えていいと思います。レベルが上がったら調べる予定) - 入力 n, A を受け取る
- n: 整数型で受け取る
- A: リスト型で受け取るが、インデックス合わせのため先頭に 0 を追加している
- 有向グラフの頂点毎の連結先を格納するための g を準備する。
- 各頂点に複数の接続先があるときがあるので、2次元配列を準備する。
＊ここでもインデックス合わせのため初期に0を追加 - 配列Aは、各インデックス番号が頂点を示し、番号が次の連結先になっているため、その情報を g に登録していく。
- 各頂点に複数の接続先があるときがあるので、2次元配列を準備する。
- 深さ優先探索DFSをdfs関数として定義していく
- 関数に入力する引数は以下になっている
- pos: 現在の頂点の位置
- visited: 訪問したかどうかを確認するためのリスト
(頂点数+1(インデックス合わせ)分） - order: 訪れた頂点順を格納していく配列
- dup: 重複して訪れたポイントをリスト形式で保持。def外で呼び出したいためリスト形式にしている
- posが既に訪問済みかどうかを確認する
- 訪問済みでない場合：
- 訪問済みリストの更新 (visited[pos] = 1)
- 訪問順に登録 (order.append(pos))
- for文を用いて次の連結先を順番に調べる
- 再起を用いてdfsの同じ操作を繰り返す
- 訪問済みの場合：
- 一度訪問しているため重複(閉路連結)ポイントになるため、配列dupに現在の位置posを追加する
- 閉路を見つけたため、returnでdfsから戻る
- 訪問済みでない場合：
- posが既に訪問済みかどうかを確認する
- 関数に入力する引数は以下になっている
- 上記のdfsに引数を渡して目的の処理を行う
- 各頂点に対して閉路を探すために順番に頂点番号を取り出す
- dfsに渡す引数を準備する(各引数の役割は番号4を参照)
- 頂点 i に対してdfsを実行する
- 上記dfsの結果において、dupに値が保持されているかを調べる
つまり、頂点 i からDFSを行った場合に、閉路が見つかったかどうかを確認する- 閉路が見つかったので、あとは閉路になっている箇所の頂点数と頂点番号を取得する
- orderには訪問順の頂点番号が登録されているが、下記の特徴を持っている
- 閉路でない部分も含む
- 閉路が見つかった時点でDFSから抜けている
-> dup[0]に保持されている頂点からorderの最後までが求める閉路の頂点
- リストのindex関数を用いる事により、dup[0]がリストの何番目にあるかを確認する
例） order = [1, 3, 4, 7, 8, 2] の order.index(7) => 3 を返す - スライスを用いて order の要望部分を抜き出しつつ、求めたい頂点数(len関数)と頂点番号を出力する
- 目的の答えを出力できたため、プログラムを終了させる
- 各頂点に対して閉路を探すために順番に頂点番号を取り出す
感想
やった！C問題まで解けました。ここ1ヶ月近く、B問題までしか解けない期間が続いていたので、正直悔しい思いもしましたが、今回C問題をクリアできて本当に嬉しいです(´▽｀)。競プロの難易度は上がっていますが、毎回C問題までは解ける実力をつけて、次はD問題にも挑戦できる回数が増えるように精進していこうと思います。
また、最近はpythonでのデータ分析にもハマっています！これからはKaggleの問題もブログで扱っていきたいと思います。初心者の方にもわかりやすいように、pythonを使ったデータクレンジングやデータの視覚化などの方法を紹介していきます(´ω｀)。
競プロライフをより楽しく、充実したものにするために、これからもコンテストに参加し、ブログを毎週更新していきます！皆さんも一緒に頑張りましょう！
それでは、良い競プロライフを〜！(*＾▽＾)／
コメント