2020.02.25 problem solving

Grand Prix of Gomel

Ptz Winter 2020 Gennady Korotkevich Contest 5이다.

kdh랑 같이 했다. 문제들이 너무 수학적 성향이 강해 내 취향은 아니었다.

• B: online FFT 테크닉으로 된다는데, 그 online FFT가 그냥 분할 정복 같아서 차라리 G 말고 이걸 할까 하는 후회가 있었다. 뭐 분할 정복을 시도 안 해 본 건 아니지만.. 300iq가 웃긴 풀이를 알려줬는데, $n + k$ 개의 결과를 $2n+k$ 개의 결과로 확장하는 방법이 있다. $2n+k$ 각각의 계수는 (self-convolution) + ($[x/2, x/2+k]$ 근처에서 튀어나온 계수 몇개 제거) 정도로 구할 수 있다. 우항은 $n+k$ 개의 결과가 있으면 $O(nk)$ 에 찾을 수 있다. 그러면 대충 식이 $P(x) = xP(x)^2 + C(x)$ 같이 나온다. 근의 공식을 풀어주면 $P(x) = \frac{1 + \sqrt{1 - 4C(x)}}{2x}$ 가 된다. 다항식에는 $O(n\log n)$ 시간에 sqrt를 취해줄 수 있으니 $O(nk + n\log n)$ 풀이가 완성된다.
• C: 어려운 문제는 아닌데, suffix array 초기화 잘못해서 +6 ㅠㅠ 내가 돌릴때는 채점 서버도 이상해서 고생을 많이 했다.
• G: F 풀고 1시간 남았을 때 kdh가 매칭 문제라고 알려줬다. 이분 매칭도 아니고 일반 매칭이라서 이걸 직접 구할 시도는 전혀 안하고, 구성적인 풀이를 계속 고민했지만 실패했다. 시간 제한이 5초고 입력으로 가능한 경우의 수가 작았는데 눈치를 못 챘다.. 아무튼 의도한 풀이는 blossom을 돌리면 그냥 잘 나온다였다. 짜증 팍 대회 후 toosimple이 이 문제의 constructive solution에 대한 굉장히 방대한 자료를 들고 왔는데, 시간이 남으면 공부해 보면 좋을 것 같다.
• H: 괜찮은 문제 같은데 업솔해야 한다.
• K: longest substring 길이가 최대 $X$ 인 경우 부분합 사용하여 $O(nm)$ DP를 할 수 있다. 고로 각 쿼리에 대해 $X$ 를 대충 구해준 후 $X$ 에 대해서 $O(nm)$ DP를 돌리는 $O(max(n,m) nm)$ naive 풀이를 생각할 수 있다. $X$ 는 이진 탐색으로 해도 되고, 정말 대충 구해도 된다. 한편, wlog $n < m$ 을 가정하면 $n$ 이 $m/X$ 근처에 있을 수 밖에 없다는 것을 알 수 있다 ($X$를 구할 수 있으면 이 사실이 명확할 것이다). 이 bound를 구해주면 naive 풀이를 그냥 돌려줘도 $\sum O(nm/X) = O(nm \log max(n, m))$ 정도가 되어서 문제를 해결할 수 있다. bound는 명시적으로 구해줄 필요가 없다. 그냥 longest substring 길이가 $X$ 인 쿼리들 중 $x, y$ 의 전체 최댓값을 취하면 되기 때문이다.

JAG Summer Camp 2018 Day2

• D: CF Goodbye 2014 F, USACO Mowing Mischief와 같이 monotone한 구간 집합을 두 개의 prefix/suffix로 쪼개는 트릭을 사용하면 해결할 수 있다.

• E: 백트래킹 돌리면 보인다

• F: 토했다

• G: Stern-brocot 류 Fraction finding 도구를 100번 정도 김치에 싸먹는 별로 알기 싫은 풀이가 정해일 줄 알았으나, rkm이 복잡한 도구를 전혀 사용하지 않는 멋진 풀이를 알려줬다. 이 지면에 쓰기에는 너무 긴 풀이지만 아무튼 그의 수학 실력에 박수를.

