Pythonで解く【初中級者が解くべき過去問精選 100 問】(005 - 009 全探索：工夫して通り数を減らす全列挙)

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

本記事は「005 - 009 全探索：工夫して通り数を減らす全列挙」です。

# 2. 総括
【006.三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN】がやや難しかったです。
007と009はベクトルができなければ難しいかもしれません。


# 3. 本編
## 005 - 009 全探索：工夫して通り数を減らす全列挙
### 005. [AtCoder Beginner Contest 095 C - Half and Half](https://atcoder.jp/contests/abc095/tasks/arc096_a)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/2d78eda2-2847-d45a-6915-632b2d80bafb.png)

#### 回答
```python
A, B, C, X, Y = map(int, input().split())

answer_1 = A * X + B * Y # すべてA、Bで買う場合
answer_2 = C * 2 * max(X, Y) # すべてCで買う場合

# answer_3: 先にA,Bを買ってから残りをCで補う場合
# answer_4: 先にCを買ってから最後に残りA,Bで補う場合
if X > Y:
    answer_3 = A * Y + B * Y + C * (X - Y) * 2
    answer_4 = A * (X - Y) + C * Y * 2
else:
    answer_3 = A * X + B * X + C * (Y - X) * 2
    answer_4 = B * (Y - X) + C * X * 2

answer = min(answer_1, answer_2, answer_3, answer_4)
print(answer)

```

最も安い値段で買うためには、下記4通りを試せば十分です。
1. すべてA,Bで買う場合
2. すべてCで買う場合
3. 先にA,Bの少ない数量分まで買ってから、残りをCで補う場合
4. 先にCで少ない数量分まで買ってから、残りをA,Bで補う場合

この4通りの金額を算定した後に最小値を求めれば答えになります。


---

### 006. [三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN](https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/1c3f10cc-9b02-a386-2359-0b5fbbdd37fc.png)

#### 回答
```python
import itertools

def find_index(l, x): # 組み込み関数indexでは、見つからない場合エラーとなってしまうので-1を返すように修正
    if x in l:
        return l.index(x)
    else:
        return -1


if __name__ == "__main__":
        
    N = int(input())
    S = [int(c) for c in input()]
    table = list(range(10))

    count = 0
    for p in itertools.product(table, repeat=3): # 重複を許して1~9の数値を３つならべる
        target = list(p)

        s1_index = find_index(S, target[0])
        if s1_index == -1:
            continue
        s1 = S[s1_index+1:]

        s2_index = find_index(s1, target[1])
        if s2_index == -1:
            continue
        s2 = s1[s2_index+1:]
        
        s3_index = find_index(s2, target[2])
        if s3_index == -1:
            continue
        
        count += 1

    print(count)

```

この回答は上手くないです。

文字列Sを主体に探すとSの長さが最大30,000で、ここから３つを選ぶ方法を全通り試すと10**12くらいのオーダーとなり間に合いませんので違う方法を考えます。

文字列Sを主体ではなく0~9の数字を重複許して3つ選ぶ方法を考えれば10**3のオーダーになるので、こちらを主体で考えれば行けそうな気がしてきます。

方針は、
1. ```itertools.product```で0~9を使用した3桁の数字を列挙する
2. 左側の桁の数字が文字列Sに初めて現れるindex番号を調べる
3. 上記で見つけたindex番号以降の文字列Sで、真ん中の桁の数字が初めて現れるindex番号を調べる
4. 上記で見つけたindex番号以降の文字列Sで、右側の桁の数字が初めて現れるindex番号を調べる
5. 2~3のでindex番号が見つからなかった場合はそれぞれ```break```する

です。

---

### 007. [JOI 2007 本選 3 - 最古の遺跡](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/49586618-b81b-484e-fe16-fb8d2aa5b302.png)

