Problem:


最長の階段  

問題

 1 から n までの整数がそれぞれ 1 つずつ書かれた n 枚のカードと,1 枚の白紙の
カードがある.これら n + 1 枚のカードの内,k 枚のカードが与えられる.ただし,
1 ≤ k ≤ n である.白紙のカードには 1 から n までの整数を 1 つ書くことができ
る.与えられたカードだけで,できるだけ長い連続した整数列を作りたい.

 与えられるカードが入力されたときに, 与えられたカードから作ることができる連
続した整数列の最大長を出力するプログラムを作成せよ.

例1

 n = 7, k = 5 とする.6, 2, 4, 7, 1 のカードが与えられたとき,このカードを使っ
て作れる連続した整数列のうち最長のものは 1, 2 であり,その長さは 2 である.

例2

 n = 7, k = 5 とする.6, 2, 4, 7 と白紙のカードが与えられたとき,このカードを
使って作れる連続した整数列のうち最長のものは,白紙のカードに 5 を書くことに
よってできる 4, 5, 6, 7 であり,その長さは 4 である.

入力

input.txt である.-->
入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロ２つを含む行で終了する．

  1 行目には,2 つの整数 n (1 ≤ n ≤ 100000) と k (1 ≤ k ≤ n) がこの順で 1 つの
空白を区切りとして書かれている.続く k 行には整数が 1 つずつ書かれており,与
えられる k 枚のカードに書かれている整数を表している.白紙のカードは 0 で表さ
れる.

  採点用データのうち, 配点の 40% 分は 1 ≤ n ≤ 1000, 1 ≤ k ≤ 500 を, 配点の 20% 分は 1 ≤ n ≤ 60000, 1 ≤ k ≤  50000 を. 配点の 40% 分は 1 ≤  n ≤  100000, 1 ≤ k ≤ 100000 を満たす.

データセットの数は 5 を超えない．

出力

output.txt である.
output.txt は 1 行だけからなり,その 1 行は出力する整数 1 つだけを含む.
-->
データセットごとに整数を1行に出力する．

入出力例

入力例

7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0

出力例

2
4

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
7 5
6
2
4
7
1
7 5
6
2
0
4
7
0 0


Sample output:
2
4

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N, K = [], []
C = []


def set_inputs():
    global N, K, C
    while True:
        n, k = get_li()
        if n == k == 0:
            break
        N.append(n)
        K.append(k)
        c = get_data(k, [int])
        C.append(c)
    return


def sgn(n):
    if n == 0:
        return 0
    if n > 0:
        return 1
    return -1


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    for n, k, c in zip(N, K, C):
        c.sort()
        ans = 0
        if c[0] == 0:
            tmp = 1
            for v1, v2 in zip(c[1:], c[2:]):
                if v2 - v1 == 1:
                    tmp += 1 * sgn(tmp)
                    if abs(tmp) > abs(ans):
                        ans = tmp
                elif v2 - v1 == 2:
                    if tmp > 0:
                        tmp = -tmp - 2
                    else:
                        tmp = -3
                else:
                    tmp = 1
            if ans > 0:
                ans += 1
            ans = abs(ans)
        else:
            tmp = 1
            for v1, v2 in zip(c, c[1:]):
                if v2 - v1 == 1:
                    tmp += 1
                    ans = max(ans, tmp)
                else:
                    tmp = 1
        print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,K = map(int,raw_input().split())
    A = sorted([int(rraw_input()) for i in range(0,K)])

    if (N,K) == (0,0):
        break

    if A[0] == 0:
        flag = True
        A = A[1:]
        K -= 1
    else:
        flag = False

    diff = []
    ans = 0
    prev = 0
    prev_prev = 0
    count = 0
    for i in range(1,K):
        if A[i] - A[i-1] == 1:
            count += 1
            ans = max(ans,count-prev_prev)
        elif A[i] - A[i-1] == 2:
            if flag is True:
                count += 1
                ans = max(ans,count-prev_prev)
                prev_prev = prev
                prev = count - prev
            else:
                count = 0
        else:
            count = 0
    print(ans + A[0])

Submission status: Runtime Error

Solution code:
# AOJ 0517: Longest Steps
# Python3 2018.6.30 bal4u

while True:
	n, k = map(int, input().split())
	if n == 0: break
	c = [0]*(n+1)
	f = 0;
	for i in range(k):
		a = int(input())
		if a == 0: f = 1
		else: c[a] = 1
	ans = w0 = w = 0
	for i in range(1, n+1):
		if c[i]: w += 1
		elif w > 0:
			if w0 + w + f > ans: ans = w0 + w + f
			w0 = w if f and c[i+1] else 0
			w = 0
	if w0 + w + f > ans: ans = w0 + w + f
	print(ans)

Submission status: Runtime Error

Solution code:
while 1:
	n,k = map(int,raw_input().split())
	if n == 0: break
	s = [0]*(n+1)
	c = sorted([int(raw_input()) for i in range(k)])
	p = min(0,C[0])
	pre = 0
	for i in c[p:]:
		s[i] = s[i-1] + 1
		if p and s[i-1] == 0:
			if s[i-2]:
				s[i] += s[i-2] + 1 - pre
				pre = s[i-2] + 1
			if s[i-2] == 0:
				pre = 0
	print max(s)