NERC 2020 Virtual Participation

koosaga와 같이 2인 팀으로 버추얼을 돌았다. (Gym 링크)

총평 : 매우 비추천.

코로나 때문에 대회를 온라인으로 운영하느라고 3인 3컴으로 진행했다고 하는데, 그러다 보니 문제는 15문제나 되고 그 중에 한 1/3이 시간끌기용 trash problem이다.

총 9문제를 풀었으며, 공식 대회 기준 9등이다. 내가 A, C, D, I를 풀고 koosaga가 E, G, K, L, M을 풀었다. 아마 3명으로 쳤으면 1~2문제는 더 풀지 않았을까 싶다..

아래는 문제별 후기(스포 주의). 제대로 읽지도 않은 문제가 과반이라 매우 대충 적었다.

A : 가중치가 1인 노드가 A개, 2인 노드가 B개 있다. A+B개의 노드로 이루어진 이진 트리를 하나 출력하는데, 모든 노드에 대해 abs(왼쪽 서브트리의 가중치 합 - 오른쪽 서브트리의 가중치 합) ≤ 1을 만족해야 한다. (불가능하면 불가능하다고 출력)

1이 2보다 훨씬 유동적으로 들어갈 수 있으므로 루트에는 되도록 2를 넣으면 좋을 것 같다. 이제 남은 1과 2를 양쪽에 적절히 배분해야 하는데, 직관적으로 봤을 때 최대한 1과 2가 골고루 들어가도록 하면 좋을 것 같으니 갯수의 홀짝성에 따라서 최대한 반씩 나누어서 들어가도록 해 주고, 이제 재귀적으로 다시 문제를 풀면 된다. 왜 맞는지 정확히는 모르겠는데, 아무튼 그렇게 대충 짜면 맞는다.

 

B : 단어 27만개짜리 사전을 주고, 그 사전에 들어있는 단어 두 개가 주어지면 사전에서 단어 하나를 더 골라서 복면산 문제를 만들 것이다. 문제의 답이 유일하게 되는 단어를 사전에서 모두 찾아라.

    SEND 
+  MORE  <- 위에 있는 2단어를 입력으로 주면
=MONEY  <- 여기 들어갈 단어를 찾는 것이다. 

백트래킹을 어떻게 잘 짜면 되는 듯 한데, 나는 접근 방식을 이상하게 해서 TLE가 났다. 위의 두 단어는 이미 정해져 있으니까 걔네들의 각 글자마다 값을 다 줘 보면 되는데, 낮은 자리부터 결정해 나가면 아래쪽 값도 결정하면서 탐색을 할 수 있기 때문에 가지치기가 어떻게 잘 되는가보다. 아무리 봐도 시간 끌려고 낸 문제. 여담으로 이걸 짜다가 한 시간 정도 WA on test 1의 늪에 빠졌었는데, 그 이유는 출력할 때 줄 끝에 공백을 찍어서였다;; 2020년인데 좀 심하지 않나 하는 생각이다 ㅋㅋ;

 

C : 정점 20개 이하의 루트 있는 트리가 주어진다. 처음에는 루트 정점만 빨간색이고, 나머지 모든 정점은 초록색이다. 이제 한 번의 연산으로 정점 하나의 색깔을 toggle할 수 있는데(빨간색 <-> 초록색), 연산 전후에 모두 다음 조건을 만족해야 한다 : "임의의 빨간색 정점에 대해, 그 정점의 모든 조상도 빨간색이다." 조건을 만족하는 상태로 연산을 최대한 많이 하고 싶다고 할 때, 연산의 sequence를 출력하라.

예제를 좀 살펴보면 "가능한 모든 색깔 조합을 다 방문"하는 게 답일 거 같다고 짐작할 수 있다. 그리고 실제로도 그렇다! 우선 풀이의 편의를 위해서 초기 상태가 "모든 정점이 초록색인 상태"라고 하자. 이제 문제를 재귀적으로 풀 수 있다. 예를 들어 어떤 노드에 자식이 2개 있고 각각 가능한 상태가 총 3개, 4개 있다고 하자. 각 자식에 대해 재귀함수를 호출하면 각각 "상태 1 -> 상태 2 -> 상태 3", "상태 1 -> 상태 2 -> 상태 3 -> 상태 4"에 해당하는 연산 순서를 얻을 수 있다. 각 연산이 정점 하나의 색을 toggle하는 것이므로 반대 방향으로도 움직일 수 있다는 것을 관찰해야 한다.
이제 나에서 모든 조합을 다 방문하기 위해서는 우선 나 자신을 빨간색으로 바꾼 뒤, 자식의 상태를 다음 순서대로 방문하면 된다 : (1, 1)(여기가 시작점) -> (1, 2) -> (1, 3) -> (1, 4) -> (2, 4) -> (2, 3) -> (2, 2) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (3, 4). 대충 지그재그로 왔다갔다 한다고 생각하면 된다. 자식이 3개 이상일 때에도 대충 비슷한 전략을 적용하면 모든 상태를 다 방문할 수 있다. 재귀함수를 하나 더 짜도 되고, 반복문으로 잘 구현할 수도 있다.

 

D : 계단이 하나 있고, 계단의 각 층은 8개의 타일로 이루어져 있다. 각 타일은 흰색이거나 검은색이다. 이제 이 계단에서 두 사람이 선/후공을 나누어 다음 규칙에 따라 게임을 한다:
- 처음에 말 하나를 계단의 맨 아래층(1층)에 놓는다.
- 각 차례가 올 때마다 말을 위로 옮겨야 한다. 말을 옮길 때는 다음 조건을 만족하는 층으로 옮길 수 있다:
  (계단 층수의 차이) ≤ (두 층에서 위치와 색깔이 모두 같은 타일의 쌍 갯수).
