요즘 특징이, 풀 문제는 다 푸는데 앞에서 이상한 문제에서 시간 끌리거나 몇 번 틀려서 동 솔브자 대비 순위가 낮다는 것이다. 앳코더는 그래도 푼 시간의 max라 그 영향이 적은 반면 코포는 누적이라 그 영향이 크다. 이번 대회로 2231점이 되었고, IM이 눈앞이다. 2400을 향해...
https://codeforces.com/contest/1621
A
$(1, 1), (3, 3), \cdots $ 순서대로 배치하면 된다. $k>\frac{n+1}{2}$면 불가능
B
결국 양 끝점만 중요하다. 하나의 구간에 대한 최대구간과 그 최소비용, 가장 왼쪽 점이 포함된 구간과 최소비용, 가장 오른쪽 점이 포함왼 구간과 최소비용을 적당히 관리하며 답을 출력하면 된다.
C
결국 어떤 자리에 대해 숫자들은 어떤 사이클을 이루며 순환한다. 이 때 $x_1,x_2,\cdots,x_k,x_1$순으로 사이클을 이룰 때 $p_{x_i}=x_{i+1}, x_{k+1} =x_1$임이 당연하다. 아직 $p$값을 모르는 자리에서 두 번 질문하고, 각각 $x, y$라 할 때 $y$가 $x$가 아닐 때까지 계속 질문하고 바꿔주며 $p$를 채워주면 된다.
여담으로 인터랙티브가 익숙치 않아 시간을 좀 빼앗겼다. 옛날 div2 D에 인터랙티브가 자주 나왔던 시절에는 D를 풀 실력이 안 되었어서 생각을 안 하고 있었는데 진짜 인터랙티브 연습 좀 해야겠다...
D
왼쪽 아래, 오른쪽 아래 사각형의 네 모퉁이, 총 8개 중 하나를 반드시 잘라야 하고, 그 중 하나만 잘라도 된다. 오른쪽 아래를 다 더하고 후보 중 가장 작은 것을 더하면 답이다.
이 조건을 생각한건 문제 읽고 거의 바로이지만, 너무 간단해서 내가 문제를 잘못 이해한 것인지 몇번이고 생각했다. $n$제한도 작아 함정이 있지는 않은지 고민하다 시간을 빼앗겼다. 틀리지 않는 것이 중요하긴 하지만 불안감보다는 이성적으로 판단하는 것이 중요할 듯 싶다.
E
결석을 고려하지 않고 생각해보면 선생과 학생평균을 각각 정렬한 뒤 순서대로 매칭시키는 것이 최적이다. 이 때 각 학생 그룹이 매칭되는 선생은 많아봤자 양옆으로 1씩 바뀌므로, 미리 학생평균과 선생을 내림차순으로 정렬한 뒤, 매칭이 왼쪽으로 밀렸을 때, 안 밀렸을 때, 오른쪽으로 밀렸을 때 매칭이 실패하는 것이 얼마나 있는지 누적합으로 관리해주면 구간을 $O(1)$에 처리할 수 있다. 이제 각 학생 그룹에 대해서 그 그룹의 어떤 학생이 빠졌을 때, 결론적으로 그 그룹의 평균이 바뀌고 이 때 바뀐 순서가 무엇인지 이분탐색으로 구할 수 있다. 이제 케이스를 잘 나누고 안바뀌는 부분, 왼쪽 또는 오른쪽으로 바뀌는 부분, 빠진 학생이 속한 그룹에 대해 각각 매칭이 가능한지 검사하여 매칭 가능성을 검사하면 된다.
이게 정말 구현이.. 정말 힘들었다. 이 구현을 하면서 난생 처음으로 lower_bound에서 비교 함수만 잘 짜면 int형 배열에서 pair를 가지고 이분탐색이 가능함을 배웠고.. 사실 코드의 절대적인 양은 그렇게 많지 않은데 디버깅에 시간이 많이 뺏겼다. 여담으로 학생그룹과 선생을 모두 모아놓고 학생은 -1, 선생은 +1이라 생각할 때 내림차순으로 정렬한 뒤 누적합을 구해보자. 여기서 음수가 없다면 매칭이 가능한 것이다. 이 조건을 이용하면 lazy seg로 문제를 풀 수 있다. 아니 나 말고는 다 그렇게 풀었던데... 흑흑
결국 오늘도 대부분의 오렌지~레드 구간의 사람들이 푸는 만큼은 풀었지만, 페널티로 인해서 드라마틱한 상승은 없었다. 코포 버츄얼을 자주 돌려 구현 실수를 줄이는 것이 좋겠다.. 라고 하지만 오늘 div3 버츄얼 돌면서 뇌절을 몇번이나 했는지 모르겠다. 언젠가는 나아지겠지?
