https://codeforces.com/contest/1936
총평: Div1, Div2가 동시에 열린 대회였습니다. 레이팅 1600~2100정도의 고수분들은 Div2를 보셨고, 레이팅 2100~의 초고수분들은 Div1을 보았습니다. 저는 레이팅이 2403이여서 Div1으로 신청하였고, 그래서 Div2의 쉬운 문제들은 풀이는 커녕 문제도 모릅니다... 그래서 Div1의 쉬운문제만 리뷰해보겠습니다.
Div1은 역시 어렵네요. 진짜 어렵네요;;;;;;;;;;;
A: p_0부터 시작해서, p_i | p_0가 max가 되는 p_i를 찾아봅시다.
대충 i=1부터 시작해서, (p_i | p_0) < (p_j | p_0)라면 i <- j를 해주면 됩니다. 여기까지 약 N-2번의 연산이 소요됩니다.
이제 이러한 i를 찾았으면, 다시 p_i | p_j가 max가 되는 p_j를 찾아봅시다. 위와 비슷하게 하면 똑같이 N-2번의 연산정도가 소요됩니다.
p_i | p_j는 이제 max가 되는데, 이값은 당연하지만 2^(k+1)-1꼴의 숫자가 됩니다. (2^k <= n을 만족하는 최대의 k에 대해서, 2^k와 2^k-1을 잡으면 이 둘의 XOR은 2^(k+1)-1이 되며, 최대입니다.) 이제 p_i | p_i , p_j | p_j 쿼리를 던져서 더 큰쪽을 찾아봅시다. p_i가 더 큰수라고 가정합시다.
p_i | p_k = max가 되는 p_k를 찾고, 이러한 p_k중에서 가장 작은 수를 골라봅시다. 역시 (p_k1 | p_k1), (p_k2 | p_k2) 쿼리를 던지면 어느 쪽이 더 큰지 작은지 알 수 있습니다.
이제 p_i XOR p_k = max가 됨을 보장할 수 있습니다.
총 연산수는 약 3N-1 ~ 3N-2정도로, 주어진 3N번의 쿼리연산 이내로 구할 수 있습니다.
B: 어렵습니다. ">"가 나오는 index, "<"가 나오는 index를 가지고 누적합을 만들어서, 각 위치마다 이분탐색을 적절하게 사용한 후 누적합으로 답을 계산해야합니다. 생각하기도 까다롭지만, 구현은 더까다롭습니다.
간단히 예제로 설명하겠습니다.
1번 예제의 경우 ><<인데 (1-indexed), 1번 위치에서 보면 ">"의 index는 0,1이 존재하며, "<"의 위치는 2,3이 존재합니다.
그러므로, 답은 (2-1) + (2-0) = 3입니다.
2번 위치에서 보면 ">"의 index는 0,1이 존재하며, "<"의 위치는 2,3이 존재합니다. 하지만 1번과 방향이 반대므로 더해지는 순서는 약간 달라집니다.
답은 (2-1) + (3-1) + (3-0) = 6입니다.
즉, 더해지는 순서를 보면 +되는 수의 경우 (처음 <위치 1번, 그 다음 <위치 2번, 그 다음 <위치 2번,...)이 됩니다.
-되는 수의 경우 (처음 >위치 2번, 다음 >위치 2번,.... 마지막 >위치 1번)이 됩니다.
이런식으로 왼쪽에서 끝나는지, 오른쪽에서 끝나는지, 방향은 >인지 <인지 잘 살펴보면서 누적합 잘 써서 계산해주면 됩니다.
빡세네요.
C: ?? 쉽습니다.
각 j(1<=j<=m)마다 정렬하여서, a_{i_1}j <= a_{i_2}j <= ... <= a_{i_n}j가 성립한다고 가정합시다.
그러면, 더미 노드 1~n번을 만들어서, i_k에서 i_(k+1)로 이동할 때, 더미 k -> 더미 k+1로 가는, weight a_i_(k+1)j - a_i_kj 간선을 만들어줍시다.
그리고, 각 k마다 i_k노드 -> 더미 k번 노드로 가는 weight 0인 간선을 만들고, 더미 k번 -> i_k 노드로 가는 weight c_i_k인 간선을 만들어줍시다.
이걸 모든 j에 대해서 하면 더미노드 약 nm개가 추가되어, 정점수 약 (n+1)m, 간선수 약 4(n+1)m개정도인 그래프가 만들어집니다.
여기서 1번노드 -> n번노드로 가는 최단거리를 구하면 됩니다. 당연하지만 다익스트라로 빠르게 구할 수 있습니다.
왜 이런게 Div1C에 있는지 모르겠네요. 어려운 문제긴 합니다만 Div1C에 있기엔 너무 쉽습니다. 실제로 20분컷했네요.
D: sqrt decomposition + 겁나 어려운 monoid 위에서 정의된 segment tree 적용해서 O(Nsqrt(N) + Qsqrt(N)logN)풀이를 짰는데 메모리가 너무 커서 틀렸습니다;;;
생각해보니 segment tree를 구현할 필요 없고 union-find로도 충분히 가능하고, 이 경우 메모리를 4배정도 아낄 수 있는데 너무 급박해서 생각해내지 못한게 아쉽습니다. 실제로 sqrt decompositino + union-find로 통과된분이 있다 하더군요.
진짜 아쉽습니다..... ㅠㅠㅠ
E: 분할정복 + FFT를 쓰면 될것처럼 보이는 문제고, 실제로 그랬다고 하지만, 시간이 없어서 문제 읽고 구현하지는 못했습니다.
F: 문제를 읽지도 않았습니다.
결과:
이야 대박났다ㅏㅏㅏㅏㅏㅏ 전체 64등! 퍼포먼스 2700대! 레이팅 약 100이 올라서 단번에 2499가 되었습니다 ㅎㅎㅎ
조금 아쉽기도 합니다. D 풀었으면 아마 세계 20등안에 들고 퍼포먼스 3000대도 찍을 수 있었을텐데 말이죠.
그래도 이정도로 대박난게 얼마만인가 싶네요
2600까지 101남았다.............