[ABC429] ABC 429(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)

A問題

• if を使って条件分岐

A.py

"""
<方針>
- `if` を使って条件分岐
"""
# 入力
N, M = map(int, input().split())

# 繰り返し出力
for i in range(N):
  # 条件分岐
  if(i<M):
    print("OK")
  else:
    print("Too Many Requests")

B問題

• 総和を求めておく su
• あとは、(su - A[i]) == M となるところを探せば良い。

B.py

"""
<方針>
- 総和を求めておく `su`
- あとは、`(su - A[i]) == M` となるところを探せば良い。
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

# 総和
su = sum(A)

# 一個減らして同じになるところがあるかどうか
if(any([((su - a) == M) for a in A])):
  print("Yes")
else:
  print("No")

C問題

方針

• 全てのペアを試していたら、O(N^3) になり、とても間に合わない
• 結局それぞれの数字が何個ずつあればわかれば、解析的に求まりそう
• 同一の数字を２個取り出して、それ以外の数字の個数で積を取れば良さそう (c*(c-1)//2)*(N-c)
• 全体として、O(N) でいけそう

前提

• C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
• AとB問題では，基本的に制約条件を見ずにやっても解ける．
• しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
• 詳しい話は私の352回の記事 のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- 全てのペアを試していたら、`O(N^3)` になり、とても間に合わない
- 結局それぞれの数字が何個ずつあればわかれば、解析的に求まりそう
- 同一の数字を２個取り出して、それ以外の数字の個数で積を取れば良さそう `(c*(c-1)//2)*(N-c)`
- 全体として、`O(N)` でいけそう
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# それぞれの数字をカウントする
C = [0]*(N+1)
for a in A:
  C[a] += 1

# それぞれの数字を２個選んだ時で考える
ans = 0
for c in C:
  ans += (c*(c-1)//2)*(N-c)

# 出力
print(ans)

補足

関係するリンク(参考文献など)

• 今回のコンテスト

筆者について

• Atcoderアカウント
• 今回も不参加のため，成績なし．
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出

その他

• 間違いを含んでいる可能性があります．
• 方針と言いつつ，方針ではない感想などを書いている可能性があります．
• A問題から解説がだんだん省略されます．
• コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

• 学会発表ェ...