12월 14일 2017 Ho Chi Minh Regional 연습

 연습 결과와 대회 공식 등수입니다. 일부는 시간제한이 너무 짧아서 맞다고 생각한 답이 시간초과가 났고, 일부는 시간초과가 날 것 같다고 생각한 답이 맞는 등 불편한 점들은 꽤 있었습니다. 문제 분야도 한쪽으로 과하게 몰린 느낌이 있었습니다. 꽤나 말렸는데도 11문제 푼 것은 좋은 신호라 생각하지만, 말린 만큼 아쉬운 점도 있는 것 같습니다.

~1시간: 초반에 쉬운 I와 C를 밀고 나서 바로 도토리가 B를 잡았습니다만, 나눗셈 연산 4천만 정도의 풀이에 시간초과가 나서 당황했습니다. 1시간동안 시간을 줄여봤지만 1초 아래로 만들 수는 없어서 일단 보류했습니다.

~2시간 30분: 3번째 문제로 상수가 J를 해결했습니다. 쉬운 문제가 전부 도토리한테 몰린 상황에서 B 시간초과로 순서가 많이 꼬였습니다. 보류 이후 풀이가 나온 F, H를 코딩했습니다. F는 대충 보고 어려운 쪽 문제인 줄 알고 버려뒀는데, 전달하고 보니 생각보다 쉬워서 바로 코딩했습니다. E는 왜 시간 안에 나오는지 모르겠습니다.

~3시간 30분: 도토리가 D를 코딩했고, 상수가 K를 코딩하는 동안 도토리와 함께 G를 풀었습니다. 풀고 나서는 매우 행복했지만, 풀이 검증 과정에서 어설퍼 꽤나 오래 걸렸습니다.

~4시간: A는 열심히 수식으로 뻘짓을 하다가 답을 구했고, 답을 보고 나서는 필요 없지만 매우 깔끔한 풀이가 생각났습니다. 코딩이 그리 오래 걸리지 않았기 때문에 중간에 끼어들어갔습니다.

~5시간: 상수가 K를 여러 번의 시간초과를 낸 후 풀었습니다. 구현 문제인지 알고리즘 문제인지는 모르겠지만 다른 사람보다 오래걸렸습니다. 이후 B를 처음부터 다시 풀어서 11문제로 마무리했습니다. L은 제 자유시간이 1시간 정도 남았다면 비빌 수 있을 것 같지만 언제나처럼 힘들었을 것 같습니다.

문제 난이도는 Opencup GP에서 세계대회를 열어도 괜찮을 정도로 매우 어려웠습니다. 점수판을 안본 것 때문에 순서가 꼬여서 패널티가 높아진 것은 아쉽지만, 순서가 정상적이어도 풀 문제수가 늘어나지 않아 큰 문제는 아닌 것 같습니다.

가장 신기했던 문제 G입니다.

음이 아닌 정수 n(2 <= n <= 1024)개를 가지고 두 사람이 게임을 합니다. 숫자가 남지 않을 때까지 한 명씩 번갈아가면서 정수를 가져가고, 최종 점수는 가져간 숫자 총합입니다. 점수가 주어진 숫자 k (2 <= k <= 32)의 배수인 쪽이 이기는데, 둘 다 k의 배수이거나 둘 다 아닌 경우는 비긴 것으로 합니다.

최적의 전략을 따랐을 때에 대한 결과를 구하면 됩니다.

예제 입력

3(n) 4(k)

4 4 2

예제 출력

SECOND

예제 설명

첫 번째 사람이 어떤 것을 가져가도 두 번째 사람이 4를 가져갈 수 있습니다.

이 경우 첫 번째 사람의 총점은 6으로 4의 배수가 아니지만, 두 번째 사람의 총점은 4로 4의 배수입니다.

E 코멘트입니다.

플로우, MCMF류의 문제에서 작은 시간복잡도로 문제를 내는 것은 매우 안좋다고 생각합니다. 