#### 回答
```python

import itertools

n = int(input())
dots = [tuple(map(int, input().split())) for _ in range(n) ]
dots_set = set(dots)

# ABCDの正方形を考える
max_area = 0
for A, B in itertools.combinations(dots, 2):
    Ax, Ay = A
    Bx, By = B

    Cx, Cy = Bx - (By - Ay), By + (Bx - Ax) 
    Dx, Dy = Ax - (By - Ay), Ay + (Bx - Ax)
    
    if (Cx, Cy) in dots_set and (Dx, Dy) in dots_set:
        area = (Ax - Bx) ** 2 + (Ay - By) ** 2
        max_area = max(max_area, area)

print(max_area)

```
与えられた座標から2点が確定すれば、正方形作成のための4点と面積が確定します。したがって方針としては座標から2点選ぶ方法を全通り試して、正方形が作成できるか否かを判定していきます。
1. ```itertools```で座標から2点選ぶ方法を列挙（A, Bとする）
2. 2点から正方形を作成するときの残りの二つのあるべき点C, Dを求める
3. C, Dが与えられて座標の集合に含まれるか否かを判定
4. 含まれる場合は面積を求めて最大値を記録する

です。
点C、Dが与えられた座標の集合に含まれるか否かを判定する際に、普通にリスト```in dots```で判定すると```TLE```になるので、あらかじめ```dots_set = set(dots)```としておく必要があります。


---

### 008. [Square869120Contest #6 B - AtCoder Markets](https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/7c50fb9c-52b0-7e51-23ad-d69f086954fd.png)

#### 回答
```python
N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

min_time = float('inf')
for a in A:
    for b in B:
        total_time = 0
        for i in range(N):
            total_time += abs(a - A[i]) + abs(A[i] - B[i]) + abs(b - B[i])
        
        min_time = min(min_time, total_time)

print(min_time)

```
入口と出口は与えられたAi, Biのいずれかに置くことが最適とおもわれます（たぶんほかにも最適な場所が存在すると思われる・・・）。
したがってAとBすべてについて試して最小の時間となるものを探します。

---

### 009. [JOI 2008 予選 4 - 星座探し](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/ef24674c-fb78-b438-1eaf-fce16300636f.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e322f1f2-ce9e-22be-0cfc-80bb2257310d.png)



#### 回答
```python
m = int(input()) # mは探す星座の星の数
target = [tuple(map(int, input().split())) for _ in range(m)] # 見つけたい星座の座標
n = int(input()) # nは写真に写っている星の数
stars = [tuple(map(int, input().split())) for _ in range(n)] # 写真上の星の座標
set_stars = set(stars)

target_vector = [] # 相対位置をベクトルとして保持
for i in range(m-1):
    y1, x1 = target[i]
    y2, x2 = target[i+1]
    vector_y, vector_x = y2 - y1, x2 - x1
    target_vector.append((vector_y, vector_x))

# すべての星についてベクトルを足す。
target_y, target_x = 0, 0 
for star in stars:
    y, x = star
    new_y, new_x = y, x
    count = 0
    for vector in target_vector:
        y_vector, x_vector = vector

        new_y += y_vector
        new_x += x_vector

        if (new_y, new_x) not in set_stars:
            break

        count += 1
        if count == m - 1: # すべてのベクトル加算後の星が存在した場合スタートの座標が答えのもと
            target_y, target_x = y, x 
            break
# ターゲットの最初の座標との相対座標が答え
answer_y = target_y - target[0][0]
answer_x = target_x - target[0][1]

print(answer_y, answer_x)

```
添え字のyとxを問題の設定と逆でやってしまいましたが答えはあってます。

方針は、
1. 目的となる星座の形をベクトル```target_vector```として保有(反時計回り)
2. 写真にあるすべての星でベクトル通り移動し、移動後の座標に星があるか否かをチェック
3. 星がなければ```break```、ある場合は使用したベクトルの回数を数えて```m-1```回使用できた場合は星座の再現完了
4. 星座を再現できたら、始点となった座標と目的となる星座の最初の座標の差分をとると、それが答え

です。