구사과와 함께하는 인터넷 예선 연습 대회

팀: glycine (rkm0959, TAMREF, leejseo) 결과: 8솔브, 4등

스코어보드: https://www.acmicpc.net/contest/scoreboard/346 

입시 공부와 이 대회 참가 사이에서 고민하고 있었는데, 탐레프가 leejseo랑 같이 팀으로 나가자고 해서 나갔다.

결과도 잘 나왔고 대회 자체도 엄청 재밌었다. 물론 3컴에 인터넷도 엄청 썼지만...

각자 코드를 짜서 AC를 받은 문제는 다음과 같다. 문제 순서는 AC 순서.

밑에 문제 이름 옆에 괄호 안에 써놓은 사람은 그 문제를 잡은 사람 목록이다.

rkm0959: G, L, H, F 

TAMREF: J, C, D

leejseo: B

G: 등록 (rkm0959, 1분)

대회 중 풀이: 그냥 출력하면 되는데 팀 계정 기본 언어가 Text여서 한 번 틀렸다. 상큼한 시작.

J: The Chosen Sub Matrix (TAMREF, 28분)

대회 중 풀이: 범위가 작으니, 문제의 조건을 잘 읽고 구현하면 된다. 여러 이유로 3WA.

대회 후 내 풀이: 그냥 구현 문제라 크게 다른 건 없었다. 짜는 방식이 살짝 달랐다.    

L: Weights (rkm0959, 65분)

대회 중 풀이: 생각을 깊게 안하고 코드를 짜고 내다보니 쓸데없이 시간도 오래 걸리고 WA도 2번이나 났다. 

답에 대한 이진탐색이 가능하므로, 이진탐색을 하자. \( x \)개의 weight를 올리는 것이 가능한지 판별하고 싶다면, 당연히 가장 무게가 작은 \(x\)개의 weight들을 올릴 수 있는 지만 확인하면 된다. 이제 그리디하게 weight를 올리자.

durability가 큰 컨테이너 순으로 다음 시행을 한다.

올릴 수 있는 가장 무거운 weight를 컨테이너에 올려주는 것을 반복 

이 방식으로 모든 weight를 올릴 수 없으면, \( x \)개의 weight를 올리는 것은 불가능하다. 

또한, 주어진 배수 조건 때문에 서로 다른 weight 종류 개수는 \(\mathcal{O}(\log W)\)이다. 

이 두 가지 관찰을 하면 문제를 해결하는 것은 간단하다. 주어진 input을 정렬하고 weight의 종류/개수를 전처리를 하자.  

이제 결정문제를 쉽게 \(\mathcal{O}(N \log W)\)에 해결할 수 있고, 전체 문제도 제한 시간 안에 풀 수 있다.

이런 문제가 어떻게 8분 컷이 될까 싶다 ㅋㅋ

C: Cross Spider (TAMREF and leejseo, 68분)

대회 중 풀이: 모든 점이 한 평면 위에 있는지 판별하는 문제다. \( N \le 3 \)일 때는 당연히 참이고, \(N \ge 4\)를 보자. 

일직선 위에 있지 않은 세 점은 한 평면을 이루니까, 이 평면 위에 모든 점이 있으면 충분하다.

네 점의 Coplanarity는 벡터의 외적/내적을 활용하여 \( \mathcal{O}(1)\)시간에 판별할 수 있다. 

이걸로 \(\mathcal{O}(N) \) 풀이가 완성된다. overflow에 주의할 필요가 있다. 어쩌다보니 7WA;;

대회 후 내 풀이: '일직선 위에 있지 않은'을 빼먹어서 한 3WA 정도 한 것 같다. 극혐.    

D: Gophers (TAMREF and leejseo, 152분)

대회 중 풀이: 각 CD가 영향을 줄 수 있는 길이가 동일하므로, 각 CD가 '독점적으로 영향력을 발휘하는 영역'은 선분이다. 

그래서 이 구간을 구해주면서 그 구간에 속하는 구멍의 개수를 더하고 빼면서 쿼리에 답하면 된다. 

대회 중에는 OSRank와 펜윅을 써서 2928ms 뚝딱 AC. 사실 펜윅을 쓸 필요는 없다. (OSRank도 쓸 필요 없다. ㅋㅋ!)

