5월 2주차 Weekly PS

• Google Codejam 2021, Round 2
• [Virtual] Google Codejam 2018, Round 2
  • Falling Balls
  • Graceful Chainsaw Jugglers (small)
  • Costume Change

May 10 - May 17, 2021.

Google Codejam 2021, Round 2

PS를 시작하고 세 번째 Codejam이다. 처음으로 Round 3에 진출하고 Codejam 티셔츠를 얻었다.

순위는 855등으로, 거의 막차를 탔지만 아무튼 티셔츠를 받았다는 사실이 매우 고무적이다 (?)

나름대로 중요한 대회이므로 별도로 포스팅하기로 한다.

[Virtual] Google Codejam 2018, Round 2

Codejam을 대비하기 위해 영원한 팽도리들 dhdroid, dlwocks31 과 함께 2018 Round 2를 virtual로 돌았다. 많은 부족함을 느꼈다.

Falling Balls

나름대로 재밌는 Greedy construction 문제이다. 먼저, /과 \에 대한 조건으로부터, 시작하는 공들이 교차해서 움직이지 못함을 관찰하자. 그러고 나면 결국 왼쪽에서 $k$번째라는 공의 상대적 위치가 잘 보존되므로, 어느 공이 어디로 가야 하는지를 정확하게 안다. 이를 맞추어 construct하기는 어렵지 않다.

Graceful Chainsaw Jugglers (small)

$O(n^4)$ 의 자명한 DP를 이용하여 small을 긁었고, 어떻게든 이를 줄여보려고 이리저리 많은 고민을 했지만 성공하지 못했다.

끝나고 dhdroid 의 솔루션을 들었는데, DP의 차원을 줄이는 아이디어가 상당히 매력적이다. 뭔가 형태적으로 자주 보이는 DP인 듯 함에도 떠올리지 못한 점은 좀 아쉽다. 풀이에는 $O(n^{8/3})$ 의 놀라운 풀이가 적혀 있으나, $O(n^3)$ 도 문제 해결에 아무런 지장이 없고 훨씬 떠올리기 쉽다.

Costume Change

중요한 포인트 하나는, 사실 색깔은 충분히 많다는 것이다. 즉, 현재의 ‘특별하지 않음’ 이라는 이슈만 resolve하면 된다.

어떤 $n \times n$ 그리드 상에서, $k$개의 점들이 놓여 있을 때, 이중의 subset을 스도쿠스럽게 뽑는 방법 (각 행에 하나, 각 열에 하나 이하를 유지하는 방법) 은 비교적 well-known이다. 행을 표현하는 정점 $n$개와 열을 표현하는 정점 $n$개를 만들고, $(i, j)$ 에 점이 놓여 있음을 $r_i \to c_j$ 간선으로 표현한 다음, 이들간의 maximum bipartite matching을 찾으면 된다. 이것만 찾는 방법은 좋은 방법이 많이 있지만, 무지성 플로우가 가장 쉽게 구현할수 있다.