Pythonで解く【初中級者が解くべき過去問精選 100 問】(001 - 004 全探索：全列挙)

# 1. 目的
[初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa)をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「001 - 004 全探索：全列挙」になります。
# 2. 総括
Pythonでは組み合わせの列挙等は```itertools```でも行えるが、練習のためfor文で書いた。
特につまずくことはなかった。


# 3. 本編
## 001 - 004 全探索：全列挙
### 001. [ITP1_7_B - How Many Ways?](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/15b26294-110c-a81a-d883-7d499caa6fb8.png)
#### 回答
```python
answer_list = []
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break

    count = 0
    for first in range(1, n + 1):
        for second in range(first + 1, n + 1):
            for third in range(second + 1, n + 1):
                if first + second + third == x:
                    count += 1

    answer_list.append(count)

for answer in answer_list:
    print(answer)

```

問題文は重複無しとあるので、for文の```first```、```second```、```third```の範囲が重複しないように気を付けます。
具体的には```second```のスタートを```first+1```、```third```のスタートを```second+1```にします。

---

### 002. [AtCoder Beginner Contest 106 B - 105](https://atcoder.jp/contests/abc106/tasks/abc106_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/5c1483ae-0e45-6e49-361b-5673b44bdf2a.png)

#### 回答
```python
def is_target(num):
    count = 0
    for i in range(1, num+1):
        if num % i == 0:
            count += 1
    if count == 8:
        return True
    else:
        return False

if __name__ == "__main__":
    N = int(input())
    count = 0
    for num in range(1, N+1, 2):
        count += is_target(num)

    print(count)

```

約数が8であるか否かを```True```、```False```で返す```is_target```という関数を作成します。
そのあと1~Nまでの奇数について```is_target```でチェックして足し合わせます（Trueは1なのでそのまま足せる）。

---

### 003. [AtCoder Beginner Contest 122 B - ATCoder](https://atcoder.jp/contests/abc122/tasks/abc122_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/83d5c3f0-4622-0c0e-df97-9da33de724ad.png)

#### 回答
```python
target = 'ACGT'
S = input()

answer = 0
for start in range(len(S)):
    if S[start] not in target:
        continue
    count = 0
    for end in range(start, len(S)):
        if S[end] not in target:
            break
        count += 1
    
    answer = max(answer, count)

print(answer)

```

文字列Sから取り出す部分文字列は添え字```start```と```end```を使って```S[start : end]```と書けますので、```start```と```end```それぞれについて、```ACGT```であるか否かをチェックしていきます。

チェックの際は、```start```のfor文では```ACGT```じゃない場合は```continue```、```end```のfor文では```ACGT```じゃない場合は```break```であることに注意します。

---

### 004. [パ研杯2019 C - カラオケ](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/4a355cd9-e570-ab74-b57b-f1fd858470d1.png)

#### 回答
```python
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

answer = 0
for song1 in range(M):
    for song2 in range(song1+1, M):
        score = 0
        for i in range(N):
            score += max(A[i][song1], A[i][song2])

        answer = max(answer, score)

print(answer)

```

```song1``` と```song2```についてfor文を回します。
そしてその内側で各生徒(添え字```i```)について```song1```と```song2```の大きいほうの点数を採用します。