AtCoder Regular Contest 014 C - 魂の還る場所

競技プログラミング

問題

　円筒の左右から赤緑青の3色のいずれかで塗られているボールを入れていく。ボールは同じ色のボールと接触すると消えるという性質を持つ。左右どちらから入れるかは任意であり、ボールを入れる順番だけが与えられるとき、最終的に円筒内に残る最小のボール数を求めよ。

解法

　枝刈り全探索。消せるときは消したほうがいいので、dequeのfrontとbackを見て同じ色があったら消す。なかったら右からと左から2通り試す。

　非公式解説PDFを見たところ、1手先読みを行わなければTLEとなると書いてあるが、僕はメモ化による高速化でACとなった。また別解として各色のボールを2で割った余りの和が答えとなるらしい。おそらくそれが想定解なのだろう。

反省

　50分9秒でAC。パッと見では半分全列挙が頭に浮かび、それに囚われた考察をしていた。25分ごろに枝刈り全探索でそこそこいけるんじゃないかと思って書き始めるがTLE。メモ化をすれば間に合いそうだと考えて実装したところ、一つのケースだけがMLEとなった。MLEは珍しいし、一つのケースだけということもあって、想定解なのかどうかが迷うところだった。

　いろいろ試行錯誤した結果、最終的にはメモ化をする際のmapのキーをtuple<int i, deque<char>>からちょっと加工してstringに変えるとACとなった。メモリの使用効率が異なるのだろうか……？

　試しに

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    string s = "1RGBRGBRGBRGBRGB";
    deque<char> dq;
    for (ll i = 1; i < s.size(); i++) {
        dq.push_back(s[i]);
    }
    auto t = make_tuple((ll)1, dq);

    cout << sizeof(s) << endl;
    cout << sizeof(t) << endl;
}

　というコードを試したみたところ、出力は40 48だった。確かにstringにした方がわずかに消費量は小さい？ しかしこのsのRGBという文字を増やしてもメモリ使用量は変わらないためsizeofが何を評価しているのかよくわからない。またAtCoderでの結果を見ると、メモリ使用量が大きいところではstringにした方が1/5ほどになっている。C++の理解が浅すぎて何が起こっているのかさっぱりわからない……。

　またusing ll = long longと定義してある部分をusing ll = intとしてもメモリ使用量は全く変わらなかった。using ll = int16_tとしても変わらなかったが、理由がわからない。少ししか変わらないとかならわかるが、まったく変わらないものなのだろうか。

　メモ化するときにこうやって適用にmapに詰め込んでしまえーというのをよくやるので、メモリ使用量の変化は理解しておきたいところなんだけど……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int16_t;

ll N;
string S;
map<string, pair<bool, ll>> memo;

ll solve(ll i, deque<char> dq) {
    if (i == N) {
        return dq.size();
    }

    string key;
    key += to_string(i);
    for (char c : dq) {
        key += c;
    }

    if (memo[key].first) {
        return memo[key].second;
    }
    memo[key].first = true;

    char curr = S[i];
    ll ans = 50;
    if (dq.size() == 0) {
        dq.push_back(curr);
        ans = min(ans, solve(i + 1, dq));
    } else if (dq.front() == curr) {
        //先頭に入れる(結果消える)
        dq.pop_front();
        ans = min(ans, solve(i + 1, dq));
    } else if (dq.back() == curr) {
        //末尾に入れる(結果消える)
        dq.pop_back();
        ans = min(ans, solve(i + 1, dq));
    } else {
        //2通り試す
        auto dq1 = dq;
        dq1.push_front(curr);
        ans = min(ans, solve(i + 1, dq1));

        auto dq2 = dq;
        dq2.push_back(curr);
        ll ans2 = solve(i + 1, dq2);
        ans = min(ans, solve(i + 1, dq2));
    }

    return memo[key].second = ans;
}

int main() {
    cin >> N >> S;
    cout << solve(0, deque<char>()) << endl;
}