티스토리 뷰

공부

Petrozavodsk Winter 2019 간단요약

구사과 2019. 2. 18. 16:31

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

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

모든 문제가 쓰레기였다.

'공부' 카테고리의 다른 글

APIO 2019  (0) 2019.05.27
Berlekamp-Massey 알고리즘  (9) 2019.05.27
Petrozavodsk Winter 2019 간단요약  (0) 2019.02.18
더불어민규당 Petrozavodsk 2019 Winter 직전 연습  (0) 2019.01.26
Linear Programming Duality  (0) 2019.01.21
더불어민규당 2019년 신년 연습  (1) 2019.01.15
댓글
댓글쓰기 폼
공지사항
Total
454,711
Today
0
Yesterday
408