[全探索：工夫して通り数を減らす全列挙]を抑える pythonで競プロ

Qiitaで紹介されていた初中級者が解くべき過去問精選 100 問をpython解いてみようという試みです。

第2弾として、[全探索：工夫して通り数を減らす全列挙]の項の問題を解いていきます。(第1弾の「全探索：全列挙」はこちら)

第5問 : 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 枚に組み替える以外にはありません。このためには最小で何円が必要でしょうか？なお、ピザの組み替えにより、必要な量を超えたピザが発生しても構いません。

https://atcoder.jp/contests/abc095/tasks/arc096_a

制約条件

• 1≤A,B,C≤5000
• 1≤X,Y≤105
• 入力中のすべての値は整数である。
https://atcoder.jp/contests/abc095/tasks/arc096_a

解答

説明

方針としては、以下の通りになります。

まず、必要な枚数分をAピザ、Bピザでそのまま購入すると考える
その後、ABピザに変えた方が良いかを判定していく

ABピザに変えた方が良いパターンは、3パターンあります。

Aピザ、Bピザ1枚ずつよりも、ABピザ2枚の方が安い場合
Aピザ1枚よりも、ABピザ2枚の方が安い場合
Bピザ1枚よりも、ABピザ2枚の方が安い場合

これらを上から順に判定していき、これらを満たす度にAピザ、Bピザの個数と合計価格を更新していき、最終的な合計価格を出力しています。

第6問 : Half and Half

問題文

AtCoder 社は、オフィスの入り口に 3 桁の暗証番号を設定することにしました。
AtCoder 社には N 桁のラッキーナンバー S があります。社長の高橋君は、S から N-3 桁を消して残りの 3 桁を左から読んだものを暗証番号として設定することにしました。
このとき、設定されうる暗証番号は何種類あるでしょうか？
ただし、ラッキーナンバーや暗証番号はいずれも 0 から始まっても良いものとします。

https://atcoder.jp/contests/abc095/tasks/arc096_a

制約条件

• 4≤N≤30000
• S は半角数字からなる長さ N の文字列
https://atcoder.jp/contests/abc095/tasks/arc096_a

解答

説明

MAX3万桁の数列から作成できる暗証番号を探すのは大変です。

なので、そもそも暗証番号になりうる3桁の数列1000通りから、その内何通りがラッキーナンバーから作成可能かを探索する方針としています。

ラッキーナンバーの前から順に3桁の数字が並んで見つかれば、暗証番号の条件を満たすことになります。

第7問 : 最古の遺跡

問題文

昔, そこには集落があり, 多くの人が暮らしていた. 人々は形も大きさも様々な建物を建てた. だが, それらの建造物は既に失われ, 文献と, 遺跡から見つかった柱だけが建造物の位置を知る手がかりだった.
文献には神殿の記述がある. 神殿は上から見ると正確に正方形になっており, その四隅には柱があった. 神殿がどの向きを向いていたかはわからない. また, 辺上や内部に柱があったかどうかもわからない. 考古学者たちは, 遺跡から見つかった柱の中で, 正方形になっているもののうち, 面積が最大のものが神殿に違いないと考えた.
柱の位置の座標が与えられるので, 4 本の柱でできる正方形のうち面積が最大のものを探し, その面積を出力するプログラムを書け. なお, 正方形の辺は座標軸に平行とは限らないことに注意せよ.

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

解答

説明

まず、正方形を探す際に全ての点から4点選択するとなると、最大数₃₀₀₀C₄で恐ろしいオーダー数になってしまいます。なので、2点を選択してこれを1辺とする正方形が存在するかを探索することで₃₀₀₀C₂と現実的な処理時間で終了するようにします。

pythonには、itertoolsという非常に便利なライブラリが存在します。リストからいくつかの組み合わせを作成したい時は、itertoolsのcombinationsとして既に実装されているのでこれを使いましょう。

2点を1辺とする正方形が存在するか否かの判定に関して、2点が確定した時の残りの2点は2パターンに絞られます。p₁=(x₁, y₁),p₂=(x₂, y₂)と置くと残りの2点は、

p₃=(x₂-(y₂-y₁), y₂+(x₂-x₁)), p₄=(x₁-(y₂-y₁), y₂+(x₂-x₁))
p₃=(x₂+(y₂-y₁), y₂-(x₂-x₁)), p₄=(x₁+(y₂-y₁), y₂-(x₂-x₁))