플로우랑 MCMF 알고리즘이 20개가 넘고, 이것들의 시간복잡도도 엄청 다양하기 때문입니다.

어쨋거나, 이 문제에서는 O(NM log nC) 정도의 시간복잡도로도 해결되는 것 같은데,

아이디어는 헝가리안 알고리즘에서 음수인지 판단하는 부분 대신, -err보다 작은지로 판단한 뒤, err를 절반씩 낮춰나가는 방식입니다.

되는지는 확인되는대로 코멘트를 수정하겠습니다.

---

직전글인 CERC 17 I의 풀이?입니다.

Lemma)  c<=b를 만족하는(교차하는) 두 "좋은 구간" [a, b], [c, d]에 대해, 

[a, d](합집합)와 [c, b](교집합)는 좋은 구간이다.

이것은 [a, c-1], [c, b], [b+1, d] 3개의 구간에 포함되는 숫자들의 분포에 대해 확인해 보면 감이 오실 것 같습니다.

이제 분할정복 방식으로 처리하는데, 구간 쿼리 문제를 분할정복으로 처리하는 방식은 다음과 같습니다.

[1, n]에 완벽하게 포함되는 [s, e](1 <= s, e <= n) 쿼리들을 해결하는 문제가 있다고 합시다.

1) 가운데 지점 m = (1+n)/2 를 포함하는 쿼리(s <= m, m+1 <= e) 들을 O((N+Q) Poly(log))로 모두 계산한 뒤,

2) 왼쪽 쿼리 (s <= m) 는 왼쪽 부분으로, 오른쪽 쿼리 (m+1 <= e) 는 오른쪽 부분으로 나눠서 재귀적으로 처리합니다.

이 방법은 1) 에 대한 알고리즘 설계만 하면 되기 때문에 문제가 간단해지는 장점이 있지만, 안되는 문제도 매우 많습니다.

s <= m, m+1 <= e인 구간들을 처리하기 위해 다음과 같은 값을 계산합니다.

L_x (x <= m) := 시작지점이 x보다 작거나 같은 구간들 중 [m, m+1]을 포함하는 가장 짧은 "좋은 구간"

R_x (x >= m+1) := 끝지점이 x보다 크거나 같은 구간들 중 [m, m+1]을 포함하는 가장 짧은 "좋은 구간"

Lemma에 의해, [s, e] 쿼리에 대한 답은 L_s와 R_e의 합집합이 됩니다.

(만약 [s, e]를 포함하는 더 짧은 좋은 구간이 있다면, 교집합이 좋은 구간이기 때문에 L_s나 R_e에 포함되는 좋은 구간이 있게 되고, 이 경우 L_s나 R_e의 정의에 모순이 생깁니다.)

풀이에서, L_s, R_e는 [m, m+1]에서 시작하여 좋은 구간의 maximal을 구해 나가는 방식으로 구할 수 있다고 합니다.

[m, m+1]이 좋은 구간이라면, maximal은 [m, m+1] 입니다. 아니라면, m번째 값과 m+1번째 값 사이에 있는 숫자는 모두 포함해야만 합니다. < 구간이 늘어나지 않을때까지 반복하는 방식입니다. maximal을 구했다면 갱신을 해준 뒤, L_x를 구하고 있다면 왼쪽을 한칸, R_x를 구하고 있다면 오른쪽을 한 칸 확장한 뒤 앞을 반복합니다.

연습때는 분할정복으로 해결하지 않았습니다. 다음과 같은 값을 정의한 뒤, (값을 구하는 방식은 매우 어렵지만, 설명하지는 않겠습니다)

L_x := 시작지점이 x인 구간들 중 가장 긴 "좋은 구간"

R_x := 끝지점이 x인 구간들 중 가장 긴 "좋은 구간"

쿼리 s~e에 대해 L_1 ~ L_s 중 [s, e]를 포함하는 가장 큰 번호 p, R_e ~ R_n 중 [s, e]를 포함하는 가장 작은 번호 q를 구했습니다.

이 경우 답은 p~q입니다.