#800 div2 6/30 virtual

https://codeforces.com/contest/1694

 

A만 풀고 나머지 업솔빙 왜 그런지 엄청 어려웠는데 업솔빙할때는 바로바로 생각남 

 

A 

1은 +1 0은 -1 

모든 prefix sum의 합의 절대값이 최소가 되도록 -> 번갈아가면서 나오도록 한다.

 

B

10 은 0이되고

01은 1이된다. 

 

string이 주어지고 sub string의 길이를 1로 만드는 모든 경우의 수

 

operation을 왼쪽꺼 삭제로 생각해보자 

*****01 꼴이면 무조건 1의 index만큼 가능

******10 꼴이면 무조건 0의 index만큼 가능

 

왜냐면 ******0은 *****10 또는 *****00 인데 

001은 01로 

101도 01로 가능

 

C

오른쪽으로 가면 +1 왼쪽으로 가면 -1 

각 값이 의미하는 내용은 = 오른쪽 이동 횟수 - 왼쪽 이동 횟수

 

맨 끝에서 오른쪽으로 갈 수는 없으니 그걸 기저로 잡고 시작

이게 맨 뒤부터 차례대로 말이 되는지 확인한다. 

 

D

트리가 주어지고, 각 vertex마다 주어진 범위의 값을 가져야 한다. 

모든 vertex는 0부터 시작

 

루트부터 어떤 노드까지 이동할 때 이동 순서에 맞춰서 비내림차순으로 임의의 값들을 생성해서 더할 수 있다. 

 

             a

      b     c    d

 

꼴의 트리가 존재할 때 a은 b, c, d 의 합을 넘을 수 없다 

 

a1+a2+a3 <= b+c+d 

a1<=b, a2 <= c, a3 <= d이므로 

 

이걸 이용하면 dfs 돌려서 a의 최솟값이 b+c+d보다 작거나 같은지 

다시 말해 b+c+d로 a를 채울 수 있는지 계산한다. 

못 채우면 +1 max(a)로 넘기고,  채울 수 있으면 min(b+c+d, max(a))로 넘겨줌