過去問精選100 問 全探索：全列挙編【Python解答例】

こちらの記事で紹介されている初中級者が解くべき過去問精選100 問をPythonで練習していきます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

分野別に分けてくれていましたので今回は全探索：全列挙を解いてみます。

ITP1_7_B - How Many Ways?

ITP1_7_B - How Many Ways?

問題文

組み合わせの数
1 から n までの数の中から、重複無しで３つの数を選びそれらの合計が x となる組み合わせの数を求めるプログラムを作成して下さい。
例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、
1 + 3 + 5 = 9
2 + 3 + 4 = 9
の２通りがあります。

制約

・3 ≤ n ≤ 100
・0 ≤ x ≤ 300

解答例

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

解説

1からnまでの数のうち重複しない3つの数字を選び合計がxとなる数を求めます。
3つの数をそれぞれi, j, kとして3重ループによって組み合わせをすべて試していきます。
xと一致すればans変数を1増加させ、ループを抜けた後にansを出力すればACでした。
AtCoderと入力など違いがあり新鮮でした。

ABC106 B - 105

B - 105

問題文

105という数は, 非常に特殊な性質を持つ - 奇数なのに, 約数が8個もある.さて,1以上N以下の奇数のうち, 正の約数をちょうど8個持つようなものの個数を求めよ.

制約

・Nは1以上200以下の整数

解答例

n = int(input().strip())

count = 0
for i in range(n):
    a = i + 1 # （※1）
    b = 0
    if a % 2 != 0: # (※2)
        for j in range(a): # (※3)
            if a % (j+1) == 0:
                b += 1
        if b == 8:
                count += 1
print(count)

解説

入力から与えられるNまでの奇数のうち、約数が8個の数字の個数を求めます。
まず※1のように1～nまでの数字をaにfor文で代入していきます。
bは約数の個数をカウントする変数です（わかりにくい変数名ですね…反省）
※2ではaが奇数か判定しています。奇数ならつぎの約数のカウントを行うループに移行します。
※3のループはaをjで割って、値が0ならjは約数ですので約数カウント変数のbを増加させます。
このループを抜けた後にbが8ならば求めたい数ですので、答えとなるcount変数を1増加させます。
すべてのループを抜けた後にcount変数出力してACでした。

ABC122 B - ATCoder

B - ATCoder

問題文

英大文字からなる文字列Sが与えられます。Sの部分文字列 (注記を参照) であるような最も長い ACGT 文字列 の長さを求めてください。
ここで、ACGT文字列とは A, C, G, T 以外の文字を含まない文字列です。

注記

文字列Tの部分文字列とは、Tの先頭と末尾から0文字以上を取り去って得られる文字列です。
例えば、ATCODER の部分文字列には TCO, AT, CODER, ATCODER, (空文字列) が含まれ、AC は含まれません。

制約

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

解答例

s = input().strip()

count = 0 # (※1)
count_max = 0

for i in range(len(s)): # (※2)
    if s[i] == "A" or s[i] == "C" or s[i] == "G" or s[i] == "T":
        count += 1
        if count_max < count:
            count_max = count
    else:
        count = 0

print(count_max)

解説

入力から文字列Sが与えられ、AかCかGかTが何連続で続くかを求めます。
※1のcount変数はACGTの連続回数で、ACGTが出なければ0になります。
count_max変数が解答です。
※2のfor文では与えられたSの1文字目から順にACGT文字列か判定し、ACGT文字列なら連続回数を1増加させます。
このときcount変数がcount_max変数より大きくなれば、その値を代入することで最大の連続回数が求まります。
ACGT文字列でなければ、count変数を0として再スタートにしました。
ループを抜けた後にcount_maxを出力すれば、求めたい答えが出力されます。

パ研合宿2019　第3日「パ研杯2019」C - カラオケ

C - カラオケ

問題文

1,2,...,Nと番号づけられている N人の生徒から成るグループが，「全国統一カラオケコンテスト」に出場することとなりました．
このコンテストで歌える曲は，曲1，曲2，...，曲MのM曲あります．また，番号iの生徒が曲jを歌うと，必ずAi,j点を取ります．
さて，コンテストのルールは，以下のようになります．
M曲の中から2つの曲を選ぶ．（それぞれT1とT2とする．）それぞれの生徒が，曲T1と曲T2の両方を歌う．各生徒の得点は，その生徒が歌った2つの曲の点数のうち高い方となる．グループの得点は，生徒1,2,...,Nの得点の合計となる．
そのとき，グループの得点として考えられる最大の値を求めてください．

制約

・1≤N≤100
・2≤M≤100
・0≤Ai,j≤100,000,000
・入力はすべて整数

解答例

n, m = map(int,input().strip().split())

a = []
for i in range(n):
    array = list(map(int, input().strip().split()))
    a.append(array)

def chmax(a,b): # (※1)
    if a > b:
        return a
    else:
        return b

ans = 0

for t1 in range(m-1): # (※2)
    for t2 in range(t1+1,m):
        sum_score = 0
        for i in range(n): # (※3)
            score = chmax(a[i][t1],a[i][t2])
            sum_score += score
        if ans < sum_score:
            ans = sum_score

print(ans)

解説

生徒がM曲あるなかから2曲歌い、2曲のうち高い点数をグループ得点に足していきます。N人目の生徒が終わったときに最も高いグループ得点を求める問題です。
選ばれる2曲をt1とt2で表し、全組み合わせにおけるグループ得点を計算していきます。
※1ではaとbという引数を渡すと大きい方を返す関数を定義しました。この問題では同じ処理は1回だけなので効果は少ないですが、動的計画法でよく出てきたので使ってみました。
※2では曲t1とt2の全ての組み合わせにおけるすべての生徒の点数を求めています。曲t1とt2のときのグループ得点をsum_scoreとし解答であるansより大きければansに代入しています（ここでもchmaxを使おうと思えば使えましたね…）
三重ループを抜ければすべての組み合わせにおける最高グループ得点がansに代入されていますので、それを出力してACでした。

人間では時間がかかる処理でも、非常に早く正確に行えるのはプログラムの魅力ですね。
次回は次の分野になりますが解いていきたいと思います。

初中級者が解くべき過去問精選100 問の記事をまとめたページはこちら
ebisuke33.hatenablog.com

蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com