Atcoder水色への精選 100 問 全探索 : 全列挙(Python)

E869120さんが作成した、精選100問を解いていきます
今回は1~4までの「全探索 : 全列挙」をやります
qiita.com

目次

1　How many ways?

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

２つ目までの範囲を決めたときの残った３番目の要素が目的の数値に等しいかをカウントします
（ちなみに３番目までを全探索したときでも程度なので間に合うっぽい）

pythonでの実装例

li = []

while True:
    n,m = map(int,input().split())
    if n == 0 and m == 0:
        break
    li.append((n,m))

for n,m in li:
    point = 0
    for one in range(1,n-1):
        for two in range(one+1,n):
            three = m-one-two
            if two < three < n+1:
                point += 1
    print(point)

2　B - 105

問題文
atcoder.jp

１からNまでの奇数のうち、各数字の約数を全列挙したときの長さが８のものの個数をカウントします

pythonでの実装例

n = int(input())

# 約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

point = 0

# 奇数全探索
for i in range(1,n+1,2):
    j = make_divisors(i)
    if len(j) == 8:
        point += 1

print(point)

3　AtCoder Beginner Contest 122 B - ATCoder

問題文
atcoder.jp

部分文字列を全探索していきます(空文字は除く)
部分文字列の先頭と終了地点を決め、作られた文字列がACGT文字列だった場合をカウントします
ACGT文字列だった場合、さらに文字列の長さが今までのACGT文字列よりも長かった場合、更新をします
フラグ管理やmax関数を使うと便利です

pythonでの実装例

s = input()
n = len(s) # 文字の長さ
max_length = 0 # 最大長さ

for i in range(n):
    for j in range(i,n):
        t = s[i:j+1]
        flag = True # ACGT文字列であるかのフラグ
        for k in t:
            if k not in "AGCT":
                flag = False
        if flag:
            max_length = max(max_length,len(t))

print(max_length)

4　C - カラオケ

問題文
atcoder.jp

1曲目と2曲目の組み合わせを求めておき、各パターンの得点を数えます
得点が過去の最大値を上回った場合は更新をします

pythonでの実装例

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

ans = 0

# 1曲目と2曲目を全探索する
for i in range(m-1):
    for j in range(i+1,m):
        point = 0
        # n人が曲を歌った時の得点を求める
        for k in range(n):
            point += max(a[k][i],a[k][j])
        # 最大値を更新 
        ans = max(ans,point)

print(ans)

次回↓
工夫して通り数を減らす全列挙
algo-archit.hatenablog.com