No.176 2種類の切手 - shifth’s blog

アルゴリズム的には全探索なのだけど、計算量見積もりがうまくできなかった。
最適化対象式の対称性に気がつけば O(√T) 計算量が導きだせたかも。
T-m*B >= 0 の判定が抜けてしまった...。

class TwoKindsOfStamp
{
public:
    ll roundUp(ll a, ll b) {
        ll x = ceil((double)a/b);
        return (x>=0)? x : 0;
    }
    void solve(void)
    {
        ll A,B,T;
        cin>>A>>B>>T;

        // f(n,m) = n*A + m*B >= T
        // を満たす f(n,m) の最小値をもとめればよい
        //
        // A,B < 10^9 なので単純な全探索では間に合わない。
        //
        // m を固定してみる。このとき条件をみたすには n は
        // n >= (T - m*B)/A
        // n >= ceil((T-m*B)/A)
        // を満たす必要がある。
        //
        // よって m を固定したときのとりうる f(n,m) の最小値は
        // f(n,m) = ceil((T-m*B)/A)*A + m*B
        //
        // m > T/B を超えると T-m*B < 0 になってしまうので m <= T/B まで探索すればよい。
        // このままだと B が小さいときは T < 10^9 のままなので間に合わない
        //
        // そこで m > A のときを考える
        // f(n,m) = n*A + (m'-A*k)*B  (m = m'-A*k, k >= 1)
        //        = (n-B*k)*A + m'*B (m' < A)
        // とかけるので m <= A と見なしてよい
        //
        // よって探索上限は min(T/B,A) となり
        // T/B == A つまり O(√T) < 10^4 にて計算できる。

        // A,B > T のケースもあるので +1 して計算する
        ll ret = max((T/A+1)*A, (T/B+1)*B);
        for (ll m = 0; m <= min(T/B+1,A); ++m)
        {
            ll x = roundUp(T-m*B,A)*A + m*B;
            ret = min(ret,x);
        }
        cout<<ret<<endl;
    }
};