Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)

https://codeforces.com/contest/2062

 

 

최근 연속으로 레드 퍼포를 내면서, 벽처럼 느껴졌던 찐렌지 달성에 성공했다. 조금 더 해봐야 알겠지만 이제야 뭔가 혈이 뚫린 것 같아 행복하다. 자세한 이야기는 레드를 달성하면.. 풀어보고 싶다.

 

Prob. A

1의 개수는 최대 1씩 줄어드니 부분 수열의 길이를 그냥 1로 잡으면 된다.

 

Prob. B

손으로 수열을 여러 개 쓰고 직접 해보면서 규칙을 찾았다. 결국 양옆으로 왔다 갔다를 할 수 있으면 된다.

 

Prob. C

수열을 여러 번 뒤집어도 바뀌는 건 결국 전체의 부호밖에 없다. 그러니 다 만들어보고 절댓값의 최댓값을 구하면 된다. int를 넘어갈 거란 생각을 못 해서 한 번 틀렸다.

 

Prob. D

그냥 1을 루트로 잡고 트리 디피를 하면서 $a_i$의 값은 자식들 중 최대로, 더해지는 값은 잘 계산하면 된다. 관찰이 많이 필요해서 설명하기 귀찮다.

 

Prob. E1

한 노드를 지울 때 그 노드보다 값이 큰 노드들이 모두 서브트리 내에 있다면 그건 지는 상황이다. 값이 큰 것부터 보면서 처음으로 그렇지 않은 노드가 나온다면 그건 지웠을 때 무조건 이긴다.