• H: 괜찮은 문제

• I: Restore가 없으면 수열과 쿼리 19와 똑같이 풀면 된다. 수쿼19의 일반적 풀이는 Segment tree beats일 텐데, restore가 퍼텐셜을 작살내서 이대로 하면 시간 초과가 나게 된다. 사실 수쿼19와 다르게 합이 아니라 최댓값만 묻는다는 것을 이용해서, amortization을 안 쓰고 순수 lazy propagation으로 풀리게 수정해주면 맞을 수 있다. 그래서 중요한 건 lazy propagation을 어떻게 관리하느냐일 것이다. 왜냐면 lazy propagation을 쓰려면 적당히 작은 두 함수를 합쳐서 계속 작은 함수가 유지되도록 해야 하기 때문이다. 대략 $f(x) = \lfloor \frac{x + b}{c} \rfloor + d$ 같은 꼴을 쓰면 된다고 하는데, 이야기 들어보면 그렇게 마냥 간단하지는 않고, 고민을 좀 해야 하는 것 같다.

• J: A를 위로, B를 오른쪽으로 하는 lattice path를 그리면, 대충 $f(s) = \max_{i = 0}^{|S|} (countA[0:i] + countB[i:|s|] - 1)$ 정도의 식이 나온다. 엄밀히 증명은 안 했는데, 문제에서 앞에 B/A를 붙이는게 곤란한 케이스를 없애 주는 것 같아서 그냥 했다. 어쨌든 저렇게 하면 $O(QN)$ 이 되고 lazy propagation으로 쉽게 $O(N + Q\log N)$ 으로 줄일 수 있다.

• K: LIS의 길이가 2 이하인 순열의 개수는 $Catalan(n)$ 이다. 정당화는 대략 다음과 같다. LIS의 길이가 2 이하면 순열을 $p_i = i$ 인 diagonal 아래/위로 분리할 수 있는데, 이 위 아래는 각각 increasing sequence를 이륜다. 또한, 위쪽에 있는 increasing sequence를 고정시키면 아래쪽에 있는 increasing sequence가 정확히 하나로 결정된다. 고로 위쪽에 있는 increasing sequence의 개수를 고정시켜야 하는데, 이 increasing sequence는 대각선 아래를 지나지 않는 lattice path에 일대일 대응되기 때문에 (우회전하는 지점에서 순열 원소를 추가하자) 우리가 아는 카탈란 수랑 같은 값이 나온다.

  이제 $P(a) = b$ 조건을 넣어야 하는데 이것은 lattice path가 $(a, b)$ 에서 우회전한다는 뜻이다. 이렇게 되면, diagonal 아래를 지나지 않으면서 $(x, y)$ 지점을 도달하는 경우의 수를 찾는 문제로 환원된다. 이것은 엄청 쉽게 $O(n^2)$ 에 구해줄 수 있다. 그런데 $O(n)$ 은 쉽지 않다. 생각해 보니 나는 diagonal 아래를 지나지 않는 lattice path가 왜 카탈란개인지 모른다. 그 자리에서 증명을 하기도 뭐해서 DP 짠 후 규칙을 돌렸다. 대충 훑어보니 소인수들이 작아서, 그냥 적당한 일차함수들의 곱이라고 생각했다. 그래서 식이 간단하고 $(x, x)$ 에서 $\frac{1}{x+1} \binom{2x}{x}$ 이 나오는 걸 여러 개 시도해 봤는데 규칙과 맞는 함수가 하나 있어서 제출했고 AC. 이렇게 말하면 대충 해서 금방 찾은 거 같지만 사실 엄청 힘들고 오래 걸렸다.

Codeforces Round 621

Hash Code 2020 Qual

kriii, kdh9949, nong와 함께 78-9 팀으로 참가하였다. 한국 1등 전체 38등으로 세계 대회에 가는 것이 확정적인 줄 알았으나 nong님이 "매년 참가팀수 줄이던데 올해 30명으로 줄지 않을까여" 라고 하셔서 잔치 분위기가 확 깨져버렸다 (...) 아무튼, 본선 진출할 수 있었으면 좋겠다.

