[ABC396] ABC 396(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
3つ連続している部分をずらしながら全て見て、全て同じかどうかを判定する。
A.py
"""
<方針>
- `3` つ連続している部分をずらしながら全て見て、全て同じかどうかを判定する。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))
# 存在判定
exist = False
# 順番にみる
for i in range(N-2):
# ３箇所全て同じ値かどうか
if(A[i] == A[i+1] == A[i+2]):
# 存在判定を変える。
exist = True
# 出力
if(exist):
print("Yes")
else:
print("No")
B問題
-
listを山に見立てて、最初は0を100要素持たせて初期化する。 -
.append()で山に追加し、.pop()で山から取り出す。
B.py
"""
<方針>
- `list` を山に見立てて、最初は `0` を `100` 要素持たせて初期化する。
- `.append()` で山に追加し、 `.pop()` で山から取り出す。
"""
# 山
cards = [0]*100
# クエリ処理
for _ in range(int(input())):
match list(map(int, input().split())):
# 追加
case [1, x]:
cards.append(x)
# 取り出し
case [2]:
print(cards.pop())
C問題
方針
-
BとWを大きい順から並べた方が効率が良さそう。 - しかし、そのまま組み合わせをフルで考えると
O(MN)でTLEしてしまう。 - 何とか最大値を求める段階では線形時間程度に抑えたい。
- まず、
Bは正の値であればなんぼあっても良いので、正の値を全て拾う。 - 次に、
Wは正の値であったとしても、選んだBの個数以下であることが求められ、個数が超えてしまうならば、B[b] + W[w] > 0であることが要求される。
- まず、
- 全体の計算量はソートがネックになるので、
O(MlogM + NlogN)
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `B` と `W` を大きい順から並べた方が効率が良さそう。
- しかし、そのまま組み合わせをフルで考えると `O(MN)` で `TLE` してしまう。
- 何とか最大値を求める段階では線形時間程度に抑えたい。
- まず、`B` は正の値であればなんぼあっても良いので、正の値を全て拾う。
- 次に、`W` は正の値であったとしても、選んだ `B` の個数以下であることが求められ、個数が超えてしまうならば、 `B[b] + W[w] > 0` であることが要求される。
- 全体の計算量はソートがネックになるので、`O(MlogM + NlogN)`
"""
# 入力
N, M = map(int, input().split())
B = list(map(int, input().split()))
W = list(map(int, input().split()))
# 番兵
B.append(-float("inf"))
N = len(B)
# 大きい順からソート
B.sort(reverse=True)
W.sort(reverse=True)
# 答え
ans = 0
# Bの正の値の境界を拾う
for b in range(N):
if(B[b] < 0):
break
else:
ans += B[b]
# Wを大きい順から見ていく
for w in range(M):
# Wが負の値であれば、答えに加える必要がない。
if(W[w] < 0):
break
# Wが正の値であれば、
else:
# Bの個数に勝らない範囲であれば、
if(b > w):
# 加える
ans += W[w]
# Bの個数をオーバーするならば、
else:
# B[b] + W[w]が正であることが要求される。
if(B[b] + W[w] > 0):
# 正の値を加える
ans += B[b] + W[w]
# Bの個数を増やす
b += 1
# Bを全て加え切ったら終了
if(b == N):
break
# 負の値であれば終了
else:
break
# 終了
print(ans)
D問題
-
Nが小さいので、計算量の問題ではなく、実装力が試されそう。 - パスを全列挙すれば良さそう。
D.py
"""
<方針>
- `N` が小さいので、計算量の問題ではなく、実装力が試されそう。
- パスを全列挙すれば良さそう。
"""
# ライブラリ
from collections import deque
# 入力
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
u, v, w = map(int, input().split())
u -= 1
v -= 1
E[u].append([v, w])
E[v].append([u, w])
# 非再帰DFS
q = deque()
# 最初の頂点から始める。
q.append([0, 0, [False]*N])
# 答え
ans = float("inf")
while q:
# 頂点, 総XOR, 訪れた頂点
u, xor, visited = q.pop() # DFS
# 自分を訪れた頂点に登録する。
visited[u] = True
# 終了状態になれば、答えを更新する。
if (u == N - 1):
ans = min(ans, xor)
# 次のパスを見る
for v, w in E[u]:
# 訪れた頂点でなければ、
if not visited[v]:
# 次の頂点を追加する。
q.append([v, xor^w, visited[:]])
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- いつまで記事を書き続けようか。