AOJ 0517 - Longest Steps

問題

問題概要

数字の連続した長さの最大値を求める問題。ただし与えられたクエリの中に、0があれば好きな数字に変えることができる。

解法

まず、与えられた数字をバケツソートしておく。前から順番に数字を見ていき、連続成分の大きさで最大ものを探す。その時に、クエリの中に0が含まれていたら、0を任意の数字に変えることができる。よって、隣接する連続部分増加列の間が1つしか空いていなければ、その間を0を利用して埋めることが可能になる。例えば増加列{123}と{56}があり、クエリの中に0が含まれていたら0を4にすることで、連続部分増加列が{123456}になる。よって、場合分けが必要になるのでそれに注意してやればいい。

ミス

特にない。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <set>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
 
int main(void){
    while(1){
        int n, k, ans = 0;
        cin >> n >> k;
        if(n == 0 && k == 0) break;//00が与えられたら終了
        bool flag = false;//クエリのなかに0があるかどうかを示すフラグ
        vector<bool> num(n + 1, false);//バケツソートをするための
        rep(i, k){
            int tmp; scanf("%d", &tmp);
            if(tmp == 0){
                flag = true;
                continue;
            }
            num[tmp] = true;//バケツソート
        }
        int pre = 0;//前回の連続増加列の数字の個数を入れておく
        int cnt = 0;//今見ている連続増加列の数字の個数をカウントするのに利用
        int now;
        int end = 0;//前回の連続部分増加列の最後の数字を入れておく
        bool rennketukanouseiflag = false;//隣接する連続増加列の間が1のときのみtrue
        reps(i, 1, n + 1){
            //数字iがある時
            if(num[i] == true){
                if(i == end + 2) rennketukanouseiflag = true;//前回の連続増加列との間が1
                cnt++;
            //数字iがないとき
            }else{
                now = cnt;//現在みている連続部分増加列の数字の個数
                //クエリ内に0が含まれていてかつ、隣接する連続部分列間が数字1つ分のときに限り、連続部分列どおしをくっつけれる
                if(flag == true && rennketukanouseiflag == true) ans = max(ans, pre + now + 1);
                //上の条件を満たせないときは、単に連続部分増加列の中で最大のものを探せばいい
                else ans = max(ans, now);
                
                // 初期化
                cnt = 0;
                rennketukanouseiflag = false;
                pre = now;//メモっておく
                end = i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}