c_Comp-Prog yukicoder No.2386 Udon Coupon (Easy)
あんまり筋の良くない解き方だけど、この制約ならではの解法が有るので
問題
問題文参照
考察
うどん札を5枚消費する$ B円の割引と10枚消費する$ C円の割引があることに注目する。
この時、それぞれは割り切れる関係(名前がわからない)なので、以下の条件が使用できる。
- $ C円の割引一回より$ B円の割引2回を行ったほうが割引金額が同じか安くなる場合、$ C円の割引を使うことはない
- それ以外の場合、$ B円の割引を使うのは最大1回
また、$ 1 \le N \le 2 \times 10^5なので、うどん札を3枚消費する$ A円の割引の回数を固定して考えた後、上記の条件を適用することで$ O(N)でこの問題を解くことが出来る。
実装
code:solve.cpp
int main(){
long long n,a,b,c;cin>>n>>a>>b>>c;
long long ret = 0;
for(int i = 0; n/3 >= i; i++){
long long x = n-(3*i);
long long val = i*a;
if(2*b >= c){
val += (x/5)*b;
}else{
val += (x/10)*c;
if(x%10 >= 5){
val += b;
}
}
ret = max(ret, val);
}
cout << ret << endl;
return 0;
}
振り返り
普通に想定解法思い浮かばなくて退化ですか?ってなったんだけど、一周回って見えなかったな...