草体にぼ日記

だらだらと

2020年7月3日 日記

2021年 7月 3日

まえがき

エキセントリックしんせてぃっくかどまつ


合成数は英語で こんぽしっとなんばー

Synthetic は合成って意味の英単語

迷子の迷子の迷子迷子の子猫チャン

最近、エキセントリックっていう言葉を使っています。
意味は知らないので今調べてみます。 エキセントリック

《ダナ》普通のものとひどく変わったさま。風変わりなさま。奇矯。

ダナって何 笑

つまり普通じゃないってことダナ

健康管理

前略お母様って感じ。

何した

大学に行ったよ

具体的に

徒歩で5分

自慢したいこと

  • エキセントリックカドマツをbit全探索みたいに(イメージ)解きました。 以下は、SyntheticKadomatuの解き方の大枠は分かっているものとして俺がイキるだけです。
    bit全探索みたいにっていうのは、bit全探索だと、あるbit = 1011(2進数表記) が会った時、0番目は1だからuse,1番目をuse,2番めをnot use, 3番目をuseってするじゃないですか、 その要領で今回は, mask = 0213(4進数表記) があったとき、0番目を長さCの竹を作るために使う,1番目を長さAの竹をつくるために使う、..., 3番目の竹は使わない。みたいにした。っていうのが僕のいうbit全探索みたいな解き方です。(0と1ではないのでbitではない)

まあ、結局やりたいことは4nの全探索なので、ループの回数はn4です。
よって

for(int mask = 0; mask < (1 << 2 * n); mask++)

のループです。ちなみに、maskっていう変数名を使っているのは、maskって変数名をbit全探索で使っている人を見たことがあるからです。
(1 << n)が2nを表していて、4n = (22n)(2の二乗のn乗)なので,(1 << n * 2) で 4のn乗を表せます。

int main()
{
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> l(n);
    rep(i, n)cin>>l[i];

    ll ans = 1e9;
    for(int mask = 0; mask < (1 << 2 * n); mask++){
        int A = 0, B = 0, C = 0;
        ll tmp = mask; // tmpを用意しないと、mask /= 4;の処理を行うことになってしまって、バグる
        int synthetic = 0; // Aに使う竹の数とBに使う竹の数とCに使う竹の数を持つ変数。
        rep(i,n){
            int now = tmp % 4;
            if(now == 0) ;// not use
            else synthetic++;
            if(now == 1) A += l[i];
            if(now == 2) B += l[i];
            if(now == 3) C += l[i];
            tmp /= 4;
        }
        if(A != 0 && B != 0 && C != 0){
            chmin(ans, (ll)(abs(a-A)+abs(b-B)+abs(c-C)+10*(synthetic-3)));
        }
    }
    cout << ans << endl;
}

コメントを続けます。
まぁ、要するにsyntheticは4進数n桁でmaskを表したときに、何桁が1以上(0 つまり "その竹を使用しない"ではない)かを持っているだけです。

10 * synthetic - 3;

の部分は、Aに3本の竹を使っているとき、合成魔法を使った回数は2回なので、AとB,Cで3回分マイナスしましょね。ってこと。

今日解いた問題

ABC063 D- Widespread

  • [二分探索]

常に体力が最も大きい魔物を爆心地として選ぶ。という操作をしたときに最短手数で全ての魔物を消せる。それはそうですが、明らかに計算量的にダメそうです。
このときの計算量をテキトウに考えてみます。
まず、1回の操作でN体のHPを更新します。このときの計算量はO(N),さらに、この後に次に体力が多いやつを知りたいので体力の配列をソートしますO(NlogN)
つまり、1回の爆発ごとにO(NlogN)かかる。
で、爆心地と選んでもA=2の時、体力が2ずつしか減らないので、h[i] = 1e9のとき、1e9/2回爆心地としなきゃ行けない。だからやべえときは1e9 * (NlogN) になってまぁ無理だろ。って感じ

じゃあ二分探索でどう解くかって考える。
とりあえず、K回の操作で倒せるならK+1回の操作でも倒せる的なのは分かるから、そういう単調性から二分探索が使える。
必要なのは、ある爆発回数K回で全てのモンスターを全滅させるかどうかを判定する方法。

K回(コード中ではmid回)の爆発で全部ぶっ殺せるかを判定する方法を述べます。 1. K回爆発させるから、少なくともB(爆心地以外のモンスターが受けるダメージ) * mid のダメージを全てのモンスターが受ける 2. 上のダメージをモンスターが受けた後の体力に対して、何回爆心地としてそのモンスターを選べば殺せるかを考えてtmpに足す(このとき、a-bの追加ダメージを爆心地として選んだ回数だけモンスターに与えられる) 3. tmp が mid回以下なら、mid回の爆発で全滅させれる。

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> h(n);
    rep(i, n)cin>>h[i];
    //sort(h.rbegin(),h.rend());

    ll fire = a - b; // 爆心地として選ぶことでa-bの追加ダメージ
    ll ng = 0, ok = 1e9+5; // 体力が各モンスタ- 1e9以下なので、1e9回の爆発をさせれば絶対全滅出来る。のでok=1e9+5(5は予備)
    while(ok - ng > 1){
        ll mid = ok + ng; mid /= 2;
        ll tmp = 0;
        rep(i,n){
            ll hp = h[i];
            hp -= mid * b;
            if(hp <= 0) continue;
            tmp += (hp + fire - 1) / fire;
        }
        if(tmp <= mid){
            ok = mid;
        } else {
            ng = mid;
        }
    }
    cout << ok << endl;
}

俺は天才です。

第16回日本情報オリンピック予選(オンライン)

  • [bitDP]

ABC142 E- Get Everything

  • [bitDP]

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)