abc153_dの解き方の解説単純だけどTLEしてしまう問題の考え方

2020/05/22 14:05

AtCoder Beginner Contest 153のD問題 Bouquetを解く。必要となる素数で割ったあまりを取得するクラスと組み合わせ数の計算方法の解決

感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。

今日はAtCoder Beginner Contest 153 の D 問題 Caracal vs Monsterです。

問題文はやけに簡単です。ちょっと実装してみましょう。

#include <bits/stdc++.h>

using namespace std;

const int MOD = 17;

long long resolve(long long h) {
    long long count = 0;

    queue<long long> monsters;
    monsters.push(h);
    while (!monsters.empty()) {
        // モンスターが残ってたら攻撃する
        count++;
        long long monster = monsters.front(); monsters.pop();
        if(monster == 1) {
            // モンスターの体力が1なら、そのモンスターの体力は0になる
        } else {
            // 2以上なら2つに割れる
            monsters.push(monster / 2);
            monsters.push(monster / 2);
        }
    }
    return count;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false); cout << fixed << std::setprecision(20);

    long long h;
    cin >> h;
    cout << resolve(h);
}

これだけだったら C 問題クラスですね。流してみると TLE です。制約で H が 10 の 12 乗、この解説によると 9 乗までしかループ回せません。その 1,000 倍なので当然ですね。

答えを眺めてみる

こういう簡単に書けそうな問題はとりあえず書いてみて、答えの法則を眺めてみるのが大事です。

main 関数のみ書き換えます。

int main() {
    cin.tie(0); ios::sync_with_stdio(false); cout << fixed << std::setprecision(20);

    for(long long i = 1; i < 20; i++) {
        cout << i << ":" << resolve(i) << endl;
    }
}

結果はこうなりました。

1,2,4,8,16 で値が変わってますね。

答えも 1,2,4,8,16 の 2 倍 - 1 という法則が読み取れます。攻撃するとモンスターの数が倍になるという問題からも、しっくりくる答えです。

これにあわせて実装してみましょう。

#include <bits/stdc++.h>

using namespace std;

const int MOD = 17;

long long resolve(long long h) {
    long long n = 2;

    // 1,2,4,8,16...でブレークする
    while(h >= n) {
        n *= 2;
    }
    return n - 1;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false); cout << fixed << std::setprecision(20);

    long long h;
    cin >> h;
    cout << resolve(h);
}

abc153_dの解き方の解説 単純だけどTLEしてしまう問題の考え方

答えを眺めてみる

abc153_dの解き方の解説単純だけどTLEしてしまう問題の考え方