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

A問題

• 等差数列の公式を使おう。

A.py

"""
<方針>
- 等差数列の公式を使おう。
"""
# 入力
N = int(input())

# 総和
ans = N*(N+1)//2

# 出力
print(ans)

B問題

• 部分列を全パターン取得する
• 約数があるかどうかを余りで考える

B.py

"""
<方針>
- 部分列を全パターン取得する
- 約数があるかどうかを余りで考える
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 個数
ans = 0
# l~r
for l in range(N):
  for r in range(l+1, N):
    # 総和
    su = sum(A[l:r+1])
    
    # 条件を満たすかのフラグ
    ok = True
    for i in range(l, r+1):
      # 約数のとき、
      if(su%A[i] == 0):
        ok = False
    
    # 条件を満たした時、
    if(ok):
      ans += 1

# 出力
print(ans)

C問題

方針

• それぞれのドミノがどれだけ倒せるかを考えてしまうと、O(N^2) もかかってしまう。
• どれだけ右を倒せるか r を管理して、左から一度走らせるだけにする O(N)

前提

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

C.py

"""
<方針>
- それぞれのドミノがどれだけ倒せるかを考えてしまうと、`O(N^2)` もかかってしまう。
- どれだけ右を倒せるか `r` を管理して、左から一度走らせるだけにする `O(N)`
"""
N = int(input())
A = list(map(int, input().split()))

# 今見てるドミノ
now = 0
# 倒せるところ
r = 0

# 倒せるところまで進めてみる
while now<=min(r, N-1):
  # 右側を更新
  r = min(max(r, now+A[now]-1), N-1)
  
  # 右に進める
  now += 1

# 個数を出力
print(r+1)

補足

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

• 今回のコンテスト

筆者について

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

その他

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

最後に一言

• ｸｪ…