はじめに

E869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】にまとめている「分野別　初中級者が解くべき過去問精選 100 問」をPythonで解いてみた。Pythonの記事は少なそうなのでアウトプットが参考になれば幸いです。

1.ITP1_7_B - How Many Ways?

問題のリンクは、こちら

1問目ということで、愚直に全探索すればよさそうです。
3重ループでO(n²) ≤ O(10⁸)なので間に合いそう。(n, xが0になるまでループだから本当は怪しい気もする)

while True:
  n, x = map(int, input().split())
  if n == 0 and x == 0: break
  continuous_arr = list(range(1,n+1))
  cnt = 0
      
  for i in continuous_arr:
    for j in range(i+1, n+1):
      for k in range(j+1, n+1):
        if i + j + k == x: cnt += 1
print(cnt)

上の解法でもACできますが，2重ループでもこの問題は解けるので別解も載せようと思います。

i + j + k = x(1 ≤ i < j < k ≤ n)

という条件をkについて移項すると、

k = x - i - j (j < k ≤ n)

という条件を満たすkが存在すればいいことに気づけます。
そのため、別解は、以下のようになります。

while True:
  n, x = map(int, input().split())
  if n == 0 and x == 0: break
  continuous_arr = list(range(1,n+1))
  cnt = 0
  
  for i in continuous_arr:
    for j in range(i+1, n+1):
      k = x - i - j
      if k > j and k <= n: cnt += 1 
print(cnt)

2.AtCoder Beginner Contest 106 B - 105

問題のリンクは、こちら

この問題は、約数を数えあげる全探索をして、そのあとにNまでの約数の個数のうち
8個約数を持つ個数を数え上げます。
そのため、計算量はO(n²) ≤ O(10⁸)になり、十分高速です。

約数の数えあげ方は、数え上げたい数字をkとすると、
kまでfor分で割り切れるか判定すればいいです。
そのため、以下のようになります。

def divisor_cnt(number):
  cnt = 0
  for i in range(1, number + 1):
    if number % i == 0: cnt += 1
    return cnt

n = int(input())
ans = 0

for i in range(1, n+1, 2):
  if divisor_cnt(i) == 8: ans += 1
print(ans) 

3.AtCoder Beginner Contest 122 B - ATCoder

問題のリンクは、こちら

この問題は、まず先頭の文字に着目して次の文字がA,C,G,Tのどれかであるならカウントを+1してその次の文字を確認する作業を繰り返します。
違う文字なら先頭から2番目の文字を先頭として再度探索を始める。違う文字がでたときに、答えの候補として長さを保持しておく。この答えの候補の最大値は答えになります。
探索していけばO(n^2) ≤ O(10^8)に収まり、高速です。

s = input()
ans = 0
char = ["A", "T", "C", "G"]

for i in range(len(s)):
  cnt = 0
  for j in range(i,len(s)):
    if s[j] not in char: break
    cnt += 1
    
  ans = max(ans, cnt)
    
print(ans)

4.パ研杯2019 C - カラオケ

問題のリンクは、こちら

入力が行列になり、複雑そうに見えますが慌てず1行でみると今までの全探索と変わりません。
曲の選び方の全探索は、1 ≤ T_1 < T_2 ≤ Mという条件にすると、2重ループで網羅できそうです。この全探索に、生徒数nのループを加えることで合計点を出します。
その合計点のうち最大値になるものが答えです。
計算量は、O(nm²) ≤ O(10⁸)となり、間に合いそうです。

n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for t_1 in range(m):
  for t_2 in range(t_1+1,m):
    group_score = 0
    for i in range(n):
      group_score += max(a[i][t_1], a[i][t_2])  
    ans = max(ans, group_score)      
print(ans)

最後に

はじめての記事なので、つたない部分があると思いますがご容赦ください。
今後は、続きの分野も挙げていこうと思っています。よろしくおねがいします。