대회 후 내 풀이: 독점구간 및 그 구간에 속하는 구멍 개수는 set을 사용하면 쉽게 계산 가능. lower/upper bound 쓰자.

H: Store-Keeper (rkm0959, 221분)

대회 중 풀이: http://www.usaco.org/index.php?page=viewproblem2&cpid=769 이 문제가 상당한 도움이 된다.

bfs를 돌려야 할 것 같은 문제인데, 상태를 (내 위치, 박스 위치)로 두면 상태 개수가 저세상으로 간다. 

그러니까 상태를 (박스 위치, 박스 기준으로 내가 있는 방향 - U/D/L/R)로 두자. 이러면 상태 개수가 \( \mathcal{O} (NM) \)이다.  

가능한 행동은 둘 중 하나다. 내가 있는 곳에서 박스를 밀어 움직이거나, 다른 방향에서 박스를 밀기 위해 내가 움직이는 것이다. 첫 번째 행동은 박스를 밀 수 있는지를 판별하는 게 \( \mathcal{O}(1)\)에 되니 문제 없다.

두 번째 행동은 조금 까다로운데, 내가 한 위치에서 다른 위치로 움직일 수 있는지를 판별해야 하기 때문이다.

이 과정에서 flood-fill을 하는 등의 방법을 쓰면 \( \mathcal{O}(N^2M^2)\) 풀이가 나온다. 

잘 짜여진 \( \mathcal{O}(N^2M^2)\)는 실제로 AC를 받았지만, 그렇지 않으면 TLE가 뜬다고 한다. 

시간을 줄이려면 두 번째 행동이 가능한지 여부를 빠르게 판별할 수 있는 방법을 찾아야 한다.

여기서 biconnected component를 떠올릴 수 있다. grid를 그래프로 보고, biconnected component를 구하자. 

grid의 각 칸이 (즉 그래프의 각 노드) 속한 biconnected component를 set 등으로 모두 저장하자.

각 칸이 속한 biconnected component의 개수는 최대 4개니까 (why?) set을 써도 큰 문제는 없다. 

이제 처음 위치와 끝 위치가 같은 biconnected component에 속하는 지 여부를 확인하여, 두 번째 행동이 가능한 지 불가능한 지 판별할 수 있다. 이 판별은 앞선 관찰에 의해 \( \mathcal{O}(1) \)에 가능하다. 이제 bfs를 그대로 돌리면 문제가 \( \mathcal{O}(NM) \)에 풀린다. 

 

Tarjan BCC를 처음 써봤다. 많은 것을 배울 수 있었던 문제. 위에 저 USACO 문제도 풀어봐야 할 듯.

F: Laundry (rkm0959, 244분)

대회 중 풀이: \(i\)번째 오는 사람은 \(2d_i\)개 양말용 빨래집게, \(3d_i\)개 셔츠용 빨래집게가 필요하다. 

이 문제는 그리디로 풀 수 있는 문제다. \(d_i\)가 큰 사람 순서로, 다음과 같이 집게 색깔을 고르자.

1. 집게가 \(5d_i\)개 이상 있는 색깔이 있으면, 그 중 집게 개수가 가장 작은 색깔을 골라 양말/셔츠용으로 한다.

