A : 문자 x가 x-'A'+1번 이상 등장하면 답에 카운트


B : 5 4 3 2 1처럼 내림차순으로 배치해 두고 prefix k+1개를 sort


C : 각 prefix에 대해, 이 prefix에 속하는 i들만 모두 한 번 이상씩 사용하는 최대 점수를 구하기

sum(a[1..i]) + max(b[1..i]) * (k-i)이므로 prefix max, prefix sum만 관리하면 됨


D : a_x + b_y + c_z를 구할 때 x < y < z이도록 강제한 문제를 풀 수 있다면, (a,b,c)의 permutation 개수인 3! = 6번만큼 풀어 보면 됨

y를 고정했을 때 max(a_x + b_y + c_z) = max(a_x) + b_y + max(c_z)이므로 prefix max of a, suffix max of c를 전처리해 두면 해결 가능


E1 : n! backtracking


E2 : 선공이 최종 상태에서 i를 골랐다면 a_i - 1만큼의 이익을 얻고, 안 골랐다면 b_i - 1만큼의 손해를 얻음

따라서 골랐을 때와 안 골랐을 때는 서로 a_i - 1 + b_i - 1만큼의 점수 차이가 있음. 후공에게도 마찬가지

선공과 후공은 둘 다 a_i - 1 + b_i - 1이 큰 순으로 뽑는 전략을 채택해야 함


F : root를 기준으로 나뉘는 subtree들 중에 majority size가 없다면 모두 matching 가능

majority size subtree T가 존재한다면, T와 다른 subtree 간에서 최대한 matching해 주고 모자란 만큼은 T 내부에서 recursive하게 해결하기


G1 : 값 i의 왼쪽 등장을 L_i, 오른쪽 등장을 R_i라 정의하고 interval i를 [L_i, R_i]라 정의하자

i와 i+1을 모두 cover하는 interval이 없다면 두 구간 [1,i]와 [i+1,2N]은 서로 independent함

이러한 cut을 모두 찾으면 각 구간 내부에서 정확히 하나만 S에 포함하면 됨


이제 각 구간 [s,e]마다 초기에 선택할 수 있는 bulb의 개수를 구하면, 이들의 곱이 정답이 되는 경우의 수임

1. s는 초기에 선택 가능

2. same color 중 하나가 초기에 선택 가능하면, 나머지 하나도 가능

3. x가 초기에 선택 가능하고 L_i < x < R_i라면 L_i도 초기에 선택 가능

위 규칙에 따라 BFS를 하면 n^2


G2 : BFS를 할 때 3번 규칙에서 모든 i를 naive하게 순회하지 말자

L_i < x인 i들 중에 max(R_i)부터 차례대로 뽑으면서 x < R_i인 동안 queue에 L_i, R_i를 push하면 불필요한 i를 검사하지 않게 됨

max segment tree로 하면 nlogn