—2025/04/19
今日は土曜日、気温が上昇していましたが、穏やかな一日でした。
Atcoder095回目を挑戦しました。これはまた面白いです。
宅配ピザに関わる話です。
「A ピザ」「B ピザ」「AB ピザ」の 3 種類です。A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ 1 枚あたりの値段はそれぞれ A 円、B 円、C 円です。
A ピザ X 枚と B ピザ Y 枚を用意するために、もっとも安い金額はいくらでしょう。
こんな感じで、
どう考えたら、よろしいでしょうか？
まず、手を動かしてみます。
真っ先思ったのはAピザX枚、BピザY枚、これで完結です。でも、一番安いかどうかがわかりません。
それで、Cを1枚購入して、総額はどうなりますか？Aピザは X – 1/2 枚に、Bピザは Y – 1/2 枚になり、総額は A × ( X – 1/2 ) + B × ( Y – 1/2 ) + C × 1 になります。
Cピザをどんどん購入して、金額はどのように変化していきますか？
Cピザを最大何枚まで購入できるを考えました。A ピザ X 枚と B ピザ Y 枚を用意する必要があるので、Max(X,Y) (つまり、XとYの内、大きい方）× 2倍 枚数のC ピザを購入すれば、上記の条件が必ず満たせます。
図で現わしてみました。
以上の流れになりますね、これで問題を解決することができました。
つまり、Cの枚数で判断しながら、最小金額を記録していくという方法です。
このようなアルゴリズムは全探索処理の一種だと思います。
全探索処理を行う際、もっとも重視されているのは実行時間の見積もりです。処理結果は２秒以内に出さなければいけません。
今回の処理において、X,Yは両方とも10⁵以下なので、つまり最大実行回数は2×Max(X,Y)で、2×10⁵です。一般に、コンピューターには、１秒10⁸～10⁹回実行すると言われているので、今回の問題を全探索方法で用いて、問題がありません。