Atcoder 100問解く【中級者になるために】#2 全探索

<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<script type="text/x-mathjax-config">
 MathJax.Hub.Config({
 tex2jax: {
 inlineMath: [['$', '$'] ],
 displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
 }
 });
</script>

# 全探索：全列挙
## [ABC106B](https://atcoder.jp/contests/abc106/tasks/abc106_b)
```py:python
N = int(input())
res = 0
for i in range(1,N+1):
    if i % 2 == 1:
        cnt = 0
        for j in range(1,i+1):
            if i % j ==0:
                cnt += 1
                
        if cnt ==8:
            res += 1
            
print(res)

```

## [ABC122B](https://atcoder.jp/contests/abc122/tasks/abc122_b)
```py:python
S = input()
res = 0
num = 0
ls = ['A','C','G','T']
for s in S:
    if s in ls:
       num += 1
    elif res < num:
        res = num
        num = 0
    
if res < num:
    res = num
    
print(res)
```

## [パ研杯2019C](https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_c)
*points*にそれぞれの曲の組み合わせに対する、各個人の最高得点を代入。
その和を比較する。
```py:python
import itertools
N,M = map(int,input().split())
H = int(M*(M-1)/2)
point_list = [list(map(int,input().split())) for _ in range(N)]
#print(point_list)
points = [[0 for _ in range(N)] for _ in range(H)]
#print(H)
#print(points)

alls = list(itertools.combinations(range(M), 2))
max_sum = 0
for i in range(len(alls)):
    for j in range(N):
        #print(i,j)
        points[i][j] = max(point_list[j][alls[i][0]],point_list[j][alls[i][1]]) 
    sum_list = sum(points[i])
    if max_sum < sum_list:
        max_sum = sum_list
#print(points)
print(max_sum)
```
# 全探索：工夫して通り数を減らす全列挙
## [ABC095C](https://atcoder.jp/contests/abc095/tasks/arc096_a)
```py:python
A,B,C,X,Y = map(int,input().split())
min_piza = min(X,Y)
max_piza = max(X,Y)
soneki = A-C +B-C

if soneki > 0:#toku
    sep =max((X-min_piza)*A,(Y-min_piza)*B)
    setp = (max_piza-min_piza)*C*2
    print(2*C*min_piza + min(sep,setp))
else:#son
    print(A*X + B*Y)
```

## [三井住友信用銀行2019D](https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d)
3桁を指定するのは$O(N^3)$かかる。
一方、答えの組み合わせに注目してみると、$10^3$通りの計算で済む。：**貪欲法**
```py:python
import itertools
N = int(input())
S = input()
count = 0
for i in range (10):
    if str(i) in S:
        p1 = S.index(str(i))
        
        for j in range(10):
            if str(j) in S[p1+1:]:
                p2 = S[p1+1:].index(str(j))
                
                for k in range(10):
                    if str(k) in S[p1+p2+2:]:
                        p3 = S[p1+p2+2:].index(str(k))
                        count += 1                
                    else:
                        continue
            else:
                continue
    else:
        continue
    
print(count)
```

## [JOI2007本選3](https://atcoder.jp/contests/joi2007ho/tasks/joi2007ho_c)
```py:python

```

## [Square869120Contest #6B](https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b)
距離が最も近くなるスタートとゴールは、必ず品物のある位置である。
アイテムの個数でfor文を回しても十分時間内に収まる。$O(10^3)$
```py:python
import math
N = int(input())
#dist = [[0 for _ in range(30)] for _ in range(30)]
ABs = [list(map(int,input().split())) for _ in range(N)]
#print(ABs)
min_dist = math.inf
for i in range(N):#start and end
    start =ABs[i][0]
    for j in range(N):#start and end
        end = ABs[j][1]
        #print(start,end)
        distance = 0
        for k in range(N):#zentansaku
            distance += abs(ABs[k][0]-start) + abs(ABs[k][0]-ABs[k][1]) + abs(ABs[k][1]-end)
            #print(start,ABs[k][0],ABs[k][1],end,distance)
        if min_dist > distance:
            min_dist = distance
            
print(min_dist)   
```

## [JOI2008予選4](https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d)
探すべき星座の中の任意の1点を選んで特別扱いし，この点が写真の中の n 個の星の一つに一致するように平行移動する。
```py:python
input_star = int(input())
inputs = []
for _ in range(input_star):
    input_x,input_y = map(int,input().split())
    inputs.append((input_x,input_y))
inputs.sort()
#print(inputs)  

output_star = int(input())
outputs = []
for _ in range(output_star):
    output_x,output_y = map(int,input().split())
    outputs.append((output_x,output_y))
outputs.sort()
#print(outputs)

cx = 0
cy = 0
cinputs = inputs.copy()
for oup in outputs:
    for inp in inputs:
        #print(inp,oup)
        cx = oup[0]-inp[0]
        cy = oup[1]-inp[1]
        for i in range(len(cinputs)):
            newx = inputs[i][0]+cx
            newy = inputs[i][1]+cy
            cinputs[i] =(newx,newy)
        if all(element in outputs for element in cinputs):
            print(cx,cy)
            exit()
        
```