競プロの扉を開ける！Pythonでの全探索入門

競技プログラミングにおいて、全探索という考え方はとても重要です。

問題を解決するために全探索は、非常にシンプルでパワフルな手法になります。

この記事では、全探索について基本的な考え方から、実装方法まで詳しく解説します。

Python が初めての方でもわかるようにわかりやすく説明しています。

全探索とは

全探索は、競技プログラミングにおいて重要な手法の一つです。

与えられた問題の解を求めるために、可能なすべての組み合わせやパターンを試す方法です。

たとえば、3桁のダイヤル式の南京錠は、000 から 999 までのすべての番号を試せば、時間はかかりますが開けることができます。

このように、あり得るパターンをすべて試すのが全探索です。

すべての列挙

全探索の基本は、問題の答えの候補をすべて試すことです。

そのために重要なのが、繰り返し処理です。

Python での繰り返しは for を使います。

for 変数 in オブジェクト:
    処理

次のコードを実行すると0から9までの数字が表示されます。

range(10) で 0 から 9 まで繰り返しています。print()は、出力です。

for i in range(10):
    print(i)

"""実行結果
0
1
2
3
4
5
6
7
8
9
"""

【Python】printの使い方

range() は、start から初めて、step ずつ、stop になるまで繰り返します。

stop の値は、含まれないことに注意してください。

range(start, stop[, step])

range(10) のように、渡される引数が1つだけのときは、start は 0、step は 1 になります。

for i in range(1, 5):
    print(i)

"""実行結果
1
2
3
4
"""

for i in range(2, 8, 3):
    print(i)

"""実行結果
2
5
"""

九九を表示する

繰り返しができるようになったので、九九の表をプログラムで表示させてみます。

for を２つ使って九九を表示させています。

print() は、出力の最後が改行コードになります。そのため、改行させたくないときは end を使います。

end = ‘ ‘ で出力の最後をスペースにしています。

for i in range(1, 10):
    for j in range(1, 10):
        print(i * j, end=' ')

    # 1つの段が終わったので改行する
    print()


"""実行結果
1 2 3 4 5 6 7 8 9 
2 4 6 8 10 12 14 16 18 
3 6 9 12 15 18 21 24 27 
4 8 12 16 20 24 28 32 36 
5 10 15 20 25 30 35 40 45 
6 12 18 24 30 36 42 48 54 
7 14 21 28 35 42 49 56 63 
8 16 24 32 40 48 56 64 72 
9 18 27 36 45 54 63 72 81 
"""

問題を解く

AtCoder の問題を解いてみます。

ここでは、次の記事で紹介されている全探索の問題から何問かピックアップして解説します。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 – Qiita

AtCoder Beginner Contest 144 B – 81

ABC144 B – 81 を全探索を使って解いてみます。

問題概要

整数 N が与えられるので、N を 1 以上 9 以下の２つの整数の積として表すことができるか判定し、できるなら Yes を、できないなら No を出力してください。

制約

1 ≤ N ≤ 100

N は整数である。

考え方

九九の計算した結果を１つずつ順番に計算して、その計算結果と N が同じか判定します。

次が解答コードです。入力は、input() で受け取り、int() を使って整数に変換しています。

答えを表す answer 変数に出力する文字列を格納しています。全探索をして、一致した整数があったときは、answer に Yes を代入しています。

# 入力の受け取り
N = int(input())

# 答えを表す変数
answer = 'No'

# 全探索
for i in range(1, 10):
    for j in range(1, 10):
        # N が i と j の積と等しいか 
        if N == i*j:
            answer = 'Yes'

# 答えの出力
print(answer)

AtCoder Beginner Contest 150 B – Count ABC

ABC150 B – Count ABC です。

問題概要

英大文字のみからなる長さ N の文字列 S があります。

S の連続する部分列として ABC がいくつ含まれるかを求めてください。

制約

3 ≤ N ≤ 50

S は英大文字のみからなる。

考え方

入力例１だと S は ZABCDBABCQ なので、これを例に解説します。

いきなり ABC を検索するのは難しいので、まずは、A の個数を考えてみます。

文字列から1文字ずつ A かどうかを判定します。

N = 10
S = 'ZABCDBABCQ'

# 答えを表す変数
answer = 0

# 全探索
for i in range(N):
    # A と等しいか 
    if S[i] == 'A':
        answer += 1

# 答えの出力
print(answer)	# => 2

S[i] で、文字列の要素にアクセスできます。たとえば、S[0] は Z です。

１文字目の添え字は 0 になることに注意してください。

A と等しいときは、個数を数えるための変数 answer に１足しています。

answer += 1 は、answer = answer + 1 と同じです。

