[ABC393] ABC 393(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 条件を全パターン考えれば良い。
A.py
"""
<方針>
- 条件を全パターン考えれば良い。
"""
# 入力
S1, S2 = input().split()
if(S1 == "sick" and S2 == "sick"):
print(1)
if(S1 == "sick" and S2 == "fine"):
print(2)
if(S1 == "fine" and S2 == "sick"):
print(3)
if(S1 == "fine" and S2 == "fine"):
print(4)
B問題
-
Aの位置aを全て考える。 - 間隔
dを全て考える。 -
Bの位置はa+dで、Cの位置はa+2*dとなるので、あとはカウントするだけ。
B.py
"""
<方針>
- `A` の位置 `a` を全て考える。
- 間隔 `d` を全て考える。
- `B` の位置は `a+d` で、`C` の位置は `a+2*d` となるので、あとはカウントするだけ。
"""
# 入力
S = input()
# 長さ
N = len(S)
# カウント数
ans = 0
for a in range(N):
for d in range(N):
# index out of range 対策
if(a+2*d<N):
a = a+0*d
b = a+1*d
c = a+2*d
# A, B, Cが存在するかどうか
if(
S[a] == "A" and
S[b] == "B" and
S[c] == "C"
):
# カウントアップ
ans += 1
# 出力
print(ans)
C問題
方針
-
u = vとなっているところは切り取って良い。 -
u != vとなっているところは、u < vにソートして、(N+1)*u + vとして辞書に登録する。 - 辞書で
2つ以上要素があるものを切り取っていけば良い。 - 辞書は
defaultdictを使うとkeyを見なくて良いから便利。 - 全体として、辺を見る分だけ、
O(M)かかる。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `u = v` となっているところは切り取って良い。
- `u != v` となっているところは、`u < v` にソートして、`(N+1)*u + v` として辞書に登録する。
- 辞書で `2` つ以上要素があるものを切り取っていけば良い。
- 辞書は `defaultdict` を使うと `key` を見なくて良いから便利。
- 全体として、辺を見る分だけ、`O(M)` かかる。
"""
# ライブラリ
from collections import defaultdict
# 答え
cut = 0
# 辞書
di = defaultdict(int)
# 入力
N, M = map(int, input().split())
for _ in range(M):
u, v = map(int, input().split())
# 同じ時
if(u == v):
cut += 1
continue
# u < v に直す
elif(u > v):
u, v = v, u
# 辞書に登録
key = (N+1)*u + v
di[key] += 1
# 同じ辺をカットする。
for ke, va in di.items():
cut += (va-1)
# 出力
print(cut)
D問題
- 左右から
"1"を近づけていく。 - 動かすのは、
"1"が溜まってない方にする。
D.py
"""
<方針>
- 左右から `"1"` を近づけていく。
- 動かすのは、`"1"` が溜まってない方にする。
"""
# 入力
N = int(input())
S = input()
# 1が一つの時は例外処理
if S.count("1") == 1:
print(0)
exit()
# 一番左の1を見つける。
for l in range(N):
if S[l] == "1":
break
# 一番右の1を見つける。
for r in reversed(range(N)):
if S[r] == "1":
break
# 動かした数
ans = 0
# 現在左に1が溜まってる数。
cL = 1
# 現在左に1が溜まってる数。
cR = 1
# 左右が隣り合うまで続ける。
while l+1 != r:
# 左の方が少ない時
if(cL < cR):
# 左を動かす
for l in range(l+1, r):
# 1が見つかった時、
if S[l] == "1":
# 溜まってる1を更新する。
cL += 1
break
# 0の時、
else:
# 溜まってる1を動かす。
ans += cL
# 右の方が少ない時も上記と同等の処理
else:
for r in reversed(range(l+1, r)):
if S[r] == "1":
cR += 1
break
else:
ans += cR
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- キーボードの句読点を変更しました。