[ABC377] ABC 377(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 文字を一つずつ見て，
ABCが全て存在していれば，並び替えればABCになると言える．
A.py
"""
<方針>
- 文字を一つずつ見て， `A` `B` `C` が全て存在していれば，並び替えれば `ABC` になると言える．
"""
# 入力
S = input()
# それぞれの文字が存在したかを記録するフラグ
a_exist = False
b_exist = False
c_exist = False
# 全ての文字を見る
for s in S:
# Aだった
if s == "A":
a_exist = True
# Bだった
if s == "B":
b_exist = True
# Cだった
if s == "C":
c_exist = True
# 全部存在してたら
if a_exist and b_exist and c_exist:
# 並び替えてABCになる
print("Yes")
# そうでなければ
else:
# 不可能
print("No")
B問題
- どこにコマを置くことができるかの変数
okを作る．最初はTrueのリストで初期化しておく． - 入力を受け取り，ルーク
#があったら，それが移動できる場所をok上でFalseにする． - 最後まで残った
ok上のTrueをカウントすればいける．
B.py
"""
<方針>
- どこにコマを置くことができるかの変数 `ok` を作る．最初は `True` のリストで初期化しておく．
- 入力を受け取り，ルーク `#` があったら，それが移動できる場所を `ok` 上で `False` にする．
- 最後まで残った `ok` 上の `True` をカウントすればいける．
"""
# 盤面の大きさ
N = 8
# 駒がおける場所
ok = [[True]*N for i in range(N)]
# 入力を受け取る
for i in range(N):
# 入力
S = input()
for j, s in enumerate(S):
# ルークがあったとき
if s == "#":
# 横方向の更新
for ind in range(N):
ok[i][ind] = False
# 縦方向の更新
for ind in range(N):
ok[ind][j] = False
# おける場所をカウント
ans = 0
for i in range(N):
for j in range(N):
if ok[i][j]:
ans += 1
# 出力
print(ans)
C問題
方針
- B問題と同じように盤面を作るところから始めると，
Nがデカすぎるため，O(N^2)はとても間に合わない． - 盤面は作らずとも，ナイトの可動域を登録すれば十分である．
- 重複の無いように，全てのナイトの可動域を登録すれば良い．
-
setを使うと，重複の無い追加がO(1)でできる． - 高々
M個のクイーンで前述の処理をするので，O(M)により間に合う． - テクニック
-
0-indexedでやる - ナイトの可動域はリストを作成して，
forでまとめてやる -
setの値はintにするため，縦横のいずれかの値をN倍すると上手くいく．
-
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- B問題と同じように盤面を作るところから始めると， `N` がデカすぎるため， `O(N^2)` はとても間に合わない．
- 盤面は作らずとも，ナイトの可動域を登録すれば十分である．
- 重複の無いように，全てのナイトの可動域を登録すれば良い．
- `set` を使うと，重複の無い追加が `O(1)` でできる．
- 高々 `M` 個のクイーンで前述の処理をするので， `O(M)` により間に合う．
- テクニック
- `0-indexed` でやる
- ナイトの可動域はリストを作成して， `for` でまとめてやる
- `set` の値は `int` にするため，縦横のいずれかの値を `N` 倍すると上手くいく．
"""
# 入力
N, M = map(int, input().split())
# ナイトの可動域
se = set()
# 全てのナイトを処理する
for i in range(M):
# 入力
a, b = map(int, input().split())
# 0-indexed
a, b = a-1, b-1
# ナイトの可動域を全て確認する
for x, y in [
(0, 0),
(1, 2),
(1, -2),
(-1, 2),
(-1, -2),
(2, 1),
(2, -1),
(-2, 1),
(-2, -1),
]:
# ナイトの移動先
A = a + x
B = b + y
# ナイトの移動先が盤面の中のとき
if(0<=A<N and 0<=B<N):
# 縦方向の値をN倍したものをナイトの可動域に追加する．(setへの追加なので，重複の無い追加)
se.add(A*N + B)
# 盤面の全体の広さから，ナイトの可動域を引くと答え．(len(se)はO(M)の処理)
print(N**2 - len(se))
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 時間ない ABCのみ 復習を