問題1：交互配列の最長連結区間

与えられた 0-1 列において、隣接要素が交互に変化する（例：01010）最大長の連続部分列を求める。ただし、1つの「交互セグメント」を反転することで、より長い連続交互列を得られる可能性がある。

まず、入力列を交互性に基づいて分割し、各セグメントの左右端点を記録。その後、隣接する3つのセグメント（左・中・右）を結合した長さを評価。特に、中央セグメントを反転すると、左と右のセグメントと連続して交互列を形成できる場合がある。全セグメント数が2以下なら、全体が交互列または1回の反転で完全に整列可能であるため、答えは全長となる。

struct Segment {
    int start, end;
    Segment(int s = 0, int e = 0) : start(s), end(e) {}
};
int n, segCount = 0, maxLen = 0;
int arr[200005];
Segment segments[200005];

void solveProblem1() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
    
    for (int i = 1; i <= n; ) {
        int j = i;
        while (j < n && arr[j + 1] == 1 - arr[j]) ++j;
        segments[++segCount] = Segment(i, j);
        maxLen = std::max(maxLen, j - i + 1);
        i = j + 1;
    }
    
    if (segCount <= 2) {
        printf("%d\n", n);
        return;
    }
    
    for (int i = 2; i < segCount; ++i) {
        int combined = segments[i + 1].end - segments[i - 1].start + 1;
        maxLen = std::max(maxLen, combined);
    }
    printf("%d\n", maxLen);
}

問題2：文字列マッチングの動的計画法

2つの文字列 S と T が与えられ、それぞれから部分列を取って「I」と「O」を交互に並べた最長共通部分列（ただし先頭は I）の長さを求める。状態 dp[i][j][k] を、S の i 文字目までと T の j 文字目までを用いて、末尾が k（0: O 終端、1: I 終端）の最長有効列の長さとする。

遷移は、現在の文字が 'I' なら I 終端列を延長、'O' なら直前の I 終端列から O を付加して O 終端列を生成する。初期化と境界条件に注意し、最終的にすべての dp[i][j][1] の最大値を返す。

int n, m;
char S[1005], T[1005];
int dp[1005][1005][2];

void solveProblem2() {
    scanf("%d%d%s%s", &n, &m, S + 1, T + 1);
    for (int i = 1; i <= n; ++i) S[i] -= 'A';
    for (int i = 1; i <= m; ++i) T[i] -= 'A';
    
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            if (i > 0 && S[i] == 8) // 'I' → ASCII 73 → 8 after '-A'
                dp[i][j][1] = std::max(dp[i][j][1], dp[i-1][j][0] + 1);
            if (j > 0 && T[j] == 8)
                dp[i][j][1] = std::max(dp[i][j][1], dp[i][j-1][0] + 1);
            if (i > 0 && S[i] != 8 && dp[i-1][j][1])
                dp[i][j][0] = std::max(dp[i][j][0], dp[i-1][j][1] + 1);
            if (j > 0 && T[j] != 8 && dp[i][j-1][1])
                dp[i][j][0] = std::max(dp[i][j][0], dp[i][j-1][1] + 1);
        }
    
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ans = std::max(ans, dp[i][j][1]);
    printf("%d\n", ans);
}

問題3：双方向グラフ上の最短経路

グリッド上の移動において、特定の「スイッチ座標」では東西・南北の移動モードを切り替えられる。この制約下での (1,1) から (N,M) への最短距離を求める。

キーとなるのは、スイッチ座標および始終点のみが意味を持つこと。これらをノードとして、東西移動専用グラフと南北移動専用グラフの2つを構築し、スイッチ点では両グラフ間の重み1の辺を張る。各方向グラフ内では、同一行（列）上のノードを y（x）座標順にソートし、隣接ノード間に距離に応じた辺を追加。最終的にダイクストラ法で最短距離を計算する。

struct Node { int id; long long dist; };
bool operator<(const Node& a, const Node& b) { return a.dist > b.dist; }

std::vector> graph[400005];
long long dist[400005];
int coords[400005][3]; // x, y, type(0=normal,1=switch)
int nodeCount = 0, startX = -1, startY = -1, endX = -1, endY = -1;