次に AB の個数を数えてみます。

1文字ずつ A か判定して、その次の文字が B かを判定します。

N = 10
S = 'ZABCDBABCQ'

# 答えを表す変数
answer = 0

# 全探索
for i in range(N-1):
    # AB と等しいか 
    if S[i] == 'A' and S[i+1] == 'B':
        answer += 1

# 答えの出力
print(answer)	# => 2

先ほどは range(N) で最後の文字まで確認していましたが、今回は最後まで確認する必要はないので1文字前の range(N-1) にしています。

同じように ABC を確認するには次のようなコードになり、AC できます。

# 入力の受け取り
N = int(input())
S = input()

# 答えを表す変数
answer = 0

# 全探索
for i in range(N-2):
    # ABC と等しいか 
    if S[i] == 'A' and S[i+1] == 'B' and S[i+2] == 'C':
        answer += 1

# 答えの出力
print(answer)

ちなみに、スライスを使えば文字列の一部を簡単に取得できます。

次のコードは、スライスを使った解法です。S[i:i+3] で i文字目から3文字取得しています。

# 入力の受け取り
N = int(input())
S = input()

# 答えを表す変数
answer = 0

# 全探索
for i in range(N-1):
    # ABC と等しいか 
    if S[i:i+3] == 'ABC':
        answer += 1

# 答えの出力
print(answer)

【Python】文字列の使い方 – スライス

AtCoder Beginner Contest 122 B – ATCoder

ABC122 B – ATCoder です。

問題概要

英大文字からなる文字列 S が与えられます。
S の部分文字列であるような最も長い ACGT 文字列の長さを求めてください。

ここで、ACGT 文字列とは A, C, G, T 以外の文字を含まない文字列です。

制約

S は長さ 1 以上 10 以下の文字列である。
S の各文字は英大文字である。

考え方

1 文字ずつ探索していきます。

文字列を１文字ずつ確認するには、今までどおり、range() を使ってもいいですが、Pythonでは次のようにも書けます。

len(S) は、文字列 S の長さを取得しています。

S = 'ATCODER'

# range() を使う方法
for i in range(len(S)):
    print(S[i])

# 文字列を直接使う方法
for c in S:
    print(c)

"""どちらも実行結果は次のようになる
A
T
C
O
D
E
R
"""

次に、ACGT のいずれかの文字と等しいか判定する必要があります。

in を使えば、文字列の中に部分文字列が存在するか確認できます。

S = 'ATCODER'

# 全探索
for c in S:
    # ACGT のいずれかの文字のとき
    if c in 'ACGT':
        print(c)

"""実行結果
A
T
C
"""

あとは、ACGT が連続したときの個数をカウントします。

「答えの変数」と「部分文字列をカウントする変数」の２つでカウントしています。

max() は、最大の引数を返します。

# 入力の受け取り
S = input()

# 答えを表す変数
answer = 0

# 部分文字列の個数
count = 0 

# 全探索
for c in S:
    # ACGT のいずれかの文字のとき
    if c in 'ACGT':
        count += 1
        answer = max(answer, count)
    else:
        count = 0
        
# 答えの出力
print(answer)

AtCoder Beginner Contest 136 B – Uneven Numbers

ABC136 B – Uneven Numbers です。

問題概要

整数 N が与えられます。N 以下の正の整数のうち、(先頭に 0 をつけずに十進法で表記したときの) 桁数が奇数であるようなものの個数を求めてください。

制約

1 ≤ N ≤ 10⁵

考え方

制約が 10⁵ なので全探索しても間に合います。

１から N までを全探索するので、range(1, N+1) となります。Nまで探索する必要があるので、N＋1なことに注意してください。

桁数が奇数かどうかを判定するために、整数を文字列に変換して len() で文字数を取得します。

奇数は２で割り切れないので、２で割った余りが０以外だと奇数です。

N = int(input())

# 答えを表す変数
answer = 0

# 全探索
for i in range(1, N+1):
    # 桁数が奇数か判定
    if len(str(i)) % 2 != 0:
        answer += 1
        
# 答えの出力
print(answer)

【Python】型と演算子

まとめ

競技プログラミングにおいて、全探索はとっても大事なテクニックの１つです。

全探索は、問題の答えの候補をすべて試すことです。

Python での繰り返し処理は for を使います。

for 変数 in オブジェクト:
    処理

たとえば、0 から 9 まで繰り返すには次のように書きます。

for i in range(10):
    print(i)

len() を使えば、文字列の長さを取得できます。

max() を使えば、最大の引数を取得できます。

競技プログラミングの実力アップにオススメの書籍です。

リンク