Atcoderを振り返る(AtCoder Beginner Contest 323)

はじめに

ここ数か月ほぼ毎週参加していますが、今回の問題の解き方で今後使えそうなものがあったため自分用にまとめています。

D - Merge Slimes

こちらの問題ですね。どういう問題なのかは、実際に上のサイトに飛んでいただいて確認してもらえればと思うのですが、要するに以下のような問題に変換できます。

• 小さいサイズ(a)のスライムから個数(b)を確認していき、それが2体以上いるならば倍の大きさ(2a)のスライムの数をb/2増やす。
• 最終的に小さいスライムから一番大きいスライムまでの数を計算していく

文字だけで見ると簡単そうなんですが、制約が個人的に厳しくて悩みました。
一つ方法として考えたのは配列をめちゃくちゃ作って、大きさの配列の番号に個数を入れていくというやり方で、下のような例の場合このように解けばいいじゃんと考えていました

3
3 3
5 1
6 1

int ans[100009];
ans[3] = 3;
ans[5] = 1;
ans[6] = 1;

//ans[3]は個数が3以上あるため減らす
ans[3*2] += ans[3] / 2;

ただこの場合、配列の大きさが足りなくなるんですね。（大きさが1000000000,数が1000000000
のスライムがいた場合、もっと大きい値の配列が必要になるが作れない）

そこでいろいろ方法を調べると、上記よりも全然いい方法がありました。それが連想配列を作るやり方です。
先にコードを見せます

#include <iostream>
#include <map>

using namespace std;

int main() {
    //Nに標準入力を代入する
    int N;
    cin >> N;

    map<long long, long long> slime_count;
    for (int i = 0; i < N; i++) {
        long long S, C;
        //S(スライムの大きさ),C(スライムの数)に標準入力を代入する
        cin >> S >> C;
        //連想配列を使い、スライムの大きさに対して何体いるのかを代入する
        slime_count[S] += C;
    }

    //連想配列が終わるまで、for文の中で連想配列のキーが増える可能性もあるため、これで最後まで確認する
    for (auto it = slime_count.begin(); it != slime_count.end(); ) {
        long long size = it->first;
        long long count = it->second;

        //数が2以上なら合体させる
        if (count >= 2) {
            slime_count[size * 2] += count / 2;

            //限界まで合体させたため、現在のイテレータの個数は0か1になる
            it->second %= 2;
            //もし個数が0なら確認する必要がないため削除
            if (it->second == 0) {
                it = slime_count.erase(it);
            } else {
                ++it;
            }
        } else {
            ++it;
        }
    }

    long long result = 0;
    //連想配列slime_countのキーが残っている値を確認していき、足していく
    for (auto &p : slime_count) {
        result += p.second;
    }

    cout << result << endl;

    return 0;
}

最初に自分が考えていた方法の場合、無駄に配列を作り、また配列の数にも限界があります。
それを連想配列を使うことにより、配列の個数を最低限に抑え、今回の条件を満たす大きさの個数を保存することができます。
このやり方だとサイズと個数が大きい以下の場合にも対応ができます

1
1000000000 1000000000

map<long long, long long> slime_count; //スライムのサイズと個数の連想配列
slime_count[1000000000] = 1000000000; // 先ほどの式よりキー1000000000に対応する値を設定します

for文
{
    slime_count[2000000000] = 500000000;
    slime_count[1000000000] = 0; //0なので子の連想配列は消して次のイテレータ(2000000000)に移動する

    slime_count[4000000000] = 250000000;
    slime_count[2000000000] = 0;
}

みたいなことを繰り返して最終的に個数が2よりも少なくなったタイミングで一番下の値のキーの値を足していって答えを出します。

結論としては連想配列使うとこういうことができるよってことでした。