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

1. 目的

初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

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

2. 総括

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

3. 本編

005 - 009 全探索：工夫して通り数を減らす全列挙

005. AtCoder Beginner Contest 095 C - Half and Half

回答

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

回答

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 - 最古の遺跡

回答

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

回答

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 - 星座探し

回答

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. 星座を再現できたら、始点となった座標と目的となる星座の最初の座標の差分をとると、それが答え

です。