【Atcoder】【Python】分野別　初中級者が解くべき過去問精選 100 問を解いてみた（全探索：全列挙）

はじめに

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

1.ITP1_7_B - How Many Ways?

問題のリンクは、こちら

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

answer1

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$が存在すればいいことに気づけます。
そのため、別解は、以下のようになります。

answer2

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^2) ≤ O(10^8)$になり、十分高速です。

約数の数えあげ方は、数え上げたい数字を$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^2) ≤ O(10^8)$となり、間に合いそうです。

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)

最後に

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