ABC361(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
- 標準入力を受け取る．
-
Aをリストで受け取り，0-indexedに注意し，insertメソッドでK番目にXを挿入する． - アンパックをいう方法で空白区切りで出力する．
A.py
"""
<方針>
- 標準入力を受け取る．
- `A` をリストで受け取り，`0-indexed` に注意し， `insert` メソッドで `K` 番目に `X` を挿入する．
- アンパックをいう方法で空白区切りで出力する．
"""
N, K, X = map(int, input().split())
A = list(map(int, input().split()))
A.insert(K, X)
print(*A)
B問題
-
x, y, zのそれぞれにおいて，区間が交差しないといけないので，区間の最大と最小を比較すれば良い．
B.py
"""
<方針>
- `x, y, z` のそれぞれにおいて，区間が交差しないといけないので，区間の最大と最小を比較すれば良い．
"""
# 入力を受け取る．
abcdef = list(map(int, input().split()))
ghijkl = list(map(int, input().split()))
# 体積が正にならないときにTrueになるフラグ
ng = False
# x, y, z の3種類確認する．
for i in range(3):
# 区間が交差しないとき，
if ghijkl[i+3]<=abcdef[i] or abcdef[i+3]<=ghijkl[i]:
# 体積が正にならない．
ng = True
# 出力
if ng:
print("No")
else:
print("Yes")
C問題
方針
-
K個削除し，残った要素の順序を保つBと書いてあるが， 「順序を保つこと」は今回の問題においては重要ではない． - 最大と最小を考えるので，
Aはソートする．以下，Aは昇順であるとする． -
Aの外側をK個削った状態で，最大と最小の差を考えれば良い． -
Aの左端をi個削って，Aの右端をK-i個削って，最も差が小さくなったものを出力すれば良い．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `K` 個削除し，残った要素の順序を保つ `B` と書いてあるが， 「順序を保つこと」は今回の問題においては重要ではない．
- 最大と最小を考えるので， `A` はソートする．以下， `A` は昇順であるとする．
- `A` の外側を `K` 個削った状態で，最大と最小の差を考えれば良い．
- `A` の左端を `i` 個削って， `A` の右端を `K-i` 個削って，最も差が小さくなったものを出力すれば良い．
"""
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))
# Aをソートする．
A.sort()
# (最大と最小の差)の最小値を求める．
# 初期値は無限とする．
ans = float("inf")
for i in range(K+1):
# 小さい方を更新
ans = min(ans, A[i+N-K-1]-A[i])
# 出力
print(ans)
D問題
- 公式解説と一緒です．
- 筆者は，再帰を高速化してもダメだったので，非再帰で実装しました．
D.py
"""
- 公式解説と一緒です．
- 筆者は，再帰を高速化してもダメだったので，非再帰で実装しました．
"""
# このおまじないではTLEした．
"""
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)
"""
from collections import deque
N = int(input())
S = list(input())
T = list(input())
# 個数が一致してない時は到達不可能．
if(S.count("W")!=S.count("W")):
print(-1)
exit()
# 末尾に "." を２つつける．
S.append(".")
S.append(".")
T.append(".")
T.append(".")
# 連想配列にアクセスするときに利用する．
def ind(S):
return "".join(S)
# 連想配列．
## key: 状態
## val: 到達するのに必要なステップ数
dp = {}
# 初期状態は0ステップで移動可能
dp[ind(S)] = 0
q = deque()
q.append(S)
while q:
S = q.popleft()
# "."が連続している場所を取得．
a = None
for i in range(N+1):
if(S[i]=="."):
a = i
break
# 遷移
for i in range(N+1):
# 連続している2箇所を取得する．
x = S[i]
y = S[i+1]
# 両方とも"."でなければ，
if(x != "." and y != "."):
# 次の状態を作る．
tmp = S[:]
# 石を取り除く
tmp[i] = "."
tmp[i+1] = "."
# 石を移動する．
tmp[a] = x
tmp[a+1] = y
# 状態遷移．
if((not ind(tmp) in dp) or (dp[ind(S)]+1<dp[ind(tmp)])):
# if not ind(tmp) in dp:
dp[ind(tmp)] = dp[ind(S)] + 1
q.append(tmp)
# 出力
if(ind(T) in dp):
print(dp[ind(T)])
else:
print(-1)
E問題
- 公式解説と一緒です．
E.py
"""
<方針>
- 公式解説と一緒です．
"""
from collections import deque
N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N-1)]
# グラフの辺を構築
E = [[] for _ in range(N)]
for a, b, c in ABC:
a -= 1
b -= 1
E[a].append([b, c])
E[b].append([a, c])
# 引数を起点として，最も遠い点とそのコストを出力する．
def far(start):
vis = [None]*N
vis[start] = 0
q = deque()
q.append(start)
while q:
a = q.popleft()
for b, c in E[a]:
if vis[b] is None:
vis[b] = vis[a] + c
q.append(b)
v = -1
D = -1
for i, d in enumerate(vis):
if(D<d):
D = d
v = i
return v, D
# 最初の頂点から最も遠い頂点を取得
v, _ = far(0)
# 最も遠い頂点から見た，最も遠い距離を取得
_, D = far(v)
# 答えの計算
ans = 2*sum(map(lambda x: x[2], ABC)) - D
print(ans)
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 十で神童、十五で才子、二十歳過ぎれば只の人