void solveProblem3() {
    int N, M, K;
    scanf("%d%d%d", &N, &M, &K);
    
    auto addNode = [&](int x, int y, int t) {
        coords[++nodeCount][0] = x;
        coords[nodeCount][1] = y;
        coords[nodeCount][2] = t;
        if (x == 1 && y == 1) startX = nodeCount;
        if (x == N && y == M) endX = nodeCount;
        return nodeCount;
    };
    
    for (int i = 0; i < K; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        int a = addNode(x, y, 0);
        int b = addNode(x, y, 1);
        graph[a].emplace_back(b, 1LL);
        graph[b].emplace_back(a, 1LL);
    }
    
    if (startX == -1) startX = addNode(1, 1, 0);
    if (endX == -1) endX = addNode(N, M, 0);
    
    std::vector<int> rows[N+1], cols[M+1];
    for (int i = 1; i <= nodeCount; ++i) {
        int x = coords[i][0], y = coords[i][1], t = coords[i][2];
        if (t == 0) rows[x].push_back(i);
        else cols[y].push_back(i);
    }
    
    for (int x = 1; x <= N; ++x) {
        std::sort(rows[x].begin(), rows[x].end(), [&](int a, int b) {
            return coords[a][1] < coords[b][1];
        });
        for (size_t j = 1; j < rows[x].size(); ++j) {
            int u = rows[x][j-1], v = rows[x][j];
            long long d = coords[v][1] - coords[u][1];
            graph[u].emplace_back(v, d);
            graph[v].emplace_back(u, d);
        }
    }
    
    for (int y = 1; y <= M; ++y) {
        std::sort(cols[y].begin(), cols[y].end(), [&](int a, int b) {
            return coords[a][0] < coords[b][0];
        });
        for (size_t j = 1; j < cols[y].size(); ++j) {
            int u = cols[y][j-1], v = cols[y][j];
            long long d = coords[v][0] - coords[u][0];
            graph[u].emplace_back(v, d);
            graph[v].emplace_back(u, d);
        }
    }
    
    std::priority_queue<Node> pq;
    std::fill(dist + 1, dist + nodeCount + 1, LLONG_MAX);
    dist[startX] = 0;
    pq.push({startX, 0});
    
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if (cur.dist != dist[cur.id]) continue;
        for (auto& edge : graph[cur.id]) {
            int nxt = edge.first;
            long long nd = cur.dist + edge.second;
            if (nd < dist[nxt]) {
                dist[nxt] = nd;
                pq.push({nxt, nd});
            }
        }
    }
    
    long long ans = std::min(dist[endX], dist[endX]); // simplified for illustration
    printf("%lld\n", ans == LLONG_MAX ? -1LL : ans);
}

問題4：文字列 JOI と IOI の最大出現回数

文字列から可能な限り多くの「JOI」または「IOI」を非重複で抽出する。これらは共に「OI」を共有するため、まず最適な「OI」ペアを後方から貪欲に決定し、残りの文字で「J」または「I」（先頭）を補完する。

二分探索で実現可能数 k を検証：まず後方から「OI」を k 個取り、その位置をマーク。次に、残った未使用位置で「J」または「I」をスタックのように「OI」の「O」に対応付けてマッチング。スタックが空になれば k は達成可能。

char str[300005];
int stack[300005], top;
bool used[300005];

bool feasible(int k, int len) {
    top = 0;
    int found = 0;
    std::memset(used, 0, sizeof used);
    
    for (int i = len; i >= 1; --i) {
        if (str[i] == 'I') stack[++top] = i;
        else if (str[i] == 'O' && top > 0) {
            used[i] = true;
            used[stack[top--]] = true;
            if (++found == k) break;
        }
    }
    if (found < k) return false;
    
    top = 0;
    for (int i = len; i >= 1; --i) {
        if (used[i]) continue;
        if (str[i] == 'I' || str[i] == 'J') {
            if (top > 0) --top;
        } else if (str[i] == 'O') {
            stack[++top] = i;
        }
    }
    return top == 0;
}

void solveProblem4() {
    int n;
    scanf("%d%s", &n, str + 1);
    int lo = 0, hi = n / 3, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (feasible(mid, n)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    printf("%d\n", ans);
}

問題5：バブルソートにおける逆転数最小化

数列の隣接要素を1回だけ交換して、全体の逆転数を最小化する。交換後の逆転数減少量は、交換される2要素を頂点とする矩形領域内の点の配置に依存する。

重要な観察：最適な交換の左端点は自身が左側最大値、右端点は右側最小値である必要がある。これを満たす候補を前処理で列挙し、それらを軸に平面走査を行う。各候補ペアについて、交換による逆転数削減量を、矩形内の点数と境界上の点数から計算。イベントベースのスキャンラインとセグメント木を用いて、O(n log n) で最大削減量を求める。

int n, a[200005], leftCandidates[200005], rightCandidates[200005];
long long totalInversions = 0;
std::vector> events; // (x, l, r)

void solveProblem5() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    
    // 全体の逆転数を計算
    FenwickTree ft;
    ft.init(n);
    for (int i = n; i >= 1; --i) {
        totalInversions += ft.query(a[i] - 1);
        ft.update(a[i], 1);
    }
    
    if (totalInversions == 0) {
        printf("0\n");
        return;
    }
    
    // 候補点列挙
    int lc = 0, rc = 0;
    int maxSoFar = 0, minSoFar = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (a[i] > maxSoFar) {
            maxSoFar = a[i];
            leftCandidates[++lc] = i;
        }
    }
    for (int i = n; i >= 1; --i) {
        if (a[i] < minSoFar) {
            minSoFar = a[i];
            rightCandidates[++rc] = i;
        }
    }
    
    // イベント生成（省略詳細）
    // ...
    
    // セグメント木で最大値取得
    SegmentTree st;
    st.init(rc);
    for (auto& [x, l, r] : events) {
        st.rangeAdd(l, r, 1);
        long long curMax = st.getMax();
        // ...
    }
    
    printf("%lld\n", totalInversions - bestReduction - 1);
}