結果

問題 No.1827 最長部分スーパーリッチ門松列列
コンテスト
ユーザー mai
提出日時 2026-01-31 16:48:31
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 2,718 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 839 ms
コンパイル使用メモリ 95,268 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-31 16:48:36
合計ジャッジ時間 4,159 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Gemimi 3 Pro preview

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 各テストケースを解く関数
void solve() {
    int N;
    if (!(cin >> N)) return;

    // 順列 P の入力
    vector<int> P(N);
    // 値 x が配列 P のどのインデックスにあるかを記録する配列
    vector<int> pos(N + 1);

    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        pos[P[i]] = i;
    }

    // current_k: 現在の境界の数（隣り合う要素の High/Low が異なる箇所の数）
    // max_k: 境界の数の最大値
    int current_k = 0;
    int max_k = 0;

    // V を 1 から N まで変化させていくシミュレーション
    // 初期状態 (V=0) では全員 High (1) なので境界は 0 個
    // ループの各ステップ x では、値 x が High(1) から Low(0) に変化する
    for (int x = 1; x <= N; ++x) {
        int i = pos[x]; // 値 x のインデックス

        // 左隣 (P[i-1]) との関係を更新
        if (i > 0) {
            // P[i-1] < x ならば、P[i-1] はすでに Low(0) になっている
            // P[i-1] > x ならば、P[i-1] はまだ High(1) である
            
            if (P[i - 1] < x) {
                // 左隣は 0。自分は 1 -> 0 になる。
                // 以前の状態: 0(左) - 1(自分) -> 境界あり
                // 新しい状態: 0(左) - 0(自分) -> 境界なし
                current_k--;
            } else {
                // 左隣は 1。自分は 1 -> 0 になる。
                // 以前の状態: 1(左) - 1(自分) -> 境界なし
                // 新しい状態: 1(左) - 0(自分) -> 境界あり
                current_k++;
            }
        }

        // 右隣 (P[i+1]) との関係を更新
        if (i < N - 1) {
            if (P[i + 1] < x) {
                // 右隣は 0。自分は 1 -> 0 になる。
                // 以前: 1 - 0 -> 境界あり
                // 新規: 0 - 0 -> 境界なし
                current_k--;
            } else {
                // 右隣は 1。自分は 1 -> 0 になる。
                // 以前: 1 - 1 -> 境界なし
                // 新規: 0 - 1 -> 境界あり
                current_k++;
            }
        }

        // 最大値を更新
        if (current_k > max_k) {
            max_k = current_k;
        }
    }

    // 答えは (境界の最大数 + 1)
    // ※ブロックの数 = 境界の数 + 1
    cout << max_k + 1 << "\n";
}

int main() {
    // 高速化設定
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}
0