Atcoder水色への精選 100 問 全探索 : 工夫して通り数を減らす全列挙(Python)
引き続き水色になるための精選100問を解いていきます
今回は5~9までの「全探索 : 工夫して通り数を減らす全列挙」です
前回↓
全列挙
algo-archit.hatenablog.com
目次
- 5 AtCoder Beginner Contest 095 C - Half and Half
- 6 三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN
- 7 JOI 2007 本選 3 - 最古の遺跡
- 8 Square869120Contest #6 B - AtCoder Markets
- 9 JOI 2008 予選 4 - 星座探し
5 AtCoder Beginner Contest 095 C - Half and Half
問題文
atcoder.jp
ABピザを2枚で1セットC×2円で考えると
ABピザを何セット分買うかを全探索することで残りのA,Bピザを何枚買うかを求めることができます
pythonでの実装例
a,b,c,x,y = map(int,input().split()) ans = 10**10 # ABピザ2枚セットを何枚分買うか 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)
そこで少し工夫をして、暗証番号を1桁づつ見ていき、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
柱を2点選び、残りの2点を正方形の形になるように座標を求めた際に、その位置に柱が存在するかを確認できれば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 # 残りの2点の座標が柱として存在するかを検索 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個の星を星座の中の1地点と一致させるときのずれを記録し、残りの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