ABC 085 D Katana Thrower - gotutiyan’s blog

問題
D - Katana Thrower
N本の刀があり、それぞれの刀はAとBの攻撃力を持つ。無限回できる振る攻撃はAのダメージを与えて、1回しかできない投げつける攻撃はBのダメージを与える。投げてしまうと、その刀は使えなくなってしまう。Hの体力を削りきるための最小手数を求める。

解法
公式解説にもあるように、この問題は投げた刀も使えるように設定を変えても解けてしまいます。
例えば、以下のようなテストケースで、3本の刀があり、100の体力を削ることを考えます。

さて、初手で一番ダメージを与えられるのは３本目を投げることです。でも３本目は振るダメージだけで見たときでも最強なので、投げてしまうと最強の刀を失います。では、投げてトドメをさせるようになるまでは３本目をひたすら振るのが良さそうです。この時、

//投げた刀も使える設定
//1.最初に投げて、それ以降振る
　20+11+11+11+...11=108
//2.トドメを刺せるタイミングでやっと投げて、それまでは振る
　11+11+11+....11+20=108

となり、全く変わらないことが分かります。１番では投げても使えるとは言っても、再度投げることはできないことに注意します。

次にこのテストケースを見てみます。4本の刀で100の体力を削ります。

パッと見、投げる刀は2,3,4本目の３本強いものがあるので、いつかは投げたいところです。しかし４本目の刀は振るダメージが最強なので、できるだけ置いておきたいです。つまり、やはり投げてトドメを刺せるところまでは一番強い刀で振るのが良さそうです。

以下では、すべての刀の中で、振るダメージの最大値をAmaxとします。
投げるダメージのなかに、Amaxより大きいものがある
→ 投げてトドメを刺せるようになるまで、Amaxを振る
全ての投げるダメージよりもAmaxが大きい
→ひたすらAmaxを振る

上のような方針になります。
これを場合分け無しで解決するには、Amaxと、投げるダメージをソートしたものを用意して、Amaxより投げるダメージが大きい間、順番に投げていき、それでもHが削りきれなければAmaxで振り続ける、ということになります。

int n,h;
    int ans=0;
    cin>>n>>h;
    int amax=0;
    vector<int> b(n);
    //Amaxを求めつつ、投げるダメージを配列に格納
    rep(i,0,n){
        int x;
        cin>>x>>b[i];
        amax=max(amax,x);
    }
    Sort(b);
    //昇順ソートでやったので、添字を一番後ろから見ます
    int index=b.size()-1;
    while(b[index]>=amax&& index>=0){
        h-=b[index];
        index--;
        ans++;
　　//投げだけで削りきれたらそこで終了です。最初から投げだけでトドメをさせるということです。
        if(h<=0){
            cout<<ans<<endl;
            return 0;
        }
    }
    //一回以上振らないと投げでトドメをさせないので、Amaxで振る回数を求めます。
    //割り切れないとき、素直に割った回数＋１しなければいけないことに注意です。
    if(h%amax==0)cout<<ans+(h/amax)<<endl;
    else cout<<ans+(h/amax)+1<<endl;