Petrozavodsk Winter 2019 간단요약

뭐 했는지만 대충 알 수 있는 수준의 짧은 요약글로 정리하려고 한다. 다 쓰면 너무 길다.

Day1

• A: NEERC 2018 B랑 매우 비슷한 General Matching.
• D: 특수한 그래프에서 weighted bipartite matching을 빠르게 계산하는 문제. weighted bipartite matching은 가중치가 큰 순서대로 에지를 추가하면서, 최대 매칭을 증가시키는 것만 넣어주는 식으로 계산할 수 있다. 이렇게 가중치를 없에고 최대 매칭 문제로 환원하면, ARC076F / POI Ice Skates 에 나온 유형처럼, 홀의 결혼 정리 + Segment Tree 로 해결 가능. 사실 생략한 아이디어들이 이것저것 있는데 다 적으면 너무 길어지니 생략.
• E: planar graph에서 random walk를 할 때 n번 정점에 도달하는 시간의 기댓값. $n \le 3000$. 평면 그래프이기 때문에 적당한 행 순서를 잡아 가우스 소거법을 하면 될 것이라 생각하였으나 실패했다. 이런 식의 접근 방법이 의도된 것 같긴 하지만, 계산이 실수를 구하는 것이 아니라 mod p field에서 진행되는 것이라 Black Box Linear Algebra를 사용하면 쉽게 해결할 수 있었다. 나중에 안 사실인데, 적당한 행 순서를 잡아서 가우스 소거법을 하는 방식으로 쉽게 풀리는 문제가 WF 2014 Pachinko라고 한다.
• G: 이해 불가능한 Lemma가 있었다. 이 Lemma를 사용하면 partition number를 계산하는 문제로 환원되고, 이는 Pentagonal Number Theorem으로 $O(N^{1.5})$ 에 된다고 한다 ㅎㄷ
• H: graph를 construction해야 하는 문제. 그래프가 특정한 제약 조건을 만족한다고 생각해도 문제에서 원하는 그래프를 전부 만들 수 있음을 알… 수는 없다. 전혀 비직관적인 제약 조건이라 그게 된다는 게 이해가 안되지만, 아무튼 제약 조건을 만족하는 그래프는 DP로 쉽게 전부 열거해 볼 수 있고, 모든 입력에 대해서 그 DP 테이블이 다 차는 것은 돌려보면 알 수 있다 (…) construction 문제는 구데기니 걸러야 한다는 사실을 배웠다.
• J: APIO 2014 Sequence와 동일한 문제라는 것을 최소반례를 가정한 귀류법 (즉, 수학적 귀납법?) 으로 증명할 수 있다. 이를 $O(N\log N)$ 에 풀어야 한다. 여기까지 들으면 잘 알려진 Aliens trick + CHT 라고 생각하겠지만 역추적이 안된다. 하지만 당신은 할 수 있다. 비용 함수가 monge라는 성질만 사용해도 증명할 수 있다. 더 이상의 자세한 설명은 생략하고, 궁금하면 내 olympiad github에 있는 apio14_sequence_nlgn.cpp 를 참고.

Day2

• A: weighted cactus graph가 주어졌을 때, $flow(x, y)$ XOR $x$ XOR $y$ 의 합을 모든 $1 \le x < y \le N$ 에 대해서 구하는 문제이다. 대회 때 식이 너무 못 생겨서, 그리고 못 생긴 풀이밖에 생각이 나지 않아 풀지 못했다. 하지만 알고 보니 깔끔하고 쉬운 문제였다. cactus graph의 한 사이클을 거쳐 흐르는 flow를 생각해 보았을 때, 이 중 하나는 사이클 전체에서 용량이 최소인 간선을 따라 흐를 것이다. 고로, 이러한 flow에 대해서 용량 최소인 간선은 항상 쓰인다. 이는, 이 용량 최소인 간선을 항상 쓰인다고 가정하고 없앤 후, 대응되는 사이클의 간선들에 이 간선의 용량을 더해주면, 트리가 생기고, 이 트리의 max flow와 cactus의 max flow가 같다는 것을 뜻한다. 이제는 구간 최솟값이니 비트를 쪼개서 풀어주면 됨. 이 문제는 tourist도 못 풀었고 솔루션이 대회 초중반을 거쳐서 한번도 안 나온 문제이다. 아이디어가 크게 어렵지 않은데, 식이 대놓고 못 생기면 겁을 먹는게 본성인 것 같다.
• G: 입력이 랜덤이라 랜덤으로 뚫었는데, 알고보니 sparse table을 사용한 깔끔하고 아름다운 deterministic solution이 있었다.

이 외 대부분의 문제들은 알 가치가 없었다.

Day3 (MSU Red Panda Contest)

이 때는 쉬운 문제밖에 못 풀었고, 풀이 설명도 듣지 못해서, 딱히 후기를 쓸 문제는 없고 업솔빙할 문제만 가득하다...

