今年中に水色になりたい緑コーダーが過去問精選 100 問の「全探索:全列挙」を解いた

親記事は→今年中に水色になりたい緑コーダーが「初中級者が解くべき過去問精選 100 問」を解く

全探索:全列挙って何?

文字通り、あり得るパターンを全部試すよ、な手法。
人間がやると時間かかりすぎな組み合わせの個数でもプログラム君なら楽々やってくれる。
コンピュータ、ありがてー。

問題と解説

1. ITP1_7_B - How Many Ways?

問題リンク

問題概要

整数nとxが入力。
1からnまでの数の中から、重複しないよう3つの数を選んで、合計がxとなる組み合わせの数を求めろ。

回答

ITP1_7_B.py

while 1:
    # n,xを読込む
    n,x = map(int, input().split())

    if n == 0 and x == 0:
        # 「n,xがともに0のとき入力の終わりとします」なので終了
        exit()
    else:
        ans = 0     # 合計がxとなる組み合わせの数
        
        # 1～nまでの数の中から重複しないように3つの数i,j,kを選ぶ
        # nまでなので,range(1,n+1)。重複しないように,j,kは前に選んだ数+1からスタート
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                for k in range(j+1,n+1):
                    # 選んだ数の合計がxになるかを確認
                    if i + j + k == x:
                        # なるなら合計がxとなる組み合わせの数のカウントを+1
                        ans += 1
        
        # 全部の組み合わせを試したので、回答を出力
        print(ans)

あれ、TLEするんじゃ(後述)と思ったけど、通った。

2. AtCoder Beginner Contest 106 B - 105

問題リンク

問題概要

整数Nが入力。
1からN以下の数の中で、奇数かつ約数がちょうど8個になる数の個数を求めろ。

回答

ABC106_B.py

def make_divisors(n):
    '''
    nの約数のリストを生成する
    ref : https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56
    '''
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
N = int(input())
ans = 0     # 約数をちょうど8個持つ奇数の数

# 1～Nの奇数を全部試してみる
for i in range(1,N+1,2):
    if len(make_divisors(i))==8:
        # 約数の個数が8個ならカウントを+1
        ans += 1

# 全部試したので回答を出力
print(ans)

約数のリスト生成とかよく使うのは、どこかにまとめておくと、コピペで済むので楽だし速いし確実。
ので、自分用にまとめたものがこちらになります → [緑コーダーが競プロで良く使うコード集(作成中)]

3. AtCoder Beginner Contest 122 B - ATCoder

問題リンク

問題概要

文字列Sが入力。
SからA,C,G,Tのみで構成される文字列を連続して取り出した時に、一番長く作れる時の長さを求めろ。

回答

ABC122_B.py

S = list(input())

N = len(S)
ACGT = set(["A","C","G","T"])

ans = 0     # 最長のACGT文字列の長さ

# 全ての連続部分文字列を試してみる
for i in range(N):
    for j in range(i+1,N+1):
        # 連続部分文字列を取り出す
        T = S[i:j]  # ここでスライスで取り出しているので、jは ～N でなく ～N+1
        M = len(T)
        
        if M > ans:
            # 取り出した文字列長が最も長いACGT文字列を更新できる可能性があれば、
            # 当該文字列がAGCT文字列かを確認
            for k in range(M):
                if T[k] not in ACGT:
                    break
            else:
                # AGCT文字列だったので、最長ACGT文字列長を更新
                ans = M

print(ans)

全探索するときにforの範囲を間違えちゃうのあるあるパターン。要注意。

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

問題リンク

問題概要

整数N,Mと高さN、横Mな表に整数が入ってるAが入力。
列を2つ(T1,T2)を選んで、各行毎により良い値を取っていって、全行分で合計する。
この時、最大値はいくらになるか。

回答

ABC122_B.py

N,M = map(int, input().split())

edge = [["#" for _ in range(M+2)]]
center = [["#"] + [int(e) for e in input().split()] + ["#"] for i in range(N)]
A = edge + center + edge

ans = 0

for T1 in range(1,M+1):
    for T2 in range(T1+1,M+1):
        score = 0
        for k in range(1,N+1):
            score += max(A[k][T1],A[k][T2])
                
        ans = max(ans,score)
            
print(ans)

表形式の入力の時、indexが頭の中でごっちゃになるので、下駄を履かせてます。
他の形式の入力も含め、自分用にまとめたものがこちらになります → [緑コーダーが競プロで良く使うコード集(作成中)]

補足

ABCのB問くらいまでなら、全探索でも解ける。が、C問,D問だと全探索だとTLE(時間切れ)するパターンが多い。
ので、ABCのC問以上では問題文を見て「全探索でいけそう!」と思っても、冷静に計算量を確認すること。
ループの回数を考えて、～ $ 10^7 $ならOK, $ 10^8 $~だとNG。¹
全探索でNGな場合は下記のようなアルゴリズムを使うことが多い。

1. 蟻本に載ってるらしい。 https://cppx.hatenablog.com/entry/2017/08/06/104144 ↩