【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】

**目指せ水色コーダー！！！！！！**

ということで、 
[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)(@e869120さん)
>
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の`初中級者が解くべき過去問精選 100 問`
を**Python**で解いていきます！
@e869120さんに感謝！！！！！！

###関連記事リンク
**全探索：全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】](https://qiita.com/rudorufu1981/items/8ae8beeba7b047f2687c)
**全探索：工夫して通り数を減らす全列挙**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)
**全探索：ビット全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
**全探索：順列全探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】](https://qiita.com/rudorufu1981/items/71abd5320a636e9146cb)
**二分探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】](https://qiita.com/rudorufu1981/items/2683c3988b246c9cf9ce)
**深さ優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】](https://qiita.com/rudorufu1981/items/e39aa16d73615c7e589f)
**幅優先探索**
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】](https://qiita.com/rudorufu1981/items/4804987152ad22f3fcb4)
**動的計画法：ナップザック DP**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part8/22】
**動的計画法：区間 DP**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part9/22】
**動的計画法：bit DP**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part10/22】
**動的計画法：その他**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part11/22】
**最短経路問題：ダイクストラ法**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part12/22】
**最短経路問題：ワーシャルフロイド法**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part13/22】
**最小全域木問題**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part14/22】
**高速な素数判定法**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part15/22】
**高速なべき乗計算**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part16/22】
**逆元を使う問題**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part17/22】
**累積和**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part18/22】
**Union-Find**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part19/22】
**その他のテクニック**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part20/22】
**実装問題**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part21/22】
**数学的な問題**
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part22/22】


**(2020/05/07 追記)**
※補足
この100問解いてみたシリーズの(**Part6**)の記事から、入力を
`input()`→`sys.stdin.readline().rstrip()`
に変えています！
[【Python】競プロテンプレ【AtCoder】](https://qiita.com/rudorufu1981/items/c6bc5e4d72cfe1cb7f14)
テンプレ用の記事も作ったので、よかったら使ってください〜

#記念すべき「Part1」〜普通の全列挙編〜
以下の4問を解いていきます！

>
#####全探索：全列挙
1　ITP1_7_B - How Many Ways?　基本問題です。
2　AtCoder Beginner Contest 106 B - 105
3　AtCoder Beginner Contest 122 B - ATCoder
4　パ研杯2019 C - カラオケ　これが解ければ全探索に慣れたと思って良いです。


# [1　ITP1_7_B - How Many Ways?](https://onlinejudge.u-aizu.ac.jp/problems/ITP1_7_B)

↓過去記事でも類題として取り上げたことのある問題！
(この時は3重for文で解いた！)
[【Python】ABC133B(右上三角形問題)【AtCoder】](https://qiita.com/rudorufu1981/items/0d6d6e657864dc09ee47)

3重for文で全く問題ないのですが、
今回は気分的に2重for文にしてみた！

```python:test.py
def LI(): return list(map(int,input().split()))
while 1:
    n,x = LI()
    if n==x==0:
        break
    ans = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            k = x-i-j #ただし、kの条件は[1,n]
            if 1<=k<=n and i<j<k:
                ans += 1
    print(ans)
```
**(2020/05/01 追記)**
今ならこんな感じでコード書く。

```python:test.py
import itertools
def LI(): return list(map(int,input().split()))
while 1:
    n,x = LI()
    if n==x==0:
        break
    ans = 0
    for i,j,k in itertools.product(range(1,n+1),repeat=3):
        if i<j<k and i+j+k==x:
            ans += 1
    print(ans)
```
`itertools.product`を使えばネストが深くならない！
ので、3重for文でもわかりやすい。

**(2020/05/02 追記)**
`itertools.combinations`こっちの方がスマートでした！！！

```python:test.py
import itertools
def LI(): return list(map(int,input().split()))
while 1:
    n,x = LI()
    if n==x==0:
        break
    ans = 0
    for i,j,k in itertools.combinations(range(1,n+1),3):
        if i+j+k==x:
            ans += 1
    print(ans)
```

#[2　AtCoder Beginner Contest 106 B - 105](https://atcoder.jp/contests/abc106/tasks/abc106_b)
Difficulty:66
ほぼ脳死でいけた！
`range`の第3引数(デフォルトは1)を例えば「2」にすると、1個飛ばしになる！
`range(1,int(i**0.5)+1)`は素数判定や約数探すときに愛用してる！
`int()`は小数点以下切り捨て！

```python:test.py
def I(): return int(input())
N = I()
ans = 0
if N>=105:
    for i in range(105,N+1,2):
        count_yakusuu = 0
        for j in range(1,int(i**0.5)+1):
            if i%j==0:
                count_yakusuu += 2
        if count_yakusuu==8:
            ans += 1
print(ans)
```

~~**(2020/04/20 追記)**
ちなみに、AtCoderでは、
ABC162〜Python3のバージョンが`3.8`まで一気に上がったので、
今後のコンテストは、約数→`sympy.divisors()`で簡単ですねw
(余談：最大公約数→`math.gcd()`も使えるようになったし！やった〜)~~

**(2020/05/03 追記)**
`sympy`使えませんでした！
なんか勘違いしてたみたいです・・・ごめんなさい・・・
最大公約数→`math.gcd()`こっちは使えます！！！
参考コードは一応残しておきます・・・

参考コード

```python:test.py
import sympy
def I(): return int(input())
N = I()
ans = 0
if N>=105:
    for i in range(105,N+1,2):
        if len(sympy.divisors(i))==8:
            ans += 1
print(ans)
```

#[3　AtCoder Beginner Contest 122 B - ATCoder](https://atcoder.jp/contests/abc122/tasks/abc122_b)
Difficulty:85
2通りの解法を思いついた！
1個はいつもの貪欲法。もう1個はDP。

解1(貪欲法)
考えられる答え候補をすべて求めて、`ans`を上書きしていく！

```python:test.py
S = input()
ans,temp = 0,0
for x in S:
    if x in 'ACGT':
        temp += 1
    else:
        temp = 0
    ans = max(ans,temp)
print(ans)
```

解2(DP)
`enumerate`の第2引数(デフォルトは0)をつけると、
インデックスがその数字からスタート！

```python:test.py
S = input()
dp = [0]*(len(S)+1) #1_indexed
for i,x in enumerate(S,1):
    if x in 'ACGT':
        dp[i] = dp[i-1]+1
print(max(dp))
```

**(2020/05/26 追記)**
解3(部分文字列の全探索)
重複組み合わせ`itertools.combinations_with_replacement`を使って、
部分文字列の全探索ができる！！！
すごい！！！

```python:test.py
import itertools
S = input()
ans = 0
for i,j in itertools.combinations_with_replacement(range(len(S)),2):
    if all([x in 'ACGT' for x in S[i:j+1]]):
        ans = max(ans,j+1-i)
print(ans)
```


#[4　パ研杯2019 C - カラオケ](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c)

いやー難しかった！
1問目の[右上三角形問題](https://qiita.com/rudorufu1981/items/0d6d6e657864dc09ee47)と3問目を組み合わせたような問題。
でも、次からはすらすらとコードが書けるようになった気がする！

```python:test.py
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
ans = 0
for i in range(M):
    for j in range(i+1,M):
        temp = 0
        for k in range(N):
            temp += max(A[k][i],A[k][j])
        ans = max(ans,temp)
print(ans)
```

＜別解＞
上のコードには劣る。一番はじめにACを獲得したコード。
`for x in A`から始めてしまうと、複雑なコードになってしまう。。。
一時退避用の2次元配列を用意して・・・
行列を入れ替えて足し算・・・
その最大値！

```python:test.py
def LI(): return list(map(int,input().split()))
N,M = LI()
A = [LI() for _ in range(N)]
temp = [[0]*(M*(M-1)//2) for _ in range(N)]
for i,x in enumerate(A):
    l = 0
    for j in range(M):
        for k in range(j+1,M):
            l += 1
            temp[i][l-1] = max(x[j],x[k])
print(max([sum(x) for x in (zip(*temp))]))
```
**(2020/05/01 追記)**
`Numpyマスター(仮)`になった！
ので、今ならこんな感じでコード書く。

```python:test.py
import itertools,numpy as np
def LI(): return list(map(int,input().split()))
N,M = LI()
a = np.array([LI() for _ in range(N)])
ans = 0
for i,j in itertools.product(range(M),repeat=2):
    if i<j:
        ans = max(ans,a[:,[i,j]].max(axis=1).sum())
print(ans)

```
Numpyになれるとこちらのコードの方が読みやすかったりする。
**`np.max().sum()`と後ろに付け足しながらかけるのが面白い！！！**
2次元配列以上になると、Numpyの本領が発揮される！かも！


次回は、以下の5問を解いていきます！
>
#####全探索：工夫して通り数を減らす全列挙
5　AtCoder Beginner Contest 095 C - Half and Half
6　三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
7　JOI 2007 本選 3 - 最古の遺跡　面白いです。Python3 だと想定解法が TLE する可能性があります。（PyPy3 であれば間に合う場合が多いです）
8　Square869120Contest #6 B - AtCoder Markets　全探索すると無数に通り数があるように見えますが、ひとつ工夫すると現実的な通り数で全列挙できる問題です。
9　JOI 2008 予選 4 - 星座探し


Part1/22
おわり！

[次(Part2/22)へ](https://qiita.com/rudorufu1981/items/282e06a6898f021b5e7f)