ゆらのふなびと

競プロ, Python, C++

Codeforces Round #333 (Div. 2) B. Approximating a Constant Range

問題

Problem - B - Codeforces

与えられる整数列のうち、次の条件を満たす部分列の最長の長さを求める。

  • 条件: 最大値 - 最小値 = 1

ただし、与えられる数列はどの隣り合う数も差が1以下である。

解法

しゃくとり法の問題。隣り合う数の差がもともと1以下なので、条件は「部分列に含まれる数が2種類以下」と同値。よって蟻本p.137のこの問題と同様に、数の出現数を記録しながらしゃくとりすればよい。

MAX_N = 100000
n = input()
a = map(int, raw_input().split())
i, j, num = 0, 0, 0
ans = 0
cnt = [0 for _ in xrange(MAX_N + 1)]
while True:
    while j < n and num <= 2:
        if cnt[a[j]] == 0:
            #new number appeared
            num += 1
        cnt[a[j]] += 1
        j += 1
        
    if num == 0:
        break
    
    if num == 3:
        ans = max(ans, j-i-1)
    else:
        ans = max(ans, j-i)
    cnt[a[i]] -= 1
    if cnt[a[i]] == 0:
        #one number dissappeared
        num -= 1
    i += 1
print ans

これで一応通ったんだけど、if num == 3 のあたりもうちょっときれいに書けないのかなあ、という感じ。