• A는 작은 예제로, kriii님이 손으로 푸셨다.
• B는 simple greedy가 되는 special case로 내가 풀었다. 여기까지가 휴리스틱 없이 되는 쉬운 입력들.
• 초반 어떤 시점에서, "현재 시간에서 signup time 당 score 성능비가 제일 좋은 걸 반복해서 뽑는" 그리디를 고안했고, 고득점을 받으면서 26만점대에 진입했다. 그 이후 C를 제외한 모든 솔루션이 저 그리디를 근간으로 작동한다.
• C는 저 그리디가 나오기 이전부터 크리님이 멋진 힐 클라이밍을 짜서 돌렸고 나름대로 고득점이 나왔다. 힐 클라이밍이 나온 시점부터는 손 안대고 그냥 돌려놓고만 있었다. 끝나고 보니 우리팀의 점수가 낮았는데, C에서 우리보다 2만점 더 받은 실버님은 위에서 설명한 simple greedy만 돌리셨다고 한다 (실제로 해봤더니 거의 같은 점수가 나왔다). 저 simple greedy는 DEF에만 돌려봤는데, C가 마감되었다고 생각하고 실수한 것 같다. 그리디로 초기 솔루션을 주고 힐클라이밍 돌렸으면 엄청 잘 나왔을듯. 제일 아쉬운 부분.
• D는 몇가지 가정을 넣으면 대충 Max 3-SAT으로 환원이 된다. 이 가정하에는 결국 만족한 clause 비례 점수가 추가되는 시스템이다. 열심히 했지만 특정 시점에서 진전이 없어서 그냥 최적해에 매우 근접한 걸 찾은 게 아닐까 싶었는데 까 보니 타 진출팀 비해서 점수가 상당히 낮았다. 그런데 여기서 고득점 받았다는 팀들이 한 건 다 해봤는데 뭐가 문제인지 모르겠다. D는 5028790이 계속 찍히기에, 그리고 그게 98% 이상 배정을 했다기에, 이 정도면 optimal이 아닐까 하고 기피한 점도 있다.
• E/F가 어려운 입력이고 그냥 대충 어렵게 생겼다. 둘 다 비슷비슷하지만 E는 signup time이 작고, F는 signup time이 크다는 차이가 있다. 둘 다 simple greedy에서 시작하고, 상수 파라미터를 조금씩 튜닝해 보다가, kdh한테서 flow 이야기가 나오기에 min-cost flow를 구현해봤다. 그리디로 무슨 library를 선택할 지, 그리고 선택할 순서를 고정시킨 후 교집합을 전송하는 과정에서 낭비가 생기기 때문에 max cost matching을 사용해서 교집합을 제거해 주고, 선택된 library 집합 내에서 optimal하게 보내는 것이다. 이걸 구현한 후 점수가 15만점 올라갔다. 15만점! 사실상 여기서 승부를 봤다. 이후에 hill climbing으로 데이터를 계속 깎아서 자잘한 점수를 꽤 올렸다.
• F는 library 집합을 선택한 후 bitmask DP, min-cost flow 다 해봤는데 단 1점도 오르지 않았다. 사실상 library를 무엇을 선택하냐가 좌우하는 입력으로 보였다. 결국 nong님과 kdh가 ad-hoc한 optimization들을 많이 시도하면서 데이터를 깎았다.

POI Study

