ABC359(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
- 最初に受け取った値
N
の回数だけ,文字列を受け取る. - 受け取ったそれぞれの文字列
s
がTakahashi
と一致した回数をカウントする. -
Takahashi
と一致した回数を出力して終了する.
A.py
"""
<方針>
- 最初に受け取った値 `N` の回数だけ,文字列を受け取る.
- 受け取ったそれぞれの文字列 `s` が `Takahashi` と一致した回数をカウントする.
- `Takahashi` と一致した回数を出力して終了する.
"""
# 標準入力から値を受け取る.
N = int(input())
# Takahashi と何回一致したかをカウントする変数.
ans = 0
# N回文字列を受け取る.
for i in range(N):
# 文字列を受け取る.
s = input()
# 受け取った文字列が Takahashi と一致した時,
if(s=="Takahashi"):
# カウントを増やす.
ans += 1
# Takahashi と一致した回数を出力して終了.
print(ans)
B問題
- 人を左から順番に,二人先も同時に見ていく.
- 服の色が同じだったら,カウントを増やす.
- 二人先も見るので,最後と最後から二番目の人は右側に人が存在しないことに注意する.
B.py
"""
<方針>
- 人を左から順番に,二人先も同時に見ていく.
- 服の色が同じだったら,カウントを増やす.
- 二人先も見るので,最後と最後から二番目の人は右側に人が存在しないことに注意する.
"""
# 標準入力を受け取る.
N = int(input())
A = list(map(int, input().split()))
# 間に人がいる状態で,服の色が同じ回数を記録する変数.
ans = 0
# 人を左から順番に,最後と最後から二番目の人以外を順番に見ていく.
for i in range(2*N-2):
# 二つ右側の人と服の色が同じだったら,
if(A[i]==A[i+2]):
# カウントを増やす.
ans += 1
# 答えを出力する.
print(ans)
C問題
- 公式解説と一緒です.
C.py
"""
<方針>
- 公式解説と一緒です.
"""
xS, yS = map(int, input().split())
xT, yT = map(int, input().split())
# タイルを左に寄せる.
if (xS + yS) % 2 == 1:
xS -= 1
if (xT + yT) % 2 == 1:
xT -= 1
# 横の距離と縦の距離
xD = abs(xS - xT)
yD = abs(yS - yT)
# 答え
ans = (yD + max(xD, yD)) // 2
print(ans)
D問題
- 公式解説通りです.
D.py
"""
<方針>
- 公式解説通りです.
"""
N, K = map(int, input().split())
S = input()
mod = 998244353
# keyを長さ(K-1)の文字列として,valueがその部分文字列を含み,良い文字列となるパターンの総数.
# この部分文字列を文字の頭からずらしながら観測する.最初の文字よりも前に番兵として,"A, B, ?"でもない"C"で埋めておく.
ans = { "C"*(K-1) : 1 }
# 文字を一つずつ見ていく.
for s in S:
# sが"A"であれば,"A"を追加する."B"であれば,"B"."?"であれば,両パターンの"A"と"B"をそれぞれ追加する.
tmp = {}
if(s == "A" or s == "?"):
tmp |= { k + "A" : v for k, v in ans.items()}
if(s == "B" or s == "?"):
tmp |= { k + "B" : v for k, v in ans.items()}
# 一個前の情報を消して,次に渡す情報のために初期化を行う.
ans = {}
# 部分文字列を一つずつみる.
for k, v in tmp.items():
# 良い文字列の条件を満たすとき,
if(k != k[::-1]):
# 既に,登録されている文字列のときは,値を増やす.
if(k[1:] in ans):
ans[k[1:]] += v
ans[k[1:]] %= mod
# 登録されていなければ,そのまま次に渡す情報のキーを増やして登録する.
else:
ans[k[1:]] = v
# valueの値の総和が答え.
print(sum(ans.values())%mod)
E問題
- 公式解説の「方針1」の解法と一緒です.
E.py
"""
<方針>
- 公式解説の「方針1」の解法と一緒です.
"""
from collections import deque
N = int(input())
H = list(map(int, input().split()))
# 答え
ans = [-1]*N
# 入れた水の総量
water = 0
# スタック.
# 第一引数:水が入っている横(width)の長さ
# 第二引数:水が入っている縦(height)の長さ
q = deque()
# 水がどのくらい必要なのかを一つずつ見ていく.
for i in range(N):
# 今回水を満タンにするには,今回の右側にある板と同じ高さの水がどれだけ必要か.
cnt = 1
# 今回の右側にある板以上の高さの水が見つかるまで,既に入れた水を右から順番に抜いていく.
while q and q[-1][1] < H[i]:
# 右側にある水を選択する.
w, h = q.pop()
# 水を抜く.
water -= w*h
# 抜いた水の横の長さだけ,今回満タンするのに必要な水は増える.
cnt += w
# 水を溢れるギリギリまで入れる
q.append((cnt, H[i]))
water += cnt*H[i]
# 既に入れた水に1を足せば,ちょうど溢れる.
ans[i] = water + 1
# 出力
print(*ans)
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります.
- 方針と言いつつ,方針ではない感想などを書いている可能性があります.
- A問題から解説がだんだん省略されます.
- コードに書かれている解説の文言と,その上に書いてある解説の文言を変えている場合があります.
最後に一言
- C解けなかった🥺