PythonでJOI難易度5を埋める #2
考えたこと
白紙のカードが無い場合は連続した部分の最大を考える問題。
白紙のカードが入っている場合は入っていない場合を少し拡張して、[連続部分の長さ、連続部分列の最初の要素、連続部分列の最後の要素]を記録するlistを作って考える。白紙のカードは、「あと一枚で連続になる場所に挿入したい」ので、連続部分列の最初の要素と最後の要素を記録することで、後からどこに入れるのが最適かを確認している。あと一枚で連続になる場所は、今の連続部分列の最後の要素-次の連続部分列の最初の要素 = 2になる場所なので、そこを見つけてansを更新している。
n, k = map(int,input().split()) cards = [int(input()) for _ in range(k)] cards.sort() if cards[0] != 0: ans = 0 con = 1 for i in range(k-1): if cards[i+1] - cards[i] == 1: con += 1 else: ans = max(ans,con) con = 1 else: ans = max(ans,con) print(ans) else: ans = 0 con = 1 cards.pop(0) v = [] #start = 0 for i in range(k-2): if con == 1: start = cards[i] if cards[i+1] - cards[i] == 1: con += 1 else: v.append([con, start, cards[i]]) con = 1 else: v.append([con,start,cards[i+1]]) #print(v) for i in range(len(v)-1): if v[i+1][1] - v[i][2] == 2: ans = max(ans,v[i][0]+v[i+1][0]+1) print(ans)