Codeforces Round #344 (Div. 2)

• 
• virtual participation.. 어렵지 않은 구현문제들이었다.
  
• A : \(O(n^2)\)
• B : \(O((M+N)^2)\). 중복쿼리를 합치고 직접 칠하면 된다.
• C : 문제를 개념화하면서 range sort라고 이해했고 이러면서 range query도 힘든데 소트를 하라니 멘붕이 오면서 시작점이 zero로 고정되어 있다는 사실을 까먹었다-_- 그래서 D로 일단 넘어간 다음 다시 돌아와서 풀었음. 중요한 observation은, 쿼리당 이후에 자기보다 긴 쿼리가 나오면 쓸모가 없어진다는 것.. 일단 이렇게 내림차순의 쿼리꼴을 만들어 준 후에, deque로 element를 빼주면서 답을 만든다. 그렇게 어렵지 않은 문제였는데 역시 제약을 파악하는 것은 중요함-_-
• D : KMP를 써서 풀었다. 패턴을 정규화하고 나면 두 가지 경우로 나눠서 풀 수 있다. (1) 문자열 s의 패턴길이가 1인 경우, 각각 t에서 패턴 대응 한 개당 여러 개의 답이 더해질 수 있다. (2) 그게 아니라면 그냥 문자열 비교하듯 매칭 하나당 답이 하나만 나오게 되는데, 여기서 문자를 <'a',8>과 같은 pair요소로 보고 문자열 비교를 수행했다. 그런데 문자열 s의 시작과 끝은 대응되는 t의 개수보다 작아도 되므로, 특수처리해줘서 매칭될 때마다 조건을 따졌다.
• E : 답을 수식으로 나타내면, 초기상태에서 \( \max( \max_{i<j} (a_i*j - p_j)-(a_i*i-p_i), \max_{j<i} (a_i*j - p_{j-1}) - (a_i*i - p_{i-1} ) )\)만큼을 더한 것이 정답이 된다. 두 가지 경우로 나눴는데, 이는 숫자를 선택해서 뒤로 보내느냐 앞으로 보내느냐의 차이가 있다. 이제 겹치는 꼴인 \( x*i - p_i = f_i(x) \)를 1차함수로 삼고 \(x=a_i\)에서의 최댓값을 찾는 문제로 변환시킬 수 있고, 이는 convex hull optimization으로 \(O(n\log n)\)구현이 가능하다.
• PEGWiki에서 설명을 읽고, fully dynamic한 자료구조를 구현했는데, 소스가 굉장히 더럽다^_ㅠ iterator의 사용을 좀 더 깔끔하게 해야 할 듯...