初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC317_A-C問題】

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

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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 317

A問題：Potions

A – Potions

問題(要約)

ナオヒロ君がモンスターの体力を上げるために、持っている薬のうち最も効き目の弱い薬を選び、モンスターの体力を目標以上にする問題です。薬は番号がついており、与えると体力が増加します。ただし、薬の効き目は番号が小さい順に効き目が弱くなるようになっています。目標体力以上にするために選ばれる薬の番号を求めてください。

解答

n, h, x = map(int, input().split())  # n: 傷薬の種類数, h: モンスターの体力, x: 目標体力
P = list(map(int, input().split()))  # 各傷薬の効果

for i, p in enumerate(P, start=1):
    if h + p >= x:
        exit(print(i))  # 目標体力以上になる傷薬を見つけたらその番号を出力して終了

n, h, x = map(int, input().split())：傷薬の種類数 n、モンスターの体力 h、目標体力 x を読み込みます。
P = list(map(int, input().split()))：各傷薬の効果をリスト P として読み込みます。
for i, p in enumerate(P, start=1):：P リストをループで順に取り出し、傷薬の番号を含む enumerate イテレータを使用します。start=1 はインデックスを1から始めるための指定です。
if h + p >= x:：現在の傷薬 p を使用した場合、モンスターの体力に傷薬の効果を加えた結果が目標体力以上になるか判定します。
exit(print(i))：もし目標体力以上になる傷薬を見つけたら、その傷薬の番号 i を出力してプログラムを終了します。

B問題：MissingNo.

B – MissingNo.

問題(要約)

ナオヒロ君が連続した整数を持っていて、そのうち1つをなくしてしまいました。残っている整数のリストが与えられるので、なくした整数を求める問題です。ただし、与えられる入力はなくした整数が一意に定まるようなものだけが与えられます。

解答

考え方）

リストAを昇順にソートし、並びが１を加算した値と等しいかどうかを確認し、解を求めます

n = int(input())  # 整数の数
A = sorted(list(map(int, input().split())))  # 整数のリストを昇順にソート

for i, a in enumerate(A, start=A[0]):  # ソートされたリストをループで処理
    if i != a:
        exit(print(i))  # 欠けている整数を出力して終了

以下詳細

n = int(input())：整数の数 n を読み込みます。
A = sorted(list(map(int, input().split())))：整数のリストを読み込み、昇順にソートして A に格納します。
for i, a in enumerate(A, start=A[0]):：ソートされたリスト A をループで順に取り出し、それを i に代入します。また、ループのスタートを A の最小値に設定します。
if i != a:：もし i（ループ変数）と取り出した整数 a が異なる場合、つまり欠けている整数を見つけた場合、以下の処理を実行します。
exit(print(i))：欠けている整数を出力してプログラムを終了します。このコードは、ソートされた整数リストを順に調べることで、欠けている整数を見つけるアプローチです。

C問題：Remembering the Days

C – Remembering the Days

問題(要約)

与えられた街と道路の情報から、異なる街間を通る際に道路の長さの和が最大となる値を求める問題です。始点と終点が同じでない範囲内で、通る道路の長さの和が最大となる値を求めます。

解答

考え方）

与えられた街と道路の情報を基に、異なる街間を通る際に道路の長さの和が最大となる値を求めるための深さ優先探索（DFS）を用いています。

import sys
sys.setrecursionlimit(10 ** 8)  # 再帰の深さの制限を増やす

n, m = map(int, input().split())  # 街の数 n と道路の数 m を入力

# 各街間の関係を表すグラフを作成
graph = [list() for _ in range(n + 1)]

for _ in range(m):
    a, b, c = map(int, input().split())  # 街 a と街 b 間の道路情報と長さ c を入力
    graph[a].append((b, c))
    graph[b].append((a, c))

ans = 0  # 最終的な答えを格納する変数

def dfs(node, total_distance, visited):
    global ans　　　　　　　　# defのスコープ外(範囲外)のansを呼び出す
    if not visited[node]:  # もし街が未訪問であれば
        visited[node] = True  # 街を訪問済みにマーク

        for neighbor, distance in graph[node]:
            if not visited[neighbor]:  # もし隣接する街が未訪問であれば
                dfs(neighbor, total_distance + distance, visited)  # 隣接する街に対して再帰的に探索

        ans = max(ans, total_distance)  # 最大の道路長を更新

        visited[node] = False  # バックトラッキングで訪問状態を戻す

# 全ての街をスタート地点として探索
for i in range(1, n + 1):
    dfs(i, 0, [False] * (n + 1))

print(ans)  # 最大の道路長を出力

以下詳細

import sys および sys.setrecursionlimit(10 ** 8)：再帰の深さの制限を増やすために、再帰のスタック制限を設定しています。
n, m = map(int, input().split())：街の数 n と道路の数 m を読み込みます。
graph = [list() for _ in range(n+1)]：街間の関係をグラフとして表現するための空のリスト graph を作成します。各街についての道路情報を格納するために使用します。
for _ in range(m):：道路の数だけ以下の操作を繰り返します。
- a, b, c = map(int, input().split())：街 a から街 b への道路の情報として、街番号と道路の長さ c を読み込みます。
- graph[a].append((b, c)) および graph[b].append((a, c))：街 a と街 b を結ぶ道路の情報をそれぞれの街のリストに追加します。
ans = 0：最終的な答えを格納する変数 ans を初期化します。
def dfs(node, total_distance, visited):：深さ優先探索を行う再帰関数 dfs を定義します。引数として現在の街の番号 node、累計の道路の長さ total_distance、街の訪問状態を示すリスト visited を受け取ります。
if visited[node] == False:：もし現在の街が未訪問であれば以下の操作を行います。
- visited[node] = True：現在の街を訪問済みとしてマークします。
for neighbor, distance in graph[node]:：現在の街に隣接する各街とその道路の情報について以下の操作を繰り返します。
- if visited[neighbor] == False:：もし隣接する街が未訪問であれば、その街に対して再帰的に dfs 関数を呼び出し、道路の長さを累計した total_distance + distance と訪問状態を更新した visited を渡します。
ans = max(ans, total_distance)：現在の累計の道路の長さ total_distance とこれまでの最大長 ans を比較し、最大値を ans に格納します。
visited[node] = False：現在の街の訪問状態を未訪問に戻します（バックトラッキング）。
for i in range(1, n+1):：全ての街について以下の操作を繰り返します。
- dfs(i, 0, [False] * (n+1))：各街をスタート地点として dfs 関数を呼び出し、最大の道路長を求めます。
- dfsの引数に各項目を直接与えています。
  ＊各項目の値を先に設定してから、dfsに変数を渡すのと同じになります。下記と同義。
  　　node = i
  　　total_distance = 0
  　　visited = [False] * (n+1)
  　　dfs(node, total_distance, visited)
print(ans)：最大の道路長 ans を出力します。