[ABC427] ABC 427(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- スライスを使って、左側と右側をくっつける。
A.py
"""
<方針>
- スライスを使って、左側と右側をくっつける。
"""
# 入力
S = input()
# 長さ
N = len(S)
# 左右
left = S[:N//2]
right = S[-N//2 + 1:]
# くっつける
ans = left + right
# 出力
print(ans)
B問題
-
Aを配列で管理し、順番に求めていく。 - 関数
fを用意しておく。 - 二重の
for文を使う。
B.py
"""
<方針>
- `A` を配列で管理し、順番に求めていく。
- 関数 `f` を用意しておく。
- 二重の `for` 文を使う。
"""
# 関数
def f(a:int):
ans = 0
for val in str(a):
ans += int(val)
return ans
# 入力
N = int(input())
# 配列管理
A = [1]*(N)
# 二重ループ
for i in range(N-1):
for j in range(i+1):
# たす
A[i+1] += f(A[j])
# 最後を出力
print(A[-1])
C問題
方針
-
Nは小さいが、Mは bit 全探索できるほど小さくない。 - そこでまず、どのような黒白のパターンがあるかを全探索する。
- その上で、それを成立させられるように辺を切ってみれば良い。
- 一番辺を切った回数が少ないところを選べば良い。
- 全体として、
O(2^N・M)となる。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `N` は小さいが、`M` は bit 全探索できるほど小さくない。
- そこでまず、どのような黒白のパターンがあるかを全探索する。
- その上で、それを成立させられるように辺を切ってみれば良い。
- 一番辺を切った回数が少ないところを選べば良い。
- 全体として、`O(2^N・M)` となる。
"""
# 双方向グラフ構築。
N, M = map(int, input().split())
E = [[False]*N for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
u -= 1
v -= 1
E[u][v] = True
E[v][u] = True
# 最小削除数
ans = float("inf")
# 黒白全パターン
for b in range(1<<N):
# 黒いところを保存する。
black = [False]*N
for bit in range(N):
if(b>>bit & 1):
black[bit] = True
# 削除回数
tmp = 0
for u in range(N):
for v in range(N):
# 辺がつながっている & 色が同じ
if(E[u][v] and (black[u] == black[v])):
tmp += 1
# 双方向でカウントしたので、半分にしておく。
tmp //= 2
# 更新する
ans = min(ans, tmp)
# 出力
print(ans)
D問題
-
dp[u][k]を考える。-
u: 頂点 -
k: 状態-
0: 初期 -
1: 最初のAliceの手が終わった後 -
2: 最初のBobの手が終わった後 - ...
-
-1: 最後のBobの手が終わった後
-
-
value:Aliceが勝てるかどうか
-
- この
dpにおいて、後ろから順番に、-
AliceはひたすらTrueに遷移できるか。 -
BobはひたすらFalseに遷移できるか。
-
- 最後の手は
Sから生成してやれば上手くいきそう。
D.py
"""
<方針>
- `dp[u][k]` を考える。
- `u`: 頂点
- `k`: 状態
- `0`: 初期
- `1`: 最初の `Alice` の手が終わった後
- `2`: 最初の `Bob` の手が終わった後
- ...
- `-1`: 最後の `Bob` の手が終わった後
- `value`: `Alice` が勝てるかどうか
- この `dp` において、後ろから順番に、
- `Alice` はひたすら `True` に遷移できるか。
- `Bob` はひたすら `False` に遷移できるか。
- 最後の手は `S` から生成してやれば上手くいきそう。
"""
T = int(input())
for _ in range(T):
# 入力
N, M, K = map(int, input().split())
S = input()
E = [[] for _ in range(N)]
for _ in range(M):
U, V = map(int, input().split())
U -= 1
V -= 1
E[U].append(V)
# dp の初期値
dp = [[False]*N for _ in range(2*K + 1)]
for i, s in enumerate(S):
if(s == "A"):
dp[-1][i] = True
# dp の遷移
for i in range(K):
# Bobの手
for u in range(N):
value = True # Bob はなんとか False にしたい
for v in E[u]:
if not (dp[-2*i - 1][v]):
value = False
break
dp[-2*i - 2][u] = value
# Aliceの手
for u in range(N):
value = False # Alice はなんとか True にしたい
for v in E[u]:
if(dp[-2*i - 2][v]):
value = True
break
dp[-2*i - 3][u] = value
# 頂点１は、最後から見て2*K個前の手において、最適に動いたら、どっちが勝つか。
if(dp[0][0]):
print("Alice")
else:
print("Bob")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 自称デンジ