JOIOIの塔

嘘解法かも。

まず考察する。
とにかく2パターンの使い方ができるIが面倒。
仮に、IOIが爆破されたら(使用できるのがJOIだけだったら)ハジから貪欲にほいほいつくればいい。
なので、文字列中のIを何文字かJに変換し、貪欲に取るという事を考える。
Iの何文字かの選び方が2^n通りなので、O(n2^n)で解ける。
だが、すべてのIの選び方について考えなくても、左側から何文字かIを選ぶという選び方だけ考えれば良い。
最適解において、(3文字目としてつかうI)が(1文字目としてつかうI)より左側に来ることがないようにできるから。(そのようなIのペアがあったらswapすればいい)
だからその何文字かを全パターン試せばおしまい。

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdio>
#include <tuple>
#include <cstring>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MN = 1100100;
int d[MN][2];
int r[MN][3];
int main() {
    int n;
    string s;
    cin >> n >> s;
    d[0][0] = d[0][1] = 0;
    for (int i = 0; i < n; i++) {
        d[i+1][0] = d[i][0];
        d[i+1][1] = d[i][1];
        if (s[i] == 'J' || s[i] == 'I') {
            d[i+1][0]++;
        } else {
            if (d[i+1][0]) {
                d[i+1][0]--;
                d[i+1][1]++;
            }
        }
    }
    r[n][0] = r[n][1] = r[n][2] = 0;
    for (int i = n-1; i >= 0; i--) {
        r[i][0] = r[i+1][0];
        r[i][1] = r[i+1][1];
        r[i][2] = r[i+1][2];
        if (s[i] == 'J') {
            if (r[i][1]) {
                r[i][1]--;
                r[i][2]++;
            }
        } else if (s[i] == 'O') {
            if (r[i][0]) {
                r[i][0]--;
                r[i][1]++;
            }
        } else {
            r[i][0]++;
        }
    }
    for (int i = 0; i <= n; i++) {
//        printf("d %d 1:%d 2:%d\n", i, d[i][0], d[i][1]);
    }
    for (int i = 0; i <= n; i++) {
//        printf("r %d 1:%d 2:%d 3:%d\n", i, r[i][0], r[i][1], r[i][2]);
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
        int u = r[i][2];
        int w = min(d[i][0], r[i][1]);
        u += w;
        d[i][0] -= w;
        r[i][1] -= w;
        w = min(d[i][1], r[i][0]);
        u += w;
        d[i][1] -= w;
        r[i][0] -= w;
        u += min(d[i][1], r[i][1]);
        res = max(res, u);
        //printf("%d %d\n", i, u);
    }
    cout << res << endl;
    return 0;
}