2018.11.02 problem solving

리저널 전 연습 기록을 간단하게 적는다. 정말 간단하고 부실하게 적을 예정이다.

10/23 화요일

NEERC Southern Subregional 2018을 돌았다. 12/13으로 만족스러웠다.

• H는 처음 보고 복잡하게 생각했으나 알고 보니 쉬운 문제였다.
• J는 재밌는 냅색 문제였다.
• I는 쉬운 매칭인데 우리가 무식해서 엄청 돌아갔다.
• L은 못 풀겠어서 답이 2 이하라고 찍고 gaussian elimination을 돌렸다. 다행이도 맞았다. 알고보니 내가 옛날에 풀었던 POI (Two Parties) 였는데 대회 중에는 전혀 눈치 못챘다. 일찍 슥삭할 수도 있었는데 매우 아쉬웠다.
• M은 모르겠다.

10/24 수요일

기하 연습을 했다.

• A는 제한을 보고 당연히 N^3일 줄 알았는데 안 적혀있는 T가 매우 많았다. 그래서 TLE를 많이 받았다. 화가 났다.
• I는 문제를 뒤집어서 생각하면 보기보다 쉬웠다.
• H는 대회 끝나고 15초 뒤에 맞았다. 또 화가 났다. 그래도 dual graph 구성 + segment intersection 류 스윕을 짜는데 자신감이 생겼다.

10/26 금요일

Asia Tokyo Regional 2014을 돌았다. 8/11의 성적을 받았다. 난 잘한 거 같은데 사람들이 나보다 더 잘해서 성적이 낮았다.

• A: N^2를 짰다. 짜는 데 좀 헷갈렸다.
• F: There is no alternative. MlogM에 절선을 짜는 게 제일 빠를 것 같아서 그렇게 했다.
• D: 미적분 + 물리는 앞으로 수찬이가 담당하기로 했다.
• G: 딱 떠오른 건 로그제곱이었으나 TLE 날 것 같아서 로그 생각하고 짰다. 근데 로그제곱이 잘 되는 거 같다. 😡
• I: 아주 재밌게 푼 문제. 답에 대해서 이분 탐색을 하면 (다른 사람들 코드를 보니 필요 없는 것 같지만) 두개의 추가 인자가 들어가는 boolean dp가 나온다. 게임에 대한 관찰을 더하면, 큰 쪽 인자에 대해서 답이 모노톤함을 알 수 있다. 이 구간을 반환값으로 빼주면 simple dp.
• H: pole을 원, 로봇을 점으로 뒤집어 주자. 로봇의 움직임은 원호를 따라가거나 두 원의 접선을 타고 가거나, 둘 중 하나이다. (엄밀하게 증명하라면 모르겠다.) 그렇게 하면 고려해야 할 점이 전체 평면에서 별로 없어서, 이들로 visibility graph를 만든 후 다익스트라. 구현은 고통스러운 기하였고, 실제로 맞기까지 아주 힘들었다. 대회 시간 안에 풀지 못했고 예제를 매우 열심히 디버깅해서 겨우 AC. 삼각함수 실수였고 3글자만 고치면 됐었다. 그 3글자를 찾을 수 없는 게 문제지 ㅠㅠ 그래도 풀고 나니 기하 자신감이 조금 생겼다.

대회 중에는 H 때문에 시간이 밀려서 JK를 시도할 수 없었다. K의 정해를 보고, 어렵지 않은 풀이를 생각한 후 그걸 가능한 가장 복잡한 방법으로 꼬아서 낸 문제라는 생각이 들었다.

10/27 토요일

NCPC 2018을 돌았다. 10/11의 성적을 받았다. 적게 풀린 문제들인 A F G 에 대해서 적어보았다.