• A: should upsolve
• F: should upsolve. 안 읽었는데 별로 어렵지 않다고 들었다.
• G: should upsolve. Link-cut tree.
• H: should upsolve.
• K: should upsolve.
• M: 신기한 문제. 플레이어의 전략은 각각의 노드에 대해서, 여기서 움직일지 멈출지를 결정하는 이분법적 선택이다. 이렇게 보면 플레이어의 가능한 전략은 $2^N$ 개 존재한다. 하지만, 각 시작점에 대해서, 왼쪽에 있는 가장 먼저 멈추는 위치와, 오른쪽에 있는 가장 먼저 멈추는 위치가 같은 전략들은 모두 동등한 전략으로 취급된다. 고로 각 시작점에 대해서 가능한 전략이 $O(N^2)$ 개 존재한다. 기댓값 식을 써 보면 기하학적 접근이 가능함을 알 수 있고, $O(N)$ 에 해결할 수 있다. USACO Dec18 P1과 너무 비슷해서 쉽게 풀었다. 사실 Red Panda Contest가 오리지널이다 (...)

Day4

사실상 Combinatorial Optimization Contest였던 거 같다 (..)

• C: LR max flow.
• D: Matroid intersection. (Linear independence + Partition)
• E: Caratheodory Theorem의 증명과 비슷하게 시뮬레이션하면 되는 문제인것 같다. 업솔빙할 때 계속 틀렸는데 난 실수오차 문제라고 믿는다 (…)
• F: Planar graph의 max cut을 구하는 문제. max cut은 max bipartite subgraph이다. 평면 그래프가 bipartite하면, 이 그래프의 Dual은 Eulerian이다. max eulerian subgraph는 chinese postman problem과 비슷한 방식으로 weighted general matching을 사용하면 구할 수 있다.

Day5 (GP of Gomel)

• A: 문제는 짧지만 풀이는 정말 복잡하다. 첫번째 단계는 FFT를 사용해서 어떠한 다항식을 구해야 하고, 이렇게 힘들게 구한 다항식에 대해서 $F(x_1), F(x_2), \cdots, F(x_q)$ 를 전부 빠른 시간에 구할 수 있어야 한다. 결국 다항식에 값을 대입하는 것은 $(x - x_i)$ 로 나눈 나머지를 구하는 것과 같으니, Polynomial Division 코드가 있으면 $(x - x_i)$ 다항식을 노드로 하는 segment tree를 만들어서 문제를 $(Q+N)\log^2 N$ 에 해결할 수 있다. 이렇게 하면 한 반쯤 왔고, 이제 centroid decomposition과 몇가지 조합 카운팅을 몇번 더 해주면 됨. 총 400줄 (9KB) 짜면 AC. 업솔빙할 때 정말 짜릿했다.
• B: 그냥 설마 안될까 싶은 그리디가 된다. 그런데 제한이 100이고 푼 팀이 별로 없으면, 나이브가 $O(n \log n)$ 인 그리디를 별로 하고 싶지 않아질거다.. 그렇게 겁을 먹으면, 가정을 조금 덜 한 $O(n^3)$ DP를 짜서 맞게 된다. 
• C: should upsolve.
• D: 투어리스트 이런거 좀 그만 냈으면...
• H: 정해는 구데기였는데, 100개씩 끊어서 미리 탐색해놓고 범위를 줄이는 별해가 재미있었다.
• I: tournament graph에서 위상 정렬 순서를 찾으면 풀 수 있는 문제인데 (SCC 안에서는 자유롭게) 놀랍게도 $O(n\log n)​$ 에 단순 merge sort를 사용해서 찾을 수 있었다. 정말 재밌고 충격적이었던 문제.

Day6 (GP of Belarus)

• C: binary search inside of parallel binary search.
• D: 대회때는 사전 지식일 거라고 생각하여 잡지 않았으나 아주 좋은 풀이가 있었다. XOR 쿼리는 쉽고, OR / AND 쿼리는 두 트리를 합치는 연산에 대응된다. 트리 합치기는, 작은 것 큰 것의 요령을 사용하면, 새로 생기는 node의 개수에 비례하는 시간에 전부 합쳐줄 수 있다. 빈 트리를 합치려고 시도하면 시간 복잡도가 깨지기 때문에, 각 depth마다 비지 않은 트리들을 저장하는 Queue를 만들어 주어야 한다.

Day7

• B: construction 문제. 뭔 개똥같은 이상한 생각 열심히 하고, 그 생각이 맞는지 아닌지를 논리적으로 검증하는 게 아니라 백으로 검증한 다음에 맞으면 그걸로 후보 줄이고, 이거 반복해서 이상한 제약조건 6~7개 찾고, 그걸로 문제 내고, 이제는 내 사고로는 이해 불가. 
•  I가 (그리고 I만) 관심이 가는 문제였던 것 같다. 두 문자열 s, t 에 대해서, s 가 t의 부분문자열이거나 반대가 성립하면 두 문자열 쌍은 "비교 가능"하다. 문자열 $S$가 주어졌을 때, 모든 부분문자열의 집합에 존재하는 서로 다른 두 쌍 중, 비교 불가능한 쌍의 개수를 세어야 한다. $|S| \le 10^5$.

Day8

모든 문제가 쓰레기였으나, 반성할 거리가 있었다.

Day9

모든 문제가 쓰레기였다.