ABC153解説 - Motsu_xe 競プロのhogeやfuga

結果は46:58 (2ペナ) 382位でした。今回のセットはかなり簡単だったので、最悪です。黄色返上しろ。言い訳は後でします…。

A - Serval vs Monster

思考

サーバルちゃんは私のアイコンにもいますね、とても良い子です。
0になるまで殴るんだから $ceil(\frac{H}{A})$ で良いですね。けもフレは平和っぽい感じの雰囲気を醸し出しつつ、敵は普通に殴って屠りますからね、自然を生き抜くのは大変なことです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int h,a;
    cin>>h>>a;
    cout<<(h-1+a)/a<<endl;
}

コンテスト中のACコード

B - Common Raccoon vs Monster

思考

アライさんは色々必殺技考えてそうですね、可愛いです。
同じのを使わなければ良いだけなので、必殺技はせっかくだから全部使うことにして良いです。その方が楽しいですし、損はないです。なので総和とモンスターの体力の大小を見れば良いです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int h,n,ans{},a;
    in>>h>>n;
    fr(i,n) in>>a,ans+=a;
    cout<<(ans>=h?"Yes":"No")<<endl;
}

コンテスト中のACコード

C - Fennec vs Monster

思考

アライさんに続いてフェネックの登場ですね。マイペースちぇいさーは良い曲なのでみなさん聞きましょう。
世の中には必殺技を名乗っている必殺技じゃないもの(アライさんの必殺技など)が蔓延っていますが、これは正真正銘の必ず殺す技で、さすがフェネックなのだ！って感じです。折角なので必殺技は強いやつに使いましょう。マスターボールでコイキングを捕まえるような真似はやめた方がいいです。ソートして、弱いやつを倒すのにかかる回数だけ数えれば良いです。サンプルをみるとオーバーフローに気をつけないといけないことがわかり優しい。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    int n,k;
    in>>n>>k;
    vector<ll> h(n);
    for(auto&i:h) in>>i;
    sort(h.begin(),h.end());
    ll ans{};
    fr(i,n-min(n,k)) ans+=h[i];
    cout<<ans<<endl;
}

コンテスト中のACコード

D - Caracal vs Monster

思考

カラカルですね。ゲーム版とかアニメ2期とかでメイン張ってた子ですね、可愛いです。
スライム的なモンスターで倒すと分裂するようですが、倒すのにかかる回数は、体力で一意に定まるため、分裂後の2匹を倒すのにかかる回数は同じです。よってf(h)を体力hのモンスターを倒すのにかかる回数とするとf(h)=2*f(h/2)+1となります(ただしf(1)=1とする)。これは再帰的に計算すれば停止するので、これで終わりです。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll f(ll h){
    if(h==1) return 1;
    return 2*f(h/2)+1;
}

int main(){
    ll h;
    in>>h;
    cout<<f(h)<<endl;
}

コンテスト中のACコード

E - Crested Ibis vs Monster

思考

トキですね。アニメ1期では個人的にこうざん回がかなり好きなので思い入れのあるキャラの1人です。
ところでこれはほぼただの個数制限付きナップザックで、ダメージをD以上与えるのにかかる最小の魔力を管理すれば簡単に解くことができます。PCが起動してくれなくて、参加が遅れたので、それがなければ4分くらいだったのですが、それでもFAには程遠いですね、いくら典型でも1分台は凄いです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int h,n;
    cin>>h>>n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;++i) cin>>a[i]>>b[i];
    vector<int> dp(h+1,1e9);
    dp[0]=0;
    for(int i=0;i<n;++i){
        for(int j=1;i<=h;++i){
            if(j<a[i]) dp[j]=min(dp[j],b[i]);
            else dp[j]=min(dp[j],dp[j-a[i]]+b[i]);
        }
    }
    cout<<dp[h]<<endl;
}

コンテスト中のACコード

F - Silver Fox vs Monster

思考

ギンギツネです。湯けむりユートピアはいいぞ、みんな聞こう。
ところでこの問題、攻撃が爆弾じゃなくて必殺技だったら典型問題で、貪欲に端から取っていけばいいです。攻撃が爆弾でも結局は同じで、一番左のモンスターを倒す爆弾は、左端でギリギリ倒して悪いということはありません。なので左端から順に倒していけば良いだけです。必殺技なら誰を倒したか前から見ていけばいいだけなのですが、爆弾なのでそうもいきません。これはセグメント木を使って簡単に実装できます(まず自分より左に2*D以内の点を見つけて、セグ木でどの点で何回爆発させたかを覚えておけば、それを足せば良いです)*1。ここからが言い訳ポイントなんですが、持っていたセグメント木のライブラリが壊れていました(なんで？？？)。仕方がないのでBITを書いたんですがなんかバグりました(は？？？)。意味わからないのでネットからセグメント木持ってきたんですが、なんか通りません(？？？)。よく見たらAとDを途中から逆にしていました(何でサンプル合っちゃうの…)。とか何やかんややっていたら実装含めて10分もかからなかったはずなのに二十数分の時間と2つのペナルティが付いていました(クソ)。最悪です。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

struct SegmentTree{
    void update(i,x); //i番目のノードにx足す
    ll query(i,j); // [i,j)区間の値の和を返す
};

int main(){
    ll n,d,a;
    cin>>n>>d>>a;
    ll ans{};
    vector<pair<ll,ll>> xh(n);
    for(auto&p:xh) in>>p.first>>p.second;
    sort(xh.begin(),xh.end());
    SegmentTree st(n);
    for(int i=0;i<n;++i){
        ll x,h;
        tie(x,h)=xh[i];
        int l=lower_bound(xh.begin(),xh.end(),
                      make_pair(x-2*d,0ll))-xh.begin();
        ll s=st.query(l,i);
        h-=a*s;
        if(h<=0) continue;
        int S=(h-1+a)/a;
        st.update(i,S);
        ans+=S;
    }
    cout<<ans<<endl;
}