• G는 보자마자 Vizing임을 깨달았다. 그래서 기분이 좋지 않았다. 팀노트에 비징이 없기에 풀 수 없었다. 그래프가 특수해서 construction이 있을 법도 하다 느꼈고, 실제로도 있었으나, 대회 도중에 다른 거 대신 하는 것이 좋은 선택이 아니라고 생각했다.
• F는 기하 문제였다. 직선을 고정시키면 문제를 O(nlogn)에 풀 수 있었다. 좀 갖고 놀다 보니 좌표 압축으로 나온 격자점의 쌍을 다 해보면 될 거 같았고 O(n^5logn) 알고리즘을 찾았다. 근데 WA. 그렇게 맞왜틀을 하다가 반례를 찾았다. 한 꼭지점을 지나는 직선이 있을 수 있다는 것이다. 이 직선의 후보가 n^3개인데, 여기서 문제점은 이 직선의 후보를 안다고 직선을 specify하는 게 쉽지 않다는 것이다. 다행이도 미적분 담당 수찬이가 closed form을 찾아줘서 이것도 성공. 근데 TLE. n <= 15라 예상도 못했는데 뭔가 느린 것 같았다. 그래서 그냥 직선을 random shuffle한 후 1.9초까지 돌려보는 타임커팅을 냈고 AC. 나중에 다시 생각해 보니까 좌표압축 격자점 쌍을 볼 필요가 없이 주어진 4n개의 점만 해주면 돼서 후보가 n^3개였다.
• A는 그리디한 관찰을 하고 냅색이 된다는 믿음을 가지면 된다. 결론적으로 10^8 단위에서 냅색을 시키는 구데기 문제였다.

10/28 일요일

Asia Tsukuba Regional 2017을 돌았다. 2014를 잘 못해서 기대 안했는데 무려 10/11을 했다.

• E는 간단한 그리디를 생각했는데 틀린 알고리즘이었다. 그래서 말릴 뻔했다. 다행이도 그리디의 관찰을 사용한 n^2 dp 풀이가 있었고, monotone queue를 써서 한 항을 빠르게 구하면 해결.
• J는 내가 안 풀었는데 좋은 문제. 가장 깔끔한 해석은 이것이라고 생각한다. 같다는 relation을 그래프로 이어주자. 한쪽 구간은 겹치지 않으며 이 구간에서 왼쪽에 있는 수로 답이 이어진다. 즉, 한 수에 연결되어 있는 여러 relation을 고려했을 때 왼쪽의 수를 specify하는 relation은 하나밖에 없다. outdegree가 최대 1인 사이클 없는 방향 그래프이다. 트리의 모습을 띈다. 해당 트리의 루트의 위치를 O(구간 갯수)에 구할 수 있다. union find와 비슷하게 루트에 대해서만 정보들을 관리해주면 전체적인 정보를 전부 유지할 수 있다. 위치에 대한 canonical representation을 찾는다는 것이 풀이의 서술 방식이었다. 좋은 표현이다.
• K는 내가 풀었고 좋은 문제. 사이클에 무조건 들어가는 백엣지 set을 고정시키고 생각해보자. 여기에 더해서 simple cycle을 만들 수 있는 트리 간선 subset을 고르는 문제이다. degree 2를 맞춰줘야 하니까, 이제 리프에 대해서 귀납적으로, 쓸모 있는 간선인지 아닌지를 판별할 수 있다. 이를 구현하면 O(N2^16). 트리 압축테크닉을 써서 최적화하면 O(16*2^16). ontak 2015 lampy 문제가 생각났다. 아이디어의 방향성이 달라서 그 문제보다는 구현량이 훨씬 적다.
• D 문제는 점을 두개 빼서 남은 점의 convex hull perimeter를 최소화하는 문제. 옛날 경기과고 수행평가에 하나 빼서 넓이 최소화 하는 문제를 출제한 적이 있었다. (Stop Making Sense) 그래서 그 문제의 풀이는 익숙했다. 두개 뺀 경우에서 그 풀이를 그대로 적용하면 N^2일 것처럼 보인다. 하나의 점을 제거하면 여러 점이 컨벡스 헐에 추가될 수 있기 때문이다. 하지만 새로 추가된 점에 대해서만 같은 루틴을 사용하면 NlogN 정도에 된다. 안 될것 같지만 계산해 보면 그랬고 좀 놀라웠다. 실제 구현은 복잡하다. 안 쓴 케이스들이 꽤 있고 모두 서로 다른 코드를 써야 하기 때문이다. 하지만 짜면 매우 뿌듯하다. 구현을 매우 강력히 추천하는 문제이다.
• H 매우 어렵다. 풀이 봤는데 전혀 이해 안감... 공부해야 한다.

10/30 화요일

Northern Subregional 2017을 돌았다.