となります。この2点が与えられた点に含まれていれば、正方形として判定することが可能です。また、ソートされている前提であれば、回転方向を一意にとしても必ず1辺では判定に引っかかることになるので、実際は片方の判定のみで問題ありません。(ソートし忘れていても通ったので、入力値はソード済みっぽいです。)

第8問 : AtCoder Market

問題文

AtCoder マーケットは、1 000 000 000 個のマスが 1 列につながったマス目で表されるスーパーマーケットである。ここでは、左から i 番目のマスを「マス i」とする。
ある日、N 人の買い物客が AtCoder マーケットに来る。i 人目の買い物客は、マス A_i にある品物とマス B_i にある品物を買う。
square1001 君は、AtCoder マーケットに入口と出口を 1 つずつ設置することにした。

入口と出口はいずれかのマス目に設置する。入口と出口は同じ場所にあってもよい。
そのとき、買い物客は次のような経路で移動する。
• まず、入口からスタートする。マス A_i と B_i を経由して、出口でゴールする。
すべての買い物客について、隣り合ったマス目に進むのに 11 秒かかるとき、最適に入口と出口を設置したときの「すべての買い物客の移動時間の合計」の最小値を求めなさい。
https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b

制約条件

• 1≤N≤30
• 1≤Ai<Bi≤1 000 000 000
https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b

解答

説明

この問題は、実質以下の合計をと置き換えることが可能です。

各買い物客のマスA_i-B_i間の移動コストの合計
各買い物客のマスA_iと入口間の合計コストの最小値
各買い物客のマスB_iと出口間の合計コストの最小値

マスA_i-B_i間の合計コストに関しては、入力値からそのまま差分を取るだけなので、説明は省略します。

入口出口の場所の判定は以下の手順で実施しました。(重複するので、入口の説明とします。)

まず、入口がマス0にあるとして、マスA間との合計コストの計算を行います。
そして、ソートをしたマスAから最も小さい値を取り出し、最小のマスAを入口として再度コスト計算を実施します
2で取り出した最小の値を除いて、繰り返し2を実行していき、最終的に最もコストが小さいものが最適な入口ということになります。

入口を+1マスした時に生じる合計コストの差分は、+(入口より小さいマスAの数) - (入口より大きいマスAの数)になります。差分を用いることによって、マス数分合計の計算を毎回行わずに済み計算量を抑えることが可能です。

また、先ほどの式で、合計コストの差分が変化するタイミングはマスAと仮置きした入口が重なったタイミングだと分かります。そのため、マスAが存在しない区間は、コストが単調減少、短調増加し最小値となることはないので計算する必要はありません。

第9問 : 星座探し

問題文

あなたは星空の写真の中から星座を探している．写真には必ず，探したい星座と同じ形・向き・大きさの図形がちょうど一つ含まれている．ただし，写真の中には星座を構成する星以外に余分な星が写っている可能性がある．

例えば，図 1 の星座は図 2 の写真に含まれている（丸で囲んで示した）．与えられた星座の星の座標を x 方向に 2，y 方向に -3 だけ平行移動すると写真の中の位置になる．

探したい星座の形と写真に写っている星の位置が与えられたとき，星座の座標を写真の中の座標に変換するために平行移動するべき量を答えるプログラムを書け．

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d

解答

説明

ビットマップとして、全エリアで一致するかどうかを判定しようとするとどう考えてもオーダー数が収まらないので、星座の星の内適当な一つを基点に差分を取る方針としました。

基点とした星と写真上の各星が一致すると仮定して、星座の各差分の座標に星が存在しているかをチェックしています。オーダー数が、写真上の星の数 * 星座の星の数に抑えることが可能になります。

まとめ

工夫が必要なものとしてまとめられている通り、考えれば解ける問題ばかりで非常に楽しかったです。

ただし、7問に関しては、Pythonだと想定解がTLEすることがあると記載があった通りで、想定解を実装してからの戦いが大変でした。ただ、本当に詰めて詰めないと通らないので、知らないことを学ぶ機会になって良かったと思います。

次回は、[全探索：ビット全探索]を解いてみます。ただ、ビット探索がそもそもあまりイメージ湧いていないので、苦戦しそうな感じがします。