Atcoder水色への精選 100 問　全探索 : 工夫して通り数を減らす全列挙(Python)

AtCoder Python 競プロ精進 全探索 全列挙 精選100問

引き続き水色になるための精選100問を解いていきます
今回は5~9までの「全探索 : 工夫して通り数を減らす全列挙」です

qiita.com

前回↓
全列挙
algo-archit.hatenablog.com


目次



5　AtCoder Beginner Contest 095 C - Half and Half

問題文
atcoder.jp

ABピザを２枚で１セットC×2円で考えると
ABピザを何セット分買うかを全探索することで残りのA,Bピザを何枚買うかを求めることができます

pythonでの実装例

a,b,c,x,y = map(int,input().split())
ans = 10**10

# ABピザ２枚セットを何枚分買うか
for i in range(max(x,y)+1):
    point = 2*c*i
    # 足りない分は買い増し
    if i < x:
        point += a*(x-i)
    if i < y:
        point += b*(y-i)
    ans = min(ans,point)

print(ans)



6　三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN

問題文
atcoder.jp

暗証番号の個数はせいぜい000~999までの1000通りなので
これらの番号が文字列から生成することができるかを全列挙することで問題は解けます
しかしながら以下のようなコードをPythonで提出しようとしても間に合いません(PyPy3だと500msくらいで間に合う)

TLE例

n = int(input())
s = input()
point = 0

# 暗証番号を全探索する
for i in range(1000):
    t = str(i).zfill(3)
    now = 0
    # sで暗証番号が作れるかを検証
    for j in s:
        if j == t[now]:
            now += 1
        if now == 3:
            point += 1
            break

print(point)

そこで少し工夫をして、暗証番号を１桁づつ見ていき、Sから作ることができない数を除外してやると間に合わせることができます

pythonでの実装例

n = int(input())
s = input()
point = 0

# 100の位
for i in range(10):
    # Sのn-2番目までにiがあるか
    str_i = str(i)
    for a in range(n-2):
        if s[a] == str_i:
            now_i = a
            break
    # 作れなかった場合打ち切り
    else:
        continue
    # 10の位
    for j in range(10):
        str_j = str(j)
        for b in range(now_i+1,n-1):
            if s[b] == str_j:
                now_j = b
                break
        else:
            continue
        # 1の位
        for k in range(10):
            str_k = str(k)
            for c in range(now_j+1,n):
                # 暗証番号がそろった
                if s[c] == str_k:
                    point += 1
                    break

print(point)



7　JOI 2007 本選 3 - 最古の遺跡

問題文
https://www.ioi-jp.org/joi/2006/2007-ho-prob_and_sol/2007-ho.pdf#page=5

柱を２点選び、残りの２点を正方形の形になるように座標を求めた際に、その位置に柱が存在するかを確認できればOKです
注意書きがあった通りPythonで解こうとすると下手なコードではTLEを起こしてしまいます
itertoolsのcombinationやset型を用いることでなんとか間に合わせることができました

pythonでの実装例

from itertools import combinations

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

# 面積の最大値
max_s = 0

# 2点の組み合わせ
for (x1,y1),(x2,y2) in combinations(xy,2):
    dx = x1-x2
    dy = y1-y2
    # 残りの２点の座標が柱として存在するかを検索
    if (x2-dy,y2+dx) in set_xy and (x1-dy,y1+dx) in set_xy:
        # 存在した場合面積を更新する
        max_s = max(max_s,(x1-x2)**2+(y1-y2)**2)

print(max_s)



8　Square869120Contest #6 B - AtCoder Markets

問題文
atcoder.jp

与えられた地点の最小値から最大値までの範囲でスタートとゴールを全探索します

A A地点 -> B地点 -> ゴール
となるように移動するのが最短経路になります

中央値を使った求め方もできるようです
以下の解答リンク参照
https://img.atcoder.jp/s8pc-6/editorial.pdf

pythonでの実装例

n = int(input())
ab = [tuple(map(int,input().split())) for _ in range(n)]
set_ab = set()
ans = 10**20

for i,j in ab:
    set_ab.add(i)
    set_ab.add(j)

set_ab = list(set_ab)
S = len(set_ab)

# スタートとゴールの範囲を全探索する
for i in range(S-1):
    for j in range(i,S):
        point = 0
        for a,b in ab:
            point += abs(set_ab[i]-a) # start -> a
            point += abs(set_ab[j]-b) # b -> goal
            point += b-a # a -> b
        ans = min(ans,point)

print(ans)



9　JOI 2008 予選 4 - 星座探し

問題文
atcoder.jp

与えられたN個の星を星座の中の１地点と一致させるときのずれを記録し、残りのN-1個の星座+ずれ分の座標がM個の星の中にあるかを全探索します
M個の座標をハッシュテーブル(Pythonの辞書型)で管理することで計算量O(N*M)で解くことができます（この問題の制限時間ではあまり関係ありませんが）

pythonでの実装例

m = int(input())
star = [tuple(map(int,input().split())) for _ in range(m)]
star.sort()

n = int(input())
stars = [tuple(map(int,input().split())) for _ in range(n)]
stars.sort()

# ハッシュテーブルで管理
dic = {}
for i,j in stars:
    dic[i,j] = True

for i,j in stars:
    # 星座の一つめの星とのずれを記録
    x_gap = i-star[0][0]
    y_gap = j-star[0][1]
    for k,l in star:
        if (k+x_gap,l+y_gap) not in dic:
            break
    # breakが発生しなかった場合
    else:
        print(x_gap,y_gap)
        exit()

次回↓
bit全探索
algo-archit.hatenablog.com