2. 1이 실패했다면, 집게가 \(3d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 셔츠용으로 한다.

3. 1이 실패했다면, 집게가 \(2d_i\)개 이상 있는 색깔 중 집게 개수가 가장 작은 색깔을 골라 양말용으로 한다.

이렇게 해서 색깔 분배가 가능한 지 확인하면 된다. set과 lower/upper bound를 쓰면 쉽게 구현할 수 있다. \( \mathcal{O}(N \log N) \).

B: Bytean Road Race (leejseo, rkm0959, 283분)

대회 중 풀이: leejseo와 내가 각자 맞는 풀이를 발견했고, 각자 짜서 냈다. 내 코드는 틀렸고, leejseo가 맞았다. 갓...

leejseo의 풀이는 https://en.wikipedia.org/wiki/Reachability#Kameda's_Algorithm을 쓴다. 

간단하게 설명하면, 주어진 그래프에서 reachability는 하나의 partial order와 같다. 

그런데 dfs를 2번 '잘' 하면, dfs에서 정점이 label된 순서를 통하여 reachability의 partial order를 얻을 수 있다!   

https://www.sciencedirect.com/science/article/pii/0020019075900198?via%3Dihub 참고. 

알고리즘이 선형이라서 진짜 개빠르다 ㄹㅇ;;; 대신 대회장에서 생각하기는 좀 어려운 풀이인듯 싶다.

대회 중 풀이/대회 후 내 풀이: 풀이를 설명하기 위해 먼저 정의를 하나 내리자.

Definition: 정점 \(v\)에 대하여, 경로 \(DP(v)\)와 \(RP(v)\)를 다음과 같이 정의하자. 

\(DP(v)\): \(v\)에서 시작해 아래쪽으로 갈 수 있을 때는 아래쪽으로 이동하고, 아니면 오른쪽으로 이동하여 \(n\)에 도착하는 경로. 

\(RP(v)\): \(v\)에서 시작해 오른쪽으로 갈 수 있을 때는 오른쪽으로 이동하고, 아니면 아래쪽으로 이동하여 \(n\)에 도착하는 경로. 

또한, 정점 \(v\)에 대하여, 정점 \(DPnext(v)\)와 \(RPnext(v)\)를 다음과 같이 정의하자. 

\(DPnext(v)\): 경로 \(DP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(DPnext(n)=n\)으로 둔다.

\(RPnext(v)\): 경로 \(RP(v)\)에서 \(v\) 다음으로 방문하는 정점. 편의상 \(RPnext(n)=n\)으로 둔다.

풀이의 핵심은 다음 관찰이다. 

Claim 1: 두 정점 \(u, v\)가 있다. 이때, 다음 두 명제는 동치다.

명제 1: \(u\)에서 \(v\)로 갈 수 있는 경로가 존재한다. 

명제 2: \(v\)는 \(DP(u)\)와 \(RP(u)\) 사이에 존재한다.

이 Claim은 \(1\)번 정점에서 모든 점에 도달할 수 있고, 모든 점에서 \(n\)번 정점에 도달할 수 있다는 문제 조건에 의해 성립한다. 

직관적으로 이해하기 쉬운 Claim으로, 그 증명 자체도 크게 어렵지 않을 것으로 예상한다. 

이제 명제 2가 참인지 거짓인지를 어떻게 빠르게 판별할 지 생각해보자. 다시 두 가지 관찰을 해야 한다.

Claim 2: 앞선 Claim 1에서의 명제 2는 다음 명제 3와 동치다. 

명제 3: \(DP(u)\)에서 처음으로 \(y\)좌표가 \(v\)의 \(y\)좌표보다 작거나 같은 점을 \(w_1\)이라 하자.

또한, \(RP(u)\)에서 처음으로 \(x\)좌표가 \(v\)의 \(x\)좌표보다 크거나 같은 점을 \(w_2\)이라 하자.

이때, \(w_1\)의 \(x\)좌표는 \(v\)의 \(x\)좌표보다 작거나 같고, \(w_2\)의 \(y\)좌표는 \(v\)의 \(y\)좌표보다 크거나 같다. 

Claim 3: \(DP(u)\)는 \(u\) 뒤에 \(DP(DPnext(u))\)를 붙인 것이다. \(RP(u)\)도 마찬가지.

두 Claim 다 직관적으로 이해하기 쉽고 자명하다. 경로 위에서 \(x, y\) 좌표는 모두 단조적이므로, Claim 2와 이진탐색을 섞으면 명제 2가 참인지 거짓인지를 판별할 수 있을 것 같다! 실제로 이는 가능하다.

이진탐색을 떠올리면 남은 것은 \(DP(u)\)에서 \(k\)번째 정점을 빠르게 구하는 방법을 찾는 것이다.

Claim 3에서 나온 관찰에서, Sparse Table을 사용할 수 있음을 파악할 수 있다.

자세한 설명은 고려대학교 2017 경시 Line Friends 참고. http://koosaga.com/206에 잘 설명되어 있다.

이제 이진탐색 대신 LCA를 구하는 방법처럼 binary lifting을 하여 명제 3이 성립하는지 확인할 수 있다. 

대회에서는 binary lifting 부분에서 케이스 하나를 놓쳐서 틀렸다. 시간복잡도는 \( \mathcal{O}((N+Q)\log N)\)이다.