[Medium] LongestSequence

길이 k인 수열을 만들 수 있으면 길이가 k 이하인 수열도 당연히 만들 수 있다. 맨 뒤에서 임의로 수를 제거해도 여전히 조건을 만족하기 때문이다. 이를 통해 파라메트릭 서치를 돌리는 방법을 생각해볼 수 있다. 길이 k인 수열을 만들 수 있는가? 라는 문제는 어떻게 풀까? S[i] = sum( a[1] ~ a[i] ) 라고 해보자. (누적합) 그럼 문제에서 주어진 조건을 다음과 같이 바꿔쓸 수 있다. C[p] > 0 인 애들에 대해서는 S[i+C[p]] - S[i] > 0 따라서 S[i+C[p]] > S[i] 이어야 하고 C[p] < 0 인 애들에 대해서는 S[i-C[p]] - S[i] < 0 따라서 S[i-C[p]] < S[i] 이어야 한다. S[a] < S[b] 인 부등식이 있을 때, a -> b 인 간선을 만든 그래프를 생각해보자. a -> b -> c -> ... -> e -> a 인 경로(=사이클)가 있다면 모순이다. 모든 부등식 관계를 만족하도록 S를 정할 수 없다. 사이클이 없다면, 모든 부등식 관계를 만족하도록 S를 정할 수 있고, 그에 따라 수열 a의 값도 정할 수 있다. 따라서 그래프를 만들고 사이클이 있는지 없는지 체크해주면 된다. 여기서 만들게 되는 그래프는 특이하게 생긴 그래프다. 어떤 사이클이 있다면 그것과 똑같은 길이,형태를 가지면서 0번 정점을 지나는 사이클도 항상 존재한다. (수열에서 사이클을 그려보면 그걸 왼쪽으로 shift한 형태의 사이클도 존재하기 때문) 그래서 0번 정점에서 출발하는 bfs만 한번 돌려줘도 체크할 수 있다. 이제 답의 상한은 대충 어느정도일지 가늠하는 일만 남았다. 우선, C의 모든 원소가 양수이거나 모든 원소가 음수라면 수열을 무한히 길게 만들 수 있으므로 답은 -1 이다. 그게 아니라면 답은 |C[i]| + |C[j]| - 1 미만이어야 한다. (C[i] > 0 && C[j] < 0 인 경우) 예를 들어 C = { -3, 4 } 라고 해보자. a[1] , a[2] , a[3] a[2] , a[3] , a[4] a[3] , a[4] , a[5] a[4] , a[5] , a[6] 각 행의 원소들의 합은 음수여야 한다. 각 열의 원소들의 합은 양수여야 한다. 이것은 모순이다. 따라서 원소는 6개 보다 작아야 한다...