- 자기 차례에 말을 옮길 수 없으면 진다.
계단이 총 N층이라고 할 때, 계단의 (1층 ~ k층)까지 써서 게임을 하면 선공이 이기는지 지는지를 모든 k에 대해 구하여라.

"D[i] = i층에서 시작할 때 선공이 이기면 1, 지면 0" 으로 정의된 DP를 가장 먼저 생각해 볼 수 있다. 모든 Suffix에 대해 구하는 거였으면 그냥 DP를 뒤에서부터 하면 되는데, Prefix라서 조금 더 까다롭다. 핵심 관찰은 각 차례마다 말을 많아야 8칸까지 옮길 수 있다는 것으로, DP 값은 binary니까 \( 2^8 \)가지의 정보만 어떻게 잘 관리하면 되겠다는 생각을 할 수 있다.
\( F_{s, e} : \{0, 1\} ^8 \rightarrow \{0, 1\} ^8 \)를 "\( [e+1, e+8] \) 구간의 DP값이 주어지면 \( [s, s+7] \) 위치의 DP값을 내놓는 함수" 라고 정의하자. 계단의 (1층 ~ k층)까지 써서 게임했을 때의 결과는 \( F_{1,k} ((1,1,1,1,1,1,1,1)) \) 로 쓸 수 있다. \( F_{k, k} \) 는 \( 2^8 \) 가지 경우에 대해 다 해보면서 구하면 되고, \( F_{1, k-1} \) 과 \( F_{k, k} \) 를 각각 알면 \( F_{1, k} \)를 또 \( 2^8 \)가지에 경우에 대해 구하면 되므로 \( O(2^8 N) \) 시간에 모든 k에 대한 정답을 구할 수 있다.

 

E : koosaga가 품. 쉬운 문제인 듯.

F : 풀이를 까 보니까 생전 처음 보는 알고리즘 이름이 2개 써 있다.

G : koosaga가 품.

H : 이상한 문제

I : 6각형 cell이 붙어 있는 구조의 격자판에서 Interactive 환경으로 게임을 진행한다. 구체적인 상황은 아래와 같다.
- 6각형 격자를 2차원 좌표계로 표현하면 \( (-n, n), (-n, 0), (0, -n), (n, -n), (n, 0), (0, n) \) 의 6개 꼭짓점을 갖는 육각형 안에 포함된 격자점이다. 어떤 칸과 인접한 칸은 \( (dx, dy) \in \{ (-1,1),(-1,0),(0,-1),(1,-1),(1,0),(0,1) \} \) 만큼 이동해서 갈 수 있는 칸이다. 문제에서 n은 항상 20이다.
- 초기에 나의 말은 \( (-n/2, 0) \) 좌표에, 상대의 말은 \( (n/2, 0) \) 좌표에 있다.
- 나와 Jury가 번갈아가면서 말을 인접한 칸으로 한 칸씩 움직인다. 단, 나의 말이나 상대의 말이 있었던 적이 한 번이라도 있는 칸에는 가면 안 된다. (시작 지점 포함)
- 자기 차례에 말을 이동시킬 수 없으면 진다. 
Jury는 매 차례마다 이동 가능한 칸 중 랜덤하게 한 칸을 골라 거기로 이동한다. 당신은 Jury와 최대 5000번 게임을 해서 모두 이겨야 한다.

우선 관찰할 것은 random하게 움직이는 Jury를 가만히 놔두기만 해도 알아서 빨리 자멸한다는 것이다. 왜 그런지는 "직관적으로 그럴 거 같다 + 시뮬레이션 돌려보니까 진짜 그렇더라" 보다 잘 설명하기 힘들다... 아무튼 이제 나의 전략은 "육각형 어딘가를 상대가 못 들어오도록 먹기"가 된다.
내가 먼저 움직이기 때문에, 육각형 정 가운데 (좌표 \( (0,0) \)) 점으로 내가 먼저 갈 수 있다. 이제 도착한 다음에 상대 말의 y좌표를 살펴보자. y좌표가 음수라면 (0, 0) ~ (0, n)을 잇는 선을 따라 쭉 먹을 수 있고, 양수라면 (0, 0) ~ (n, -n)을 잇는 선을 따라 쭉 먹을 수 있음을 알 수 있다. 그렇게 먹은 다음에는 다시 선을 타고 내려와서(또는 올라와서) 선을 하나 더 그어주면 육각형의 1/3만큼을 내가 차지할 수 있다.

그런데 이 전략을 로컬에서 돌려보면 5000게임을 이기기 전에 진다. 지는 케이스에 대해 상대가 어떻게 움직였는지를 살펴보면 내가 선을 다 긋기 전에 내 땅 안으로 상대가 들어왔다는 것을 알 수 있다. 이를 해결하기 위해서 육각형 1/3짜리를 다 먹는 게 아니라 한 1/4 정도만 먹도록 해서 선 긋는 시간을 줄이면 상대가 뚫고 들어올 확률이 낮아져서 5000게임을 다 이길 수 있다.

J : 구현이 좀 귀찮은 듯한 기하. koosaga가 잡고 말렸다. Editorial을 까보니까 무려 tourist가 낸 문제였다..

K : 모름

L : 모름

M : 모름

N : 모름

O : 모름