D: 민규가 굉장히 그럴듯한 그리디를 짜고 틀렸다. 내가 봐도 맞는 거 같은데 왜 틀린지 모르겠다. ㅋㅋ

E: 좋은 그리디 문제. 그래프로 환원하면 쉽다.

F: 난 손 안 댔는데 우리 팀이 많이 말렸고(디스크립션을 한 두번 정도 잘못 읽음) 꽤 많은 시간을 넣었지만 끝까지 풀지 못했다. 그리고 끝난 후 15분 뒤에 풀었다.

G: 내가 손을 댔고 말아먹었다. 민규가 빠르게 풀이를 찾아서 구현했는데, BCC 구현을 묘하게 잘못했고, 긴 코드를 디버깅하는 과정이 쉽지 않았다. 결국 찾는데 한시간 반. BCC 코드를 잘 이해하지 못하면서 너무 성급하게 응용한 게 문제.

J: 양수/음수 항을 떼어주면 2차원 기하 문제 비슷하게 된다. 구간에 있는 점을 고정된 벡터만큼 이동시키고, $ax+by$를 최소화하는 값을 구한다. 이는 몹시 어려운 문제지만, 제한이 작아서, 대충 $O(n^{1.5}\log n)$ 버킷을 짜면 된다. 하지만 FG때문에 짤 시간이 없었다. 이건 끝나고 1시간 뒤에 풀었다.

10/31 수요일

기하 연습을 돌았다.

A: 아기 석환 💖

G: 비밀 요원과 비슷한 segment intersection 류 스윕. 제약조건이 이것 저것 붙어 있어서 쉽게 풀 수 있다.

I: 결론적으로, 직선과 convex polygon이 strict하게 교차하는 지를 판별하는 문제로 환원할 수 있다. 내가 생각했던 방법은 strictly가 아니면 쉬우나 그렇지 않으면 매우 복잡해져서 여러 케이스 처리가 필요했다. 결국 WA를 많이 받고 풀지 못했으나 종원이형이 아주 간단한 방법을 소개하였다. Convex polygon에서 임의의 변을 잡고, 해당 변의 시계방향에 두 직선 점이 모두 있는지를 판별한다. 만약 그렇다면 무조건 교차하지 않는다. 이를 모든 변에 대해서 하자. 이제 반대로, polygon이 선분이 이루는 직선을 기준으로 한 사이드에 전부 있는지를 판별하자. 그렇다면 no, 아니면 yes. 이 알고리즘을 그대로 응용해서, 두 convex polygon이 strict하게 교차하는지도 쉽게 판별할 수 있다 ($O((n+m)\log(n+m))$에!)

K: 푼 줄 알았는데 사풀이었다. 그래서 망함.

11/2 금요일

오전: Jakarta 2017

카페에서 했는데 엄청나게 혼란스러웠다. 전날에 다같이 술을 좀 많이 마시고 아침에 카페에서 했는데, 프린터 없고 스코어보드도 없고 너무 많은 것이 없었다 (...) 그래서 문제 푼 순서도 엉망이었고, 초반에 별 별 멘탈 나가는 일이 많이 있었다. 극적으로 후반에 복구해서 11/12 1866min으로 마무리. 생각보다 대회 스코어보드가 많이 낮아서 기분이 좋았다 (?)

문제는 전반적으로 무난했으나 구데기성이 좀 있었다. 월파 생각났다.

• B: 처음에 읽고 Dynamic Shortest Path인 줄 알았다. 그리고 충격에 빠졌다. 물론 완전히 잘못 읽은 거였음. ㅠㅠ.
• C: 민규가 옆에서 화를 많이 냈다.
• E: 하노이탑과 비슷한 관찰을 하면 단순 구현... 이라고 생각할 수 있으나 문제에서 C를 준 방식 때문에 sequence가 유일하지 않다. 다행이도 여기에 DP를 적용할 수 있다. 그 이후 몇가지 (왜 시키는지 모르겠는) 구현을 더하면 AC
• G: BOI 2016 Park와 같은 간단한 dual graph 문제라고 착각할 수 있으나 현실은 빡센 기하. 가장 힘든 점은 실수 오차 tolerance가 0이라는 것이다 😡
• H: 트리 압축 (요즘은 사골)

