値段の組み合わせによる最小値問題が正しく求まらない

Question

下記のリンクの問題を解いていたのですが，15個あるケースの内3つがWAで不正解になってしまいます．数字の大きさ的には問題ないと思うのですが場合分けのところなどで間違っている個所がありましたら教えていただきたいです．
また，自分のやり方では全部の組み合わせを試して最小値を求めているのですが，もう少しうまいやり方がありそうな雰囲気がある問題だと思うので，なにか方法があれば教えていただきたいです．よろしくお願いします．

問題

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>


int main(void){

    int Aprice,Bprice,Cprice;
    int numA,numB;

    scanf("%d %d %d %d %d",&Aprice,&Bprice,&Cprice,&numA,&numB);

    long ans=500000000;
    int numMAX=0;
    if(numA>numB) numMAX=numA;
    else numMAX=numB;

    long price;

    for(int i=0;i<=numMAX;i++){
        if(numA>=i && numB>=i) price=Aprice*(numA-i)+Bprice*(numB-i)+Cprice*2*i;
        else if(numA>=i && numB<i) price=Aprice*(numA-i)+Cprice*2*i;
        else if(numA<i && numB>=i) price=Bprice*(numB-i)+Cprice*2*i;
        
        if(price<ans) ans=price;
    }

    printf("%ld\n",ans);
    
    return 0;
}

Answer 1

A,B,Cがすべて5000で、X,Yがともに10^5である場合、
10^9が最小値となり、ansの5*10^8を更新できません。

ansの初期値を、intが取りうる最大値にしておくのが一番安全です。

Comments

[grape_ll]

理論上の最大値の見積もりが杜撰でした．気を付けます．ご指摘ありがとうございます．

Answer 2

正しい解にならないのはansの初期値が理論上の最大値よりも小さいからでしょう。

全探索以外の解き方としては、例えば

price=Bprice*(numB-i)+Cprice*2*i;

この式を見ると、priceは傾きがCprice * 2 - Bpriceのiの一次式になっています。なので、価格が最小になるのはiが最小の場合か最大の場合かのどちらかで、それは傾きの正負を見れば計算せずともわかります。
同様のことを3つの式についても考えれば、3つともiの一次式になってるのでこれを解くか、条件を満たす最大最小のiを調べるかをすることで、すべてのiを調べずに最小値が出せます。

Comments

[grape_ll]

理論上の最大値を正しく初期化しましたら無事通りました．ご指摘ありがとうございます．

確かにiに関する一次関数とみて，傾きを気にしてあげると計算量の削減ができますね．プログラミングにおいてそのような考え方で解いたことがなかったので大変参考になりました．ありがとうございます．

Answer 3

なぜそのコードで通らないかは分かりませんが、もう少しうまい場合分けができそうです。
A+B<=2Cの時、ABのピザを買うメリットはないので、答えはA*X+B*Yです。
A+B>2Cの時、ABのピザを買えば買うほど安くなるので、AがXを、BがYを超えない最大の2 * min(X,Y)枚買うとします。
さらに、XとY大きい方のピザをmax(X,Y)-min(X,Y)枚を買う必要があります。
仮に、Xの方が大きかったとしましょう。
Aを揃えるのに、A>2CならBは無駄になってもCを2*(max(X,Y)-min(X,Y))枚買った方が安いです。
もしA<2CならAを直接max(X,Y)-min(X,Y)枚買った方が安いです。

--追記--
なぜ質問のコードでACとならないかについて追記します。
片方のピザを余らせた場合に値引きをしてしまっているからです。
もしA!=Bなら、numA-iまたはnumB-iが負になることがあります。
つまり、このコードだと余ったピザ分だけ値引きしていることになってしまいます。

Comments

[grape_ll]

通らない理由は理論上の最大値がうまく初期化できていないからでした．

場合分けは確かにおっしゃるやり方でもできそうで，実際，自分も最初はそのようなアプローチでやってみようと考えたのですが，関数をmax関数やmina関数を作ったり分岐が少し複雑になったりするよりかは，単純な場合分けの方が自分の頭では混乱しなくて済むのではないかと考えてこの方法をとりました．
また，追記についてですが，このコードになる前にその値引きをしていることコードをかいてしまっていたので，改良してこのコードでは場合分けによって値引きがされないようになっていると思います．

ですがこれからのコードを書いていくうえで注意すべき点の確認は出来ましたの．ご回答ありがとうございました．