(考察)ARC-014-C-魂の還る場所

問題URL→http://arc014.contest.atcoder.jp/tasks/arc014_3

面白い問題だった。
各色のボールの個数の偶奇だけで求まるようだが、自分は次の考察をした。

ボールを入れるとき消せるのであれば消せるほうに入れるべき。
例:RGBにBを加えるとき、右から加える

現在の筒の中の文字列の両端の文字の種類数について
RGRのように両端の文字の種類が1種類であるはずがない。なぜなら一つ前に消すことが可能だから。

ということは両端の文字の種類数は2種類(RGB、BGRなど)
筒の中の文字列がRGBだとする。
次に入れるのはR、G、Bのどれかだが、このうち二つ(RとB)の入れ方は自明。(消えるほうに入れれば良い)
問題はGの場合
入れるGの次の色について場合わけをする
GRのときGを右に入れれば次にRを消すことが出来るのでGを右に入れる
GBのときも同様に考えて左に入れる
GGのときはどちらに入れても次にGを消すことが可能

実装は初めてdequeを使った。

#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define MOD 1000000007
#define int long long
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
using namespace std;
typedef long long ll;
const int INF = 1e9;

int N;
string S;

signed main()
{
    cin >> N;
    cin >> S;

    deque<char> deq;
    REP(i,N) {
        if (deq.empty()) {
            deq.push_back(S[i]);
        } else if (deq.front() == S[i]) {
            deq.pop_front();
        } else if (deq.back() == S[i]) {
            deq.pop_back();
        } else {
            if (i == N - 1) {
                deq.push_back(S[i]);
            } else {
                if (S[i+1] == deq.front()) {
                    deq.push_back(S[i]);
                } else if (S[i+1] == deq.back()) {
                    deq.push_front(S[i]);
                } else {
                    deq.push_back(S[i]);
                }
            }
        }
    }

    cout << deq.size() << endl;
}