過去問精選100 問 全探索：工夫して通り数を減らす全列挙【Python解答例】
今回もこちらの記事で紹介されている初中級者が解くべき過去問精選100 問をPythonで練習していきます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita
この記事は全探索：工夫して通り数を減らす編です。
現時点で正直理解できない問題がありましたので、その問題は理解できたら追記していこうと思います。
ABC 095 C - Half and Half
問題文
ファーストフードチェーン「ピザアット」のメニューは「A ピザ」「B ピザ」「AB ピザ」の3種類です。A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ1枚あたりの値段はそれぞれA円、B円、C円です。
中橋くんは、今夜のパーティーのために A ピザX枚と B ピザY枚を用意する必要があります。これらのピザを入手する方法は、AピザやBピザを直接買うか、AB ピザ2枚を買って A ピザ1枚と B ピザ1枚に組み替える以外にはありません。このためには最小で何円が必要でしょうか？なお、ピザの組み替えにより、必要な量を超えたピザが発生しても構いません。
制約
・1≤A,B,C≤5000
・1≤X,Y≤10^5
・入力中のすべての値は整数である。
解答例
a, b, c ,x ,y = map(int, input().strip().split()) if x < y: # (※1) 必ずxが大きくなるように、Aピザの必要枚数xとBピザの必要枚数yを比較する。 a, b = b, a x, y = y, x piza_ab = a * x + b * y # (※2) piza_c = c * 2 * x # (※3) piza_cb = a * (x - y) + c * 2 * y # (※4) price = [piza_ab, piza_c, piza_cb] new_price= sorted(price) print(new_price[0])
解説
パーティーに必要なAピザx枚と、Bピザy枚の最も安く購入できる価格を調べる問題です。
後の計算を楽に行うため※1で必ずx>yとなるよう比較を行っています。
もし、xが小さい場合は枚数のxとyおよび価格のaとbを入れ替えています。
ピザの買い方は3種類考えられます。
1つ目の(※2)は、ピザAをx枚、ピザBをy枚買う方法です。
2つ目の(※3)は、2枚でピザAとピザB 1枚づつに組み替えられるABピザのみ購入する方法です。条件によってはピザBに余りがでますが、必要以上にピザが発生してもかまわないと問題文にありますので、この買い方も候補となります。
3つ目の(※4)は、ピザBのy枚はABピザを買うことでまかない、ピザAの残りの(x-y)枚はAピザを買うという方法です。※1でxが大きくなるよう比較していますので、(x-y)は必ず正となり、意図した結果がもたらされます。
この3つの方法で求めた3通りの価格をpriceリストに格納し、ソートすることで最小の価格を求めることができました。
三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN
問題文
AtCoder 社は、オフィスの入り口に3桁の暗証番号を設定することにしました。
AtCoder 社にはN桁のラッキーナンバーSがあります。社長の高橋君は、SからN−3桁を消して残りの3桁を左から読んだものを暗証番号として設定することにしました。
このとき、設定されうる暗証番号は何種類あるでしょうか？
ただし、ラッキーナンバーや暗証番号はいずれも0から始まっても良いものとします。
制約
・4≤N≤30000
・Sは半角数字からなる長さNの文字列
解答例
N = int(input().strip()) S = input() ans = 0 for i1 in range(10): # (※1) for i2 in range(10): for i3 in range(10): count = 0 # (※2) for j in range(N): if count == 0 and int(S[j]) == i1: count = 1 elif count == 1 and int(S[j]) == i2: count = 2 elif count == 2 and int(S[j]) == i3: ans += 1 break print(ans)
解説
N桁（4桁以上）の数字Sから、N-3桁を消し、残りの3桁を左から並べて暗証番号とするときに、何通りの暗証番号が考えられるかという問題です。
暗証番号は3桁なので候補を000～999の千通りに絞り込み、候補が実現可能か全探索していきました。
※1でi1,i2,i3の3重ループで000～999の候補を作ります。
※2のcount変数は候補に該当する数字がなければ0、左から一桁目がSに存在していたら1、左から2桁目がSに存在していたら2を代入しています。
Sの左から1桁目から探索し、i1と同じ数字があればcount変数を1にして、Sの次の桁からi2を探します。
その後i2がSにあれば、count変数を2にして、再度Sのその次の桁からi3を探します。
最終的にi3が見つかれば、そのi1,i2,i3の候補はSから作り出せるといえますので、解答となるans変数を1増加させて次の候補を検証しています。
この繰り返しで千通りの候補を試し、ans変数を出力すればACとなりました。
square869120Contest #6 B - AtCoder Market
問題文
AtCoder マーケットは、1,000,000,000個のマスが1列につながったマス目で表されるスーパーマーケットである。ここでは、左から
i番目のマスを「マス i」とする。
ある日、N人の買い物客が AtCoder マーケットに来る。i人目の買い物客は、マスAiにある品物とマスBiにある品物を買う。
square1001 君は、AtCoder マーケットに入口と出口を1つずつ設置することにした。入口と出口はいずれかのマス目に設置する。入口と出口は同じ場所にあってもよい。
そのとき、買い物客は次のような経路で移動する。
まず、入口からスタートする。マスAiとBiを経由して、出口でゴールする。すべての買い物客について、隣り合ったマス目に進むのに1秒かかるとき、最適に入口と出口を設置したときの「すべての買い物客の移動時間の合計」の最小値を求めなさい。
制約
・1≤N≤30
・1≤Ai
解答例
N = int(input().strip()) A = [] B = [] for i in range(N): a, b = map(int,input().split()) A.append(a) B.append(b) A.sort() B.sort() if N % 2 == 0: # (※1) A_med = ((A[N//2] - A[N//2 - 1]) // 2) + A[N//2 - 1] B_med = ((B[N//2] - B[N//2 - 1]) // 2) + B[N//2 - 1] else: A_med = A[N//2] B_med = B[N//2] ans = 0 for i in range(N): # (※2) ans += abs(A[i] - A_med) + (B[i] - A[i]) + (abs(B[i] - B_med)) print(ans)
解説
N人の買い物客の移動時間が最小となる入口と出口の場所を設定する問題です。
i番目の買い物客は入口→マスAi→マスBi→出口という経路をたどります。
このとき、マスAi→マスBiの移動時間は入口と出口の位置に関係なく一定ですので、すべての買い物客の入口→マスAiとマスBi→出口の移動時間を最小とすればよいことになります。
すべての買い物客の入口からマスAi（あるいはマスBiから出口）までの移動時間を最小にするにはAiの（平均値でなく）中央値をとればよいようです。
したがって※1でAとBの中央値A_medおよびB_medをNが偶数と奇数で場合分けし、求めています。
あとはN人の移動時間をすべてans変数に足し合わせて出力すればACでした。
問題を解くには数学的に正しく効率の良い方法を思いつく必要がありますが、コンテストの際にぱっとアイデアを出すのは私には難しいと感じました。
数多く問題を解き、地道にパターンを覚えていくしかないようですね…
初心者脱出までの道のりは長いです。
JOI 2007 本選 3 - 最古の遺跡とJOI 2008 予選 4 - 星座探しは理解ができませんでした。
宿題として理解出来たらこの記事に追記していくようにします。
初中級者が解くべき過去問精選100 問の記事をまとめたページはこちら
ebisuke33.hatenablog.com
蟻本の類題も解いていますので興味があればこちらもおすすめです。
ebisuke33.hatenablog.com
