初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #1 ( 全列挙編 )

今日から "初中級者が解くべき過去問精選 100 問"
を全て解ききってみたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て時終わったら書いていきたいと思います。

今日はその第１回目！！

全探索：全列挙

この全探索の分野は全部で４問あるので、全て紹介したいと思います！

1. How many ways?

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

Nの制約が小さい時に全探索の発想を常にするようにしたいです。
(100とか1000くらいの時)

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

2. B - 105

https://atcoder.jp/contests/abc106/tasks/abc106_b

数学的にも素因数分解して個数から判別できますが、
全探索の方が圧倒的に早いので全探索！！
解法は約数列挙して、個数が8個ならカウントする感じです。

n = int(input())
cnt = 0
for i in range(1,n+1,2):
    ans = []
    for j in range(1,int(i**0.5) + 1):
        if i%j == 0:
            ans.append(j)
            if j**2 != i:
                ans.append(i//j)
    if len(ans) == 8:
        ans.sort()
        cnt += 1
print(cnt)

3. B - ATCoder

https://atcoder.jp/contests/abc122/tasks/abc122_b

高々文字列の長さが10なので困ったら全探索！！

s = input()
ans = cnt = 0
ch = ["A","G","C","T"]
for i in range(len(s)):
    if s[i] in ch:
        cnt += 1
    else:
        cnt = 0
    ans = max(ans,cnt)
print(ans)

4. C - カラオケ

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c

これは少し苦戦しました、、、
今までの３問とは違って３重for文で回さなければいけないのでしばらく考えました。
１重目は１曲目に歌う曲を決め、
２重目は２曲目に歌う曲を決め、
３重目は決まった曲をN人の生徒が歌ったらどうなるのかを調べていきます。
骨のある問題でしたが、面白かったです！！

n,m = map(int,input().split())
a = [[] for _ in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
ans = 0
score = [0]*n
for i in range(m-1):
    for j in range(i+1,m):
        for k in range(n):
            score[k] = max(a[k][i], a[k][j])
        ans = max(ans, sum(score))
print(ans)

最後に

まだまだスタートラインですが、なるべくハイペースで解いて進めていきたいです！！