[ABC426] ABC 426(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 辞書に順番の番号を登録しておく。
- その番号の大小を見れば良い。
A.py
"""
<方針>
- 辞書に順番の番号を登録しておく。
- その番号の大小を見れば良い。
"""
# 入力
X, Y = input().split()
# 辞書を作成。
di = {
"Lynx": 0,
"Serval": 1,
"Ocelot": 2,
}
# 大小を確認し、出力する。
if(di[X] <= di[Y]):
print("Yes")
else:
print("No")
B問題
- 辞書で文字を
keyとして管理する。 -
valueが1のところを出力すれば良い。
B.py
"""
<方針>
- 辞書で文字を `key` として管理する。
- `value` が `1` のところを出力すれば良い。
"""
# 入力
S = input()
# 辞書を構築
di = {}
# 文字を一つずつ見る
for s in S:
# 文字のカウントを増やす。
if(s in di):
di[s] += 1
# 文字を初めて登録する。
else:
di[s] = 1
# 辞書を全て取り出す。
for ke, va in di.items():
# カウントが一つの時、
if(va == 1):
# 文字を出力する。
print(ke)
C問題
方針
- 毎クエリ
O(Q)で全てのPCのバージョンを見てO(N)しまうと、O(NQ)で間に合わない。 - PCのバージョンがそれぞれ何個あるか
versionsを持たせる。 - 常に最低バージョンが何か
miを保持させておけば、毎クエリN個も見ることはない。 - したがって、全体として、
O(N+Q)で処理できる。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 毎クエリ `O(Q)` で全てのPCのバージョンを見て `O(N)` しまうと、`O(NQ)` で間に合わない。
- PCのバージョンがそれぞれ何個あるか `versions` を持たせる。
- 常に最低バージョンが何か `mi` を保持させておけば、毎クエリ `N` 個も見ることはない。
- したがって、全体として、`O(N+Q)` で処理できる。
"""
N, Q = map(int, input().split())
# i番目のバージョンを持つPCはいくつあるか。
versions = [1]*N
# 存在する最低バージョン
mi = 0
for _ in range(Q):
X, Y = map(int, input().split())
X -= 1
Y -= 1
# 更新するPCの個数をカウント
ans = 0
# 最低バージョンからループさせれば、間に合う。
for i in range(mi, X+1):
ans += versions[i]
versions[i] = 0 # ここはコメントアウトしても多分通る。
# 個数を変える
versions[Y] += ans
# PCを更新できたら、そのバージョンが最低バージョンとなる。
if(ans > 0):
mi = X+1
# 出力
print(ans)
D問題
- 全部
"0"or"1"のうち最適な方を選べばいい。なので、一回全部"0"にする方針で考える。 - 端っこから考えていき、
"1"と出会った時は、"0"にして、最初から"0"のところに入れれば良い。 - 端っこに
"0"が出てきた時は、仕方がないので、"1"にして、端っこに入れて、すぐ上記の処理を行えばいい。 - となると、一番
"0"が連続しているところに"0"を入れていけば良さそう。 - なので、一番連続しているところを
Co_0、"0"の個数をCu_0として、N - 2*CoN_0 + CoU_0で計算できる。
D.py
"""
<方針>
- 全部 `"0"` or `"1"` のうち最適な方を選べばいい。なので、一回全部 `"0"` にする方針で考える。
- 端っこから考えていき、`"1"` と出会った時は、 `"0"` にして、最初から `"0"` のところに入れれば良い。
- 端っこに `"0"` が出てきた時は、仕方がないので、`"1"` にして、端っこに入れて、すぐ上記の処理を行えばいい。
- となると、一番 `"0"` が連続しているところに `"0"` を入れていけば良さそう。
- なので、一番連続しているところを `Co_0` 、`"0"` の個数を `Cu_0` として、`N - 2*CoN_0 + CoU_0` で計算できる。
"""
# 連続部分でグループ化できるライブラリ
from itertools import groupby
T = int(input())
for _ in range(T):
N = int(input())
S = input()
groups = [[k, len(list(g))] for k, g in groupby(S)]
# 連続する長さでソート
groups.sort(key=lambda x: -x[1])
# 0 と 1 で分ける。番兵も加えておく。
coN_0 = list(filter(lambda x: x[0] == "0", groups)) + [["0", -1]]
coN_1 = list(filter(lambda x: x[0] != "0", groups)) + [["1", -1]]
# 連続する最大個数を取得する。
CoN_0 = coN_0[0][1]
CoN_1 = coN_1[0][1]
# カウント
CoU_0 = S.count("0")
CoU_1 = S.count("1")
# 答え
ans = min(
N-2*CoN_0 + CoU_0,
N-2*CoN_1 + CoU_1
)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 全てのインターンシップが終了したぜええええ！！
- 本当にありがとう。
- なんとか前に進めそうです。