[ABC424] ABC 424(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 三角形であることを確認する（
2*max(edges) < sum(edges)）。 - 二等辺三角形であることを確認する（
len(set(edges)) <= 2）。
A.py
"""
<方針>
- 三角形であることを確認する（`2*max(edges) < sum(edges)`）。
- 二等辺三角形であることを確認する（`len(set(edges)) <= 2`）。
"""
# 入力
edges = list(map(int, input().split()))
# 三角形であることを確認する
if not (2*max(edges) < sum(edges)):
# 三角形ではない
print("No")
# プログラムを終了
exit()
# 二等辺三角形であることを確認する
if not (len(set(edges)) <= 2):
# 二等辺三角形ではない
print("No")
# プログラムを終了
exit()
# ここまで来たら、二等辺三角形だ！
print("Yes")
B問題
- 問題の回答状況を表現する二重リスト
answerを使う。 -
answer[i]が全てTrueになったら、全問正解者リストcompleteに追加する。
B.py
"""
<方針>
- 問題の回答状況を表現する二重リスト `answer` を使う。
- `answer[i]` が全て `True` になったら、全問正解者リスト `complete` に追加する。
"""
# 入力
N, M, K = map(int, input().split())
# 回答状況を表現
answer = [[False]*M for _ in range(N)]
# 全問正解者を管理
complete = []
# イベントを順番に処理
for _ in range(K):
# 入力
A, B = map(int, input().split())
# 0-index
A -= 1
B -= 1
# 回答状況を更新
answer[A][B] = True
# Aが全て答えれたかどうか
if(all(answer[A])):
# 0-indexに注意
complete.append(A+1)
# 出力
print(*complete)
C問題
方針
- 入力を上からイベントとして順序を守って処理すると
WAを食らう。- 順序は任意でどのスキルが取得できるかどうか。
- とはいえ、全ての順序を考えることは厳しい
O(N!)
- そこで、スキルの依存関係グラフを構築する
O(N) - そして、依存関係グラフを
(0, 0)の位置から開始するO(N) - 無駄な徘徊（
O(N^2)）をしないように、すでに習得しているスキルが出てきたら探索を切る
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 入力を上からイベントとして順序を守って処理すると `WA` を食らう。
- 順序は任意でどのスキルが取得できるかどうか。
- とはいえ、全ての順序を考えることは厳しい `O(N!)`
- そこで、スキルの依存関係グラフを構築する `O(N)`
- そして、依存関係グラフを `(0, 0)` の位置から開始する `O(N)`
- 無駄な徘徊（`O(N^2)`）をしないように、すでに習得しているスキルが出てきたら探索を切る
"""
# 入力
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
# 取得したスキル
skills = [False]*N
# 始めから持ってるスキル一覧
start = []
# スキル依存グラフ
## E[u] = [v1, v2, ..., vi, ...]
## スキル u を手に入れたら、vi が取得できる。
E = [[] for _ in range(N)]
# 依存グラフの構築
for i in range(N):
A, B = AB[i]
# 始めから持ってるスキル
if(A == B == 0):
start.append(i)
skills[i] = True
# スキル取得には依存がある
for X in [A, B]:
# スキルのとき
if not (X == 0):
# X（A, B） を取得した時、iが手に入る
E[X-1].append(i)
# 始めから持ってるスキルを初期値として、全て試す
for s in start:
# 非再起探索リスト
q = [s]
while q:
u = q.pop() # DFS
# 探索
for v in E[u]:
# 取得してないスキルのとき、
if not (skills[v]):
q.append(v)
skills[v] = True
# 出力
print(sum(skills))
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 最近競プロ力が落ちてる気がする。Dが解けない...精進しないとな...