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

全探索：全列挙

ABC106B

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

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

pointsにそれぞれの曲の組み合わせに対する、各個人の最高得点を代入。
その和を比較する。

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

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

3桁を指定するのは$O(N^3)$かかる。
一方、答えの組み合わせに注目してみると、$10^3$通りの計算で済む。：貪欲法

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

python

Square869120Contest #6B

距離が最も近くなるスタートとゴールは、必ず品物のある位置である。
アイテムの個数でfor文を回しても十分時間内に収まる。$O(10^3)$

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

探すべき星座の中の任意の1点を選んで特別扱いし，この点が写真の中の n 個の星の一つに一致するように平行移動する。

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()