• POI15 Sorcerers: 상태가 많지 않고, 전이는 손으로 써보면서 열심히 노가다하면 된다. 최후 상태 전이는 노가다하기 너무 복잡하니 백트래킹으로 처리해주자.
• POI15 Squares: $f(k)$ 에 대한 "일종의" closed-form을 브루트 포스로 찾아주면 대충 할 수 있다. 짜증나는 문제
• POI15 Car Washes: 재밌는 DP. Cartesian tree를 만들어주는 식으로 구간 쪼개기 DP를 할 수 있다.
• POI12 Prefixuffix: [AB]S[BA] 형태로 분할해서 $|A| + |B|$ 를 최대화하는 것이다. B가 없으면 A는 failure function으로 효율적으로 나열할 수 있다. B가 있으니, A로 가능한 $O(n)$ 개의 후보를 다 해본 후 B를 똑같은 식으로 찾아주면 $O(n^2)$ 풀이가 된다. 이제 A의 후보를 $O(\log n)$ 으로 줄일 건데, 만약 $fail(|S|) \geq |S| / 2$ 이면 $A$는 $p = |S| - fail(|S|)$ 길이의 주기를 가진 문자열이 된다. 이제 $|A| = |S|, |S| - p, |S| - 2p, \ldots$ 를 전부 해 보는 것이 원래 풀이이다. 저런 식으로 $|S| - kp$ 까지 내려갔다고 하면, $|A| = |S| - p, \ldots, |S| - (k-1)p$ 는 해 볼 필요가 없음을 관찰할 수 있다. 그러면 $A$ 의 후보가 $O(\log n)$ 이다. 그래서 첫번째 풀이에 이 커팅을 추가해 주면 복잡도가 $O(n \log n)$ 이 된다. tlwpdus가 가짜 뉴스라고 알려줬다. 사실 아직 믿을 수 없긴 한데 확인 후 정정하겠다. 
• POI09 Algorithm Speedup: 비벼보다가 잘 안되는 거 같아서 풀이를 봤다. 설마 $F(x, y)$ 의 성질을 관찰하는 문제겠어 했더니 진짜 그런 문제였다. $F(x, y) = 1$ 이면 이를 $x \sim y$ 라고 하자. $x \sim y$ 는 reflexive (자명) symmetric (자명) transitive ($|W(x)|$ 에 대한 수학적 귀납법) 이라서 equiv. relation임을 보일 수 있다. 결국 우리가 관심있어하는 후보군은 $a$ 혹은 $b$ 의 부분배열이니까, 모든 부분배열에 대해서 equivalence relation임을 찾고 컴포넌트를 매겨주면 문제를 풀 수 있다 ($a$ 와 $b$ 는 "잘" 이어붙여주자). $W(x) = 1$ 인 경우 컴포넌트 라벨링은 자명하다. $W(x) > 1$ 인 경우, Prefix / Suffix의 컴포넌트 번호, 그리고 Suffix에서 고르지 않은 원소 (뭐 Prefix에서 고르지 않은 원소를 골라도 된다. 핵심은 $W(x)$ 가 같은지 여부를 prefix/suffix의 계산 결과에 의존해서 조는 것이다) 3개의 동치 여부가 같은 컴포넌트 여부를 좌우한다. 그래서 suffix array를 만들듯이 이 구조를 inductive하게 만들어주면 된다. 이걸 단순히 하면 대충 $O(n^2)$ 정도일 거고, $O(nk)$ 에 줄이는 것은 알아서 생각해 보면 될듯. 시간 제한이 빡빡해서 내가 시도한 $O(nk \log n)$ 은 전부 TLE 났다.
• POI10 Lamps: 튕기는 횟수가 많아야 2000번이고 (이건 입력 좌표 제한상 자명) 그리고 모두 $2^k$ 꼴이라고 가정할 수 있다. 홀수 소인수가 있으면 빼 줘도 문제가 없기 때문. 고로 튕기는 횟수를 고정한 후 brute force를 할 수 있다. 이렇게 되면 문제는, 60만개의 직사각형이 주어지고 이들이 최대 $X$ 개 겹칠 수 있다고 할 때, 쿼리로 주어진 직사각형 안에 $X$ 개 겹치는 영역이 존재하는지를 찾는 문제가 된다. 사실 쿼리가 600개인데 도움이 될 수 있는지 모르겠다. 아무튼 여기가 어려운데, VPCPC 2014 Posters와 비슷하게 (실제로는 더 쉬움) 최대로 쌓인 시점에서 tag를 저장해 주고 lazy propagation에서 태그를 관리해 주면, 해당 위치가 $X$ 개 겹친 가장 최근 시점을 저장할 수 있고, 이 시점에 대한 max query를 해 주면 판별할 수 있다. 모범 풀이는 다른 거 같은데 잘 이해가 안 간다.