[ABC398] ABC 398(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 偶数の時
-
=は2つ真ん中に入れる。左右それぞれに-をN//2 - 1つ入れる。
-
- 奇数の時
-
=は1つ真ん中に入れる。左右それぞれに-をN//2つ入れる。
-
A.py
"""
<方針>
- 偶数の時
- `=` は `2` つ真ん中に入れる。左右それぞれに `-` を `N//2 - 1` つ入れる。
- 奇数の時
- `=` は `1` つ真ん中に入れる。左右それぞれに `-` を `N//2` つ入れる。
"""
# 入力
N = int(input())
# 偶数の時
if(N%2 == 0):
left = right = "-" * (N//2 - 1)
mid = "=" * 2
# 奇数の時
else:
left = right = "-" * (N//2)
mid = "=" * 1
# 出力
print(left + mid + right)
B問題
- それぞれのカードが何枚あるかをカウントする。
-
3枚以上が1種類以上存在し、2枚以上が2種類以上存在していれば、Yes。
B.py
"""
<方針>
- それぞれのカードが何枚あるかをカウントする。
- `3` 枚以上が `1` 種類以上存在し、`2` 枚以上が `2` 種類以上存在していれば、`Yes` 。
"""
# 入力
A = list(map(int, input().split()))
# カードの種類を管理
C = [0]*14
# カードの種類を集計
for a in A:
C[a] += 1
# 3枚以上と2枚以上をカウント
cnt3 = 0 #3枚以上
cnt2 = 0 #2枚以上
for c in C:
if(c>=3):
cnt3 += 1
if(c>=2):
cnt2 += 1
# 判定
if(
(cnt3 >= 1) and
(cnt2 >= 2)
):
print("Yes")
else:
print("No")
C問題
方針
-
Aとして存在しない値まで管理するとO(A)で到底間に合わない。 - 辞書
diを使うことで、Aとして存在する値だけにし、O(N)で間に合わせる。 - 線形走査を意識して処理をする。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `A` として存在しない値まで管理すると `O(A)` で到底間に合わない。
- 辞書 `di` を使うことで、`A` として存在する値だけにし、`O(N)` で間に合わせる。
- 線形走査を意識して処理をする。
"""
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
# 辞書
## key: Aの値
## val: Aの値の重複数
di = defaultdict(int)
for a in A:
di[a] += 1
ma = 0 # 最大値
for ke, va in di.items():
# 重複が無い時
if(va == 1):
# 最大値を更新
ma = max(ma, ke)
# 最大値に合致する番号を見つける。
for i, a in enumerate(A):
# 最大値合致したとき
if(a == ma):
# 番号を出力
print(i+1)
exit()
# 最大値が見つから無い時
print(-1)
D問題
- 煙を
setで管理し、焚き火と高橋君を移動させる。
D.py
"""
<方針>
- 煙を `set` で管理し、焚き火と高橋君を移動させる。
"""
N, R, C = map(int, input().split())
S = input()
# 煙
se = set()
# 煙をsetに登録する関数
def id(y, x):
return y*(N+1) + x
# <デバッグ用> setに登録されている煙の座標を取得
def deId(id):
return divmod(id, (N+1))
# 焚き火の初期位置
y = x = 0
# 答え
ans = []
# 時間を進める
for s in S:
# 風の方向を取得
match s:
case "N":
dy = -1
dx = 0
case "W":
dy = 0
dx = -1
case "S":
dy = +1
dx = 0
case "E":
dy = 0
dx = +1
# 高橋君を移動させる。
R -= dy
C -= dx
# 煙を登録
se.add(id(y, x))
# 高橋君が煙とかぶっているかどうか。
ans.append("1" if id(R, C) in se else "0")
# print(y, x, R, C, list(map(deId, se)))
# 焚き火を移動
y -= dy
x -= dx
# 出力
print("".join(ans))
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- AtCoderのDiffが確認できない...