[ABC384] ABC 384(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
-
Sを一文字ずつsとして取り出して，sを追加するかc2を答えにするかを考える．
A.py
"""
<方針>
- `S` を一文字ずつ `s` として取り出して，`s` を追加するか `c2` を答えにするかを考える．
"""
# 入力
N, c1, c2 = map(str, input().split()) # str型で受け取る
S = input()
ans = "" # 答え
for s in S: # 一つずつみる
# c1のとき
if (s == c1):
# sを選択
ans += s
# c1じゃない時
else:
# c2を選択
ans += c2
# 出力
print(ans)
B問題
- 毎回レーティングを正しく変動させれば良さそう．
-
for文の中で，ダイナミックに入力受け取ってみる． -
match文で条件分岐をしているが，if文でも全然問題ない
B.py
"""
<方針>
- 毎回レーティングを正しく変動させれば良さそう．
- `for` 文の中で，ダイナミックに入力受け取ってみる．
- `match` 文で条件分岐をしているが，`if` 文でも全然問題ない
"""
# 入力
N, R = map(int, input().split())
# レート変動
for _ in range(N):
# 入力をダイナミックに受け取る
D, A = map(int, input().split())
# divisionで分岐
match D:
case 1:
# レーティング対象のとき
if (1600 <= R <= 2799):
R += A
case 2:
# レーティング対象のとき
if (1200 <= R <= 2399):
R += A
# 出力
print(R)
C問題
方針
- 今作のC問題は TLEは気にしなくて良い．頑張って実装できるかどうかのバトルである．
- bit全探索について前提の知識で実装しています．わからない方はググってみてください．
- それぞれのプレイヤー
playerのスコアscoreと 名前nameを計算し，リストplayersに入れる -
playersをスコアを降順に，その次に名前を昇順にソートする．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- それぞれのプレイヤー `player` のスコア `score` と 名前 `name` を計算し，リスト `players` に入れる
- `players` をスコアを降順に，その次に名前を昇順にソートする．
"""
# 入力
abcde = list(map(int, input().split()))
# プレイヤーのスコアと名前を管理するリスト
players = []
# 全てのプレイヤーのスコアと名前を計算する
for i in range(1, 1<<5):
score = 0 # スコア
name = "" # 名前
# bitで判定
for j in range(5):
if (i>>j & 1):
# スコアを追加
score += abcde[j]
# 名前を追加
name += chr(j+ord("A"))
# リストに入れる
players.append([score, name])
# スコアを降順に，その次に名前を昇順にソート
players.sort(key=lambda x:(-x[0], x[1]))
# 出力
for player in players:
# 名前だけ出力
print(player[1])
D問題
- まず，
Sを形成する上で，Aの繰り返しが続くパターンを排除する．- そのために，
Aの総和sum(A)でSを割った余りを考えれば長いAの繰り返しは無視できる． -
Aを2倍にしたものAAでSを形成できる連続部分列があるかどうかを考えれば良さそう．
- そのために，
- 累積和の差分を考えればうまくいけそう．
- 差分の一方の累積和はハッシュ関数で定数時間で計算すれば良さそう．
D.py
"""
<方針>
- まず，`S` を形成する上で，`A` の繰り返しが続くパターンを排除する．
- そのために，`A` の総和 `sum(A)` で `S` を割った余りを考えれば長い `A` の繰り返しは無視できる．
- `A` を `2` 倍にしたもの `AA` で `S` を形成できる連続部分列があるかどうかを考えれば良さそう．
- 累積和の差分を考えればうまくいけそう．
- 差分の一方の累積和はハッシュ関数で定数時間で計算すれば良さそう．
"""
# 入力
N, S = map(int, input().split())
A = list(map(int, input().split()))
# 総和で割った余りを考えれば良さそう
S %= sum(A)
# 2倍の数列を考えればOK
AA = A + A
# 累積和を計算．初期値は0とする．
cumAA = [0]*(2*N + 1)
for i in range(2*N):
cumAA[i+1] = AA[i] + cumAA[i]
# 累積和のハッシュ関数を作成．
setCumAA = set(cumAA)
# 累積和の値を一つずつみる
for cum in cumAA:
# 累積和からSを引いてみる
sub = cum - S
# その値が累積和に存在するかどうかを見る
if (sub in setCumAA):
# あればYes
print("Yes")
exit()
# 見つからなかったらNo
print("No")
E問題
- 再帰的に探索を行う．ただし，倒す順番はヒープで最弱を指定する．
- 重複の無いように，スライムを既に倒したかどうか(
killed)は管理する．
E.py
"""
<方針>
- 再帰的に探索を行う．ただし，倒す順番はヒープで最弱を指定する．
- 重複の無いように，スライムを既に倒したかどうか(`killed`)は管理する．
"""
import heapq
# 入力
H, W, XX = map(int, input().split())
P, Q = map(int, input().split())
SS = [list(map(int, input().split())) for _ in range(H)]
P -= 1
Q -= 1
killed = [[False]*W for _ in range(H)]
# 🛡️高橋くん🗡️の強さ
power = 0
# ヒープでスライムを倒していく．
## 強さ，縦インデックス，横インデックス
q = [[SS[P][Q], P, Q]]
# ヒープを回す
while q:
# 強さ，縦インデックス，横インデックス
p, y, x = heapq.heappop(q)
# 既に倒されたかどうかを判定
if killed[y][x]:
continue
else:
killed[y][x] = True
# 最初 or 倒せる条件のとき
if power==0 or p<power/XX:
# 🛡️高橋くん🗡を強化する
power += p
# 近傍を探索
for (dy, dx) in [
(0, 1),
(1, 0),
(0, -1),
(-1, 0),
]:
Y = y + dy
X = x + dx
# 枠内のとき
if (0<=Y<H) and (0<=X<W):
# TLE回避のために，自明な倒されたスライムは登録しない．
if not killed[Y][X]:
# そのスライムをヒープに登録する．
heapq.heappush(q, [SS[Y][X], Y, X])
# 近傍で最弱のスライムすら倒せない🛡️高橋くん🗡は引退してもらう
else:
break
# 出力
print(power)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 風邪が治ってないかもしれない🥺