오후: OnionPringles + jihoon + koosaga 연습

• A: Store-Keeper라는 문제가 기회의 땅에 있었다. 당시 제한이 100 * 100이었고, naive한 풀이가 n^4인데, 될지 안 될지 모르겠어서 선형 시간에 풀었던 문제이다. 그 기회의 땅 문제 제한을 1500 * 1500으로 늘리고 쿼리를 추가한게 이 버전이다. 그래서 그냥 당시 짠 선형 시간 코드를 복붙했다. 일반적인 그래프 탐색 알고리즘을 사용하면 쿼리 때문에 문제가 특별히 어려워지는 일은 없다.
• B: 선물을 받는 사람들은 입력에서 prefix를 이룬다. prefix의 마지막 원소가 선물을 받으려면, 그 원소 앞에 prefix 맨 뒤로 가는 친구가 최소 1명 있어야 한다. 아니면 안 밀려서 선물을 받을 수가 없다. 그 다음에 맨 뒤 혹은 그 앞에 가는 친구가 (아까 포함) 2명 있어야 한다. 아니면 그 앞으로 못 간다... 이를 반복하면 필요 조건이 나온다. 그리고 이것이 충분하다. 저건 정렬로 체크 가능하고. Prefix 길이에 대해서 binary search하면 해결. 로그 제곱인데 아마 선형 시간도 될 듯.
• D: 두 조건을 모두 만족하는 영역이 각 row마다 interval의 형태를 띈다. 이를 관찰하면 간단한 N^2 풀이를 찾을 수 있다. 시작점과 끝점이 모두 단조적이기 때문에 부분합을 사용해 최적화 할 수 있다. 쉬운 문제였으나 오래 걸렸다.
• E: 팬이에요
• FG: F는 쉬운 트리DP고, G는 쉬운 트리dp를 n번 하면 n^2라 시간 초과이다. 난 잘 모르겠다. ㅠ
• HI: 주어진 제약 조건을 Min Cut의 형태로 formulation할 수 있다. A_i 가 양수 / 음수인 건 적당한 수식 전개로 처리.

11/3 토요일

오전: 서울 리저널 2018

더 이상의 자세한 설명은 생략한다.

새벽: ainta와 Codechef Snackdown Elimination

• Nearest Angle: 빡구대기문제
• Strange Transform: 편의상 A를 무한 배열로 생각하자. 간단한 귀납법으로 $f^{2^k}(A)_x = A_x$ XOR $A_{x + 2^k}$ 임을 보일 수 있다. 이를 사용하면 $O(NQ)$ 풀이를 유도할 수 있음. 대략 $[X, N]$ 구간을 돌면서 $i$ 가 $K$의 submask인 모든 $A[i + X]$를 XOR하는 문제임을 알아낼 수 있다. 이를 sqrt decomposition을 통해서 줄일 수 있다. 모든 $X \leq N, K < 2^8$ 에 대해서 $i$ 가 $K$의 submask인 모든 $A[i + X]$의 XOR을 전처리해두자. DP 비슷하게 할 수 있다. 쿼리가 들어올 때마다 모든 submask를 나열할 필요는 없고, 마지막 8비트는 켜 놓고 나머지 10비트에 대한 submask만 나열해주면 된다. 그러면 1024번의 연산으로 해결. 시간 복잡도는 $O(QN^{0.5})$.
• Painting Tree: DP를 통해서 해당 트리에 $K$개의 Disjoint Path를 놓는 경우의 수 $F_k$ 를 계산할 수 있다 (단순히 하면 $O(N^3)$ 이지만 이 문제의 풀이와 같은 방법을 통해서 $O(N^2)$로 줄일 수 있음). 그러면 모든 가능한 상태 중 $K$개의 Disjoint Path까지 성공적으로 놓은 상태의 개수는 $F_k \times k!$ 임을 알 수 있다. 그렇다면 우리가 $K$ 이상의 답을 받을 확률은 $F_k \times k! \times (\frac{1}{\binom{N+1}{2}})^k$ 이다. 기댓값의 선형성에 의해 답은 이러한 확률들의 합이다. 풀이를 듣고 보면 어려운 내용이 하나도 없으나, 의외로 생각하기 굉장히 까다로운 신기한 문제이다.