2020 10월 PS 일지

중간고사 기간이라 몇개 없다. :( 다음달부턴 학교 공부 내용도 뭐 했는지 조금씩 정리해서 따로 적어볼 생각이다. 나중에 기억나는데 도움이 될것 같아서...

Rounds 

Codeforces Round 678 (Div.2) : 1077th, -42.

Div2D 못풀어서 떡락했다. 그렇게 어렵지 않은 이분탐색 + 트리 DFS 정도로 생각했는데 놓친 부분이 있었던 듯.

 

Codeforces Round Edu97 : 320th, +22

시간이 약간 모자라서 E번 코딩을 못 끝냈다. 대략적인 풀이는 이분탐색 + LIS 응용인데, 세그트리를 쓰는 구현이 오히려 조금 더 쉬웠다는 것 같다. 다음날 dhdroid랑 F번을 업솔빙했다.

---

Problems

2020 중앙대학교 프로그래밍 대회 검수를 맡았다. www.acmicpc.net/contest/view/549

대회가 끝나고 나면 11월에는 간단한 내 풀이 + 후기를 적어볼 생각이다.

 

코딩은 안 해보고, 입풀이로만 푼 문제. dhdroid / dlwocks31 두명이랑 같이 고민해봤다.

 

2020 IOI, Day 1, Problem 2, Connecting Supertrees

난이도 : SAC P2

대략적인 문제는, $n$개의 노드를 적당히 간선으로 잇되, $i$ 에서 $j$ 까지 갈 수 있는 서로 다른 path의 개수가 $p[i][j]$ 개여야 한다. $p[i][j] \leq 3$ 이고, $n \leq 1000$.

관찰을 쌓으면서 서브태스크를 하나씩 잡아나가자.

어떤 노드 집합 $S$ 가 모든 $a, b \in S$ 에 대해 $p[a][b] = p[b][a] = 1$ 이라면, 이 집합을 적당한 트리로 이어주면 된다. 이 관찰만으로 21점을 얻을 수 있다.

 

Subtask 1 : 아무 트리나 출력하면 된다.

Subtask 2 : Union-Find를 이용하여, 같은 트리에 들어가야 하는 노드들의 집합을 찾자. 이 집합이 아귀가 안 맞으면 (...) 불가능한 것이다. 그렇지 않다면 그 집합 내에서는 아무 트리나 출력하면 된다.

 

어떤 노드 집합 $S$ 가 모든 $a, b \in S$ 에 대해 $p[a][b] = p[b][a] = 2$ 라면, 이 집합을 한바퀴 도는 사이클로 이어주면 된다. 이 관찰로 19점을 더 얻을 수 있다.

 

Subtask 3 : Subtask 2와 거의 같다.

 

한 집합에 사이클이 2개 만들어진다면, 그 사이클에 속한 점을 하나씩 잡아 주면 경로가 4개가 된다. (8자 같은 형태에서, 8자의 위와 아래 점을 잇는 경로의 개수를 생각해 보자. 위쪽과 아래쪽 사이클에서 각각 left 또는 right을 고를 수 있다).

 

따라서, 답이 되는 그래프는 반드시 사이클 하나와 트리로 구성되어 있으며, 사이클을 하나의 supernode로 볼 때 전체 그래프가 포레스트를 이룬다는 사실을 확인한다. 이후에는 사이클에 들어가야 하는 점과, 나머지 점들을 분리하고, 사이클에 들어가는 점들은 한바퀴 돌리자. 나머지 점들은 적당히 트리로 이어주면 된다.

 

Subtask 4 : 위 알고리즘대로 구현하고, 아귀가 안맞는 경우만 조심하면 된다.

Subtask 5 : $p[i][j] = 3$ 이 불가능함을 알 수 있다.

 

2020 IOI Day 2, Problem 6, Stations

난이도 : SAC D5인데, 잘못 매겨졌다고 생각한다. 만점을 받는 규칙이 실제로는 더 빡빡한데 그 규칙이 BOJ에는 반영되지 않았다. 이 문제의 난이도를 매긴 분들이 이 점을 고려해서 높여 준건지는 모르겠다. (규칙이 없는 버전의 문제라면 다이아는 아닌거 같기도 하고...)

처음 보는 기괴한 스타일의 문제인데, 함수 두개를 짜야 한다. 하나는 Preprocess로 트리의 각 점에 내가 번호를 붙여 줄 수있고, 두번째 함수는 내가 앞에 붙인 번호들을 기준으로 $s, t$ 와 $s$의 neighbor를 다 줄 때 $s$에서 $t$ 로 가는 경로상에 있는 점 찾기. 정점이 1000개인데 라벨은 최대 1000 까지의 수만 써야 만점을 받을 수 있다. 정점간 라벨이 겹치는건 상식적으로 말이 안될것 같으므로, 내가 붙이는 번호가 원래 번호의 permutation이라고 이해하면 되겠다.

 

Subtask 1, 2: 이 문제의 핵심과 별로 관련이 없다. 이 문제의 핵심은, '정점의 라벨' 을 붙여줌으로써 트리의 형태에 대한 정보를 그 안에 잘 인코딩할 수 있는지의 문제인데, Subtask 1, 2까지는 트리의 구조가 미리 제시되어 있으므로, 이 트리에 특수한 정보들을 인코딩하면 해결된다. 

Subtask 3 : 100만까지의 라벨을 쓸 수 있고 루트를 제외한 나머지가 직선형이므로, 각 노드들을 '$a$ 번 branch의 $b$ 깊이에 있는 노드' 라고 생각하고 라벨링하면 된다.

Subtask 4 : 노드가 8개밖에 없는데 반해 가용 라벨이 10억까지이므로, 각 노드의 라벨을 30비트 정도의 비트필드로 보고 필요한 정보를 마구 구겨넣으면 된다. 각 노드까지의 거리를 미리 재 놓고 그 값들을 3비트 * 8개를 쓴다던가...

 

서브태스크를 통해 별로 힌트를 얻지 못했다. 서브태스크 5에 대해서는 내가 쓴 라벨값의 최대 MAX_LABEL이 작을수록 많은 점수를 주는데, 이를 이용해서 오히려 더 많은 생각을 해볼 수 있다. 

오일러투어 돌 때처럼, in / out time 을 각 노드별로 기억하자. 특히, in time * 1000 + out time 같은걸로 정보를 기록하면 100만개의 라벨을 써서 in/out time을 모두 기억할 수 있다. s와 t에 대해 이 정보들을 비교하면, 만약 t가 s의 서브트리에 속한다면 적절한 branch를 찾아가고, 그렇지 않다면 위로 올라가야 한다.

 

100만개를 1000개로 줄이기 위해서는 둘 다 가지겠다는 생각을 포기해야 한다. 루트로부터의 거리가 홀수인 정점들에서는 in time만, 짝수 정점들에는 out time 만 기억하자. 홀수정점의 neighbor는 모두 짝수정점이므로, 주변과 나의 라벨의 대소를 비교하면 내가 홀수인지 짝수인지 알 수 있다.

필요한 정보가 정확히 1000개이고, 우리는 어차피 실제값이 아닌 대소만 비교할 수 있으면 충분하므로 이걸 좌표압축해서 던져주고 반대쪽에서는 이걸 이용해서 100만개 일때의 알고리즘을 비슷하게 쓰면 된다.