【ABC】Atcoder Beginner Contest317 A,B,C問題解答・解説【Python】

A – Potions
1. 解答
B – MissingNo.
1. 解答
C – Remembering the Days
1. 解答
まとめ
1. 類題

A – Potions

解答

n,h,x = map(int, input().split())
p = list(map(int, input().split()))

for i in range(len(p)):
  if h + p[i] >= x:
    print(i+1)
    exit()

n,h,x = map(int, input().split())

p = list(map(int, input().split()))

for i in range(len(p)):

if h + p[i] >= x:

print(i+1)

exit()

N個の傷薬のリストPと、Hのヒットポイントを持つモンスターがいる。i番目の傷薬を使ってヒットポイントがX以上になった時、iを出力する。

Pは初めから小さい方から並んでいるので、for文で前から順番にhと足し算してみた結果、Xを越えたらその時のインデックス+1を出力する。

B – MissingNo.

解答

n = int(input())
a = list(map(int, input().split()))

a = sorted(a)
a.append(a[-1]+1)

for i in range(1,len(a)+1):
  if a[i]!=a[i-1]+1:
    print(a[i-1]+1)
    print(exit())

n = int(input())

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

a = sorted(a)

a.append(a[-1]+1)

for i in range(1,len(a)+1):

if a[i]!=a[i-1]+1:

print(a[i-1]+1)

print(exit())

本来は1つずつ値が増えていくので、データの最後に値を1つ追加する。追加する値は、現在の最後の値＋1の数値。

1～n+1番目のインデックスまでをfor文でループし、i番目の値がi-1番目の値＋1でない場合に、i-1番目の値+1を出力する。

実際の業務では元のデータの末尾にデータを追加するようなことはあまりしたくないと思う。

C – Remembering the Days

解答

N,M=map(int,input().split())

#それぞれの町から別の町へ移動する際の距離を二次元リストで保持
E=[[0]*(N+1) for _ in range(N+1)]
#道路の数だけループ
for _ in range(M):
  #入力を受け取る
  a,b,c=map(int,input().split())
  #1つ目の添字は出発地点の町、2つ目の添字は移動先の町を示す。値は距離
  #今回は道路を双方向にわたることができるのでお互いの町への距離を保持する
  #一方通行の場合、以下のように2行ではなく、出発元側のみ距離を保持する
  E[a][b]=c
  E[b][a]=c
#print(E)

ans=0
#訪問済みの町を示すリスト
used=[False]*(N+1)

#DFS。第一引数：今回訪問した町、第二引数：今回訪問した町までの移動距離
def dfs(v,s):
  #関数外の変数を使用する宣言
  global ans
  #今回の探索で訪問したことを示すためTrueに変更
  used[v]=True
  #今の最長移動距離よりも長ければ更新
  if s>ans: ans=s
  #町の数だけ再帰的に繰り返し呼び出す
  for i in range(1,N+1):
    #i番目の町が未訪問かつ、道路がある場合
    #道路がない場合、E[v][i]は初期化時の0のまま。0,1がFalse,Trueとして判定されている
    if not used[i] and E[v][i]:
      #print(E[v][i], "v:",v,"i:",i)
      #i番目の町を探索する。現在の最長距離＋i番目の町までの距離の合計を引数に渡す
      dfs(i,s+E[v][i])
  #別の町から再度辿れる町を全て探索するため、今回の町を探索後は未訪問に戻す。
  used[v]=False

#町の数だけ探索を行う
for i in range(1,N+1):
  dfs(i,0)
#解答を出力
print(ans)

N,M=map(int,input().split())

#それぞれの町から別の町へ移動する際の距離を二次元リストで保持

E=[[0]*(N+1) for _ in range(N+1)]

#道路の数だけループ

for _ in range(M):

#入力を受け取る

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

#1つ目の添字は出発地点の町、2つ目の添字は移動先の町を示す。値は距離

#今回は道路を双方向にわたることができるのでお互いの町への距離を保持する

#一方通行の場合、以下のように2行ではなく、出発元側のみ距離を保持する

E[a][b]=c

E[b][a]=c

#print(E)

ans=0

#訪問済みの町を示すリスト

used=[False]*(N+1)

#DFS。第一引数：今回訪問した町、第二引数：今回訪問した町までの移動距離

def dfs(v,s):

#関数外の変数を使用する宣言

global ans

#今回の探索で訪問したことを示すためTrueに変更

used[v]=True

#今の最長移動距離よりも長ければ更新

if s>ans: ans=s

#町の数だけ再帰的に繰り返し呼び出す

for i in range(1,N+1):

#i番目の町が未訪問かつ、道路がある場合

#道路がない場合、E[v][i]は初期化時の0のまま。0,1がFalse,Trueとして判定されている

if not used[i] and E[v][i]:

#print(E[v][i], "v:",v,"i:",i)

#i番目の町を探索する。現在の最長距離＋i番目の町までの距離の合計を引数に渡す

dfs(i,s+E[v][i])

#別の町から再度辿れる町を全て探索するため、今回の町を探索後は未訪問に戻す。

used[v]=False

#町の数だけ探索を行う

for i in range(1,N+1):

dfs(i,0)

#解答を出力

print(ans)

DFS：深さ優先探索を使う問題。

A – Potions

解答

B – MissingNo.

解答

C – Remembering the Days

解答

まとめ

類題

コメント