JOI 本選 2007 B - 最長の階段 (AOJ 0517) (2Q, 難易度 5)

とても色んな解法が考えられそうだ。

• 問題へのリンク

問題概要

以上 以下の 個の整数から相異なる 個の整数を選んで並べて得られる数列 が与えられる。

今、この数列の中に である要素があるならば、その要素を 1 以上 以下の好きな整数に書き換えてよい。

こうして得られた数列に対して、次の条件を満たす整数の組 をすべて考えたときの、 の値として考えられる最大値を答えよ。

「 以上 以下の任意の整数は、数列の中に含まれる」

制約

• 
• 

考えたこと

まず、与えられた数列 が 0 を含むならば、0 を除外しておくこととする。そして、数列 を「連続した整数の区間」に分解することにしよう。たとえば、

を考える。これは、3 つの連続する整数の区間 [1, 2, 3, 4], [6], [9, 10] に分解できる。

分解後

このように数列 を「連続する整数の区間」に分解したあとは、もとの数列 が 0 を含むかどうかで場合分けして、次のように解ける。

Case 1：数列 が 0 を含まないとき

この場合は簡単だ。単に上記の各区間の長さの最大値を求めれば良い。

Case 2：数列 が 0 を含むとき

この場合は次の 2 パターンを考慮しよう。

• 各区間について、その区間に整数を 1 つ付け加えることで、長さを 1 だけ増やした区間
• 隣接する区間について、その隙間に相当する整数が 1 個だけである場合に限り、0 をその値に書き換えて、その前後の区間を連結させてできる区間

これらの区間の長さの最大値を求めればよい。

コード

以上の解法は計算量が となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    deque<int> A(K);
    for (int i = 0; i < K; i++) cin >> A[i];
    sort(A.begin(), A.end());

    // A が 0 を含むかどうか（含むときは 0 を除外しておく）
    bool zero = (A[0] == 0);
    if (zero) A.pop_front();

    // A を「連続する整数からなる区間」に分解する
    vector<pair<int,int>> v;
    int left = A[0];
    for (int i = 1; i < K; i++) {
        if (A[i] - A[i-1] > 1) {
            v.emplace_back(left, A[i-1]);
            left = A[i];
        }
    }
    v.emplace_back(left, A.back());

    // 集計
    int res = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (zero) {
            // 単一区間の長さを 1 増やしたものも答えの候補（ただし N + 1 個以上にはならない）
            res = max(res, min(v[i].second - v[i].first + 1, N));

            // 0 があって、隣接する区間の間隔が 1 である場合は連結できる
            if (i > 0 && v[i].first - v[i-1].second == 2) {
                res = max(res, v[i].second - v[i-1].first + 1);
            }
        } else {
            res = max(res, v[i].second - v[i].first + 1);
        }
    }
    cout << res << endl;
}