2018.12.29 problem solving

Topcoder SRM 744

• Easy는 그대로는 매우 귀찮으나, 2차원 부분합을 구할 때 쓰는 포함 배제 테크닉을 활용하면 조금 덜 귀찮아진다. 물론 그래도 귀찮다. 난 문제를 잘못 읽어서 망했다.
• Medium은 행과 열에 대해서 해당 행 / 열을 뒤집었는가? 를 나타내는 $n+m$ 개의 boolean 변수를 잡으면, 주어진 조건은 $X_i + X_j$ 의 홀짝성에 대한 제약조건으로 바뀐다. 이를 일종의 이분 그래프라고 생각하고 풀어주면 된다... 라는 류의 문제를 한 두 번 본게 아니어서 그냥 아무 생각 없이 코드를 짰으나 문제에 함정이 있다는 것을 늦게 깨달았다. 고치니까 150점.
• Hard는 큰 트리에서 특정한 형태의 선형 계획법 (LP) 를 돌리는 문제이다. small-to-large 트릭을 활용한 그리디 접근법이 있지만 나는 이렇게 해결하지 않았다. LP Duality를 사용하면, Dual Problem이 간단한 Min-cost Max-flow임을 알 수 있다. MCMF라고 하면 복잡도가 매우 클 것 같으나, 그래프가 정말 단순하다. 싱크가 루트고, 소스는 각각의 정점이라서, 경로의 cost는 단순히 각 정점에 부여된 $c_i$ 가 되며 그 최단 경로도 유일하다. 또한, 모든 길이 루트로 가기 때문에 역변도 생기지 않는다! $c_i$ 순으로 정렬하고 유일한 augmenting path를 따라서 흘려주면 $O(n^2)$ 이다. 이렇게 단순한 구성에서는 augmenting 과정이 경로 최솟값 + 경로 덧셈 문제이기 때문에, heavy-light decomposition + segment tree + lazy propagation을 써서 최적화해 주면 된다. $O(n\log^2 n)$.
  

Hard가 fail되었는데 이유가 참 한심하다. 구글링을 열심히 해 보니 탑코더의 스택 메모리 제한이 8MB라고 한다. 8MB! 그걸로는 주어진 트리에서 DFS도 못 돌린다. 프리오더 구하려면 스택 써야 한다. 웃프다는 말 밖에 할 말이 없다. 탑코더를 할 때마다, 상식적으로 납득 불가능한 기준선에서 내 레이팅이 좌우된다는 느낌을 받을 때가 너무 많다. 물론 탑코더보다 스택 메모리 제한이 훨씬 더 답 없는 모 대회도 있다. 그 대회는 심지어 선인장을 내던데... 하지만 그 대회를 비판하는 것은 용납할 수 없다. 그렇게 5등~7등을 해야 했을 대회를 23등 했으나, 그래도 레이팅이 올랐던 거 같다. ㅋㅋ

 

Atcoder Grand Contest 029

거의 1년만에 했는데 잘 했다. 다 풀어서 기분이 좋았다. B E F는 정말 아름다운 문제들이다. A D는 조금 실망스러웠다.

• A는 사골이다. 어느 정도 사전 지식 문제라고도 생각한다. 왜 안 걸렀는지 모르겠다.

• B는 난이도가 쉬우나 매우 좋은 문제였다. 작은 숫자부터 보면 매칭해야 할 큰 숫자의 가능성이 여럿 있기 때문에 혼란스럽다. 하지만 큰 숫자의 관점에서 보면 매칭해야 할 작은 숫자는 유일하다! $A_i + A_j = 2^K$ 일 때, $i < j$ 라고 하면 $2^{K-1} \le A_j < 2^K$ 가 성립한다. $A_j$ 에 대해서 $K$ 가 정해지고 $A_i$ 도 정해진다는 것이다. 이 시점에서부터는 $j$ 를 감소순으로 돌고, 매칭할 수 있으면 무조건 매칭을 시켜 주는 그리디 알고리즘이 가능하다. 그리디 알고리즘은 왜 가능할까? Forest에서 최대 매칭을 찾는 것은 임의의 매칭되지 않은 리프를 잡고 그리디하게 지워 나가는 것을 반복하면 된다. $j$ 에 대해 매칭되는 유일한 $i$ 를 부모라고 생각해 보자. 지금 우리가 하는 것이 정확히 그것이다.

• C는 어려운 문제였다. 조건을 만족하는 임의의 문자열 집합을 생각해 보자. 이 문자열 집합을 Trie에 넣었다고 생각해 보면, 일단은 Trie를 순회했을 때 각 문자열이 순서대로 나올 것이고, 해당 Trie가 필요로 하는 최소 문자 개수는 모든 노드의 자식 개수의 max와 동일하다. 이 관찰을 가지고 답에 대해서 이분탐색 하자. 과정은 그리디하게 Trie를 만드는 과정이라고 해석될 수 있는데, 이는 스택에 해당 노드의 깊이, 자식 개수를 저장하는 식으로 가능하다. 난 이 부분을 깔끔하게 생각하고 구현하는 것이 매우 어려웠고, 결국 푸는 데 상당한 시간을 소모했다.

• D는 난이도가 B보다 훨씬 쉬우나 (A가 사전 지식임을 감안하면 그것보다도 쉬우나) 그 자리에 있었다. 난이도의 적절성을 떠나서 그냥 문제 자체가 안 좋다. 출제 과정에서 걸러지지 않은 게 이상한 문제. 내 생각

• E는 AGC 레벨의 문제였고 재미있었다. 나는 주최 풀이랑 조금 다른 복잡한 풀이였다. 어떠한 정점에서 루트로 올라간다는 것은, 한번 서브트리를 돌다가 부모를 찍고, 부모 쪽에서 또 돌다가 그 부모를 또 찍는 형태의 경로이다. 여기서 좋은 필요충분을 만들 수 있다. 임의의 정점 $v$ 에 대해서, $v$ 가 돌아다니는 와중에 정점 $w$ 를 만난다는 것은, $(LCA(v, w), w]$ 경로의 최댓값이 $[1, LCA(v, w))$ 간의 경로 최댓값보다 작다는 뜻이다. (포함 관계를 표현하기 위해 개구간 / 폐구간같은 기호를 썼음에 유의). $v$ 랑 상관 없이 LCA에 대해서 모든 것이 결정되기 때문에 저 값을 전처리하면 대략 부모 - 자식 경로 합 문제로 환원할 수 있다.

  구해야 하는 것은 각 에지 $(par(w), w)$ 에 대해서 $[1, w)$ 최댓값보다 작은 최댓값을 가지는 정점의 개수이다. Small-to-large의 요령으로 $w$ 에서의 최댓값을 priority queue에 관리할 수 있다. priority_queue 에서 구간 쿼리를 할 수는 없지만, 어떠한 정점이 빠지고 추가되었는지의 수열을 알 수 있다. 이 수열의 길이는 $O(n \log n)$ 이다. DFS로 이 수열을 다시 한번 시뮬레이션 해 보는데, 이제는 priority queue 대신 Fenwick tree를 사용한다. Fenwick tree니까 구간 쿼리를 할 수 있고, 이제 각각의 에지에 대해서 원하는 값을 구해 놓았으니 문제를 푸는 것은 어렵지 않다.

• F의 직관은, $K$ 개의 집합을 합집합했을 때 정수가 $K$ 개 이하이면 절대 트리를 절대 만들 수 없다는 것이다 (당연히, 간선이 많아야 $K-1$ 개 생기니까). 임의의 $K$ 개의 집합을 합집합했을 때 정수가 $K+1$ 개 이상이면 항상 트리를 만들 수 있을까? 여기서 홀의 결혼 정리와 analogy를 만들 수 있다. 홀의 결혼 정리는 임의의 $K$ 개의 집합을 합집합했을 때 매칭 가능한 쌍이 $K$ 개 이상이면 항상 답이 존재한다는 내용이다.

  홀의 결혼 정리는 constructive한 증명을 가지고 있다. 그렇다면 우리의 추측도 constructive한 증명을 시도하면 도움이 될 것이다. 아무 정점을 루트로 잡고 시작하자. 이 정점을 모든 집합에서 빼도, 임의의 $K$ 개의 집합을 합집합하면 크기가 $K$ 개 이상이다. 고로 홀의 결혼 정리에 의해 각각의 집합에서 루트가 아닌 서로 다른 정점을 고를 수 있다 (직접 구하는 것은 Hopcroft-Karp 이분 매칭을 사용. 이분 매칭이 없으면 자명히 답이 없다.)

  위에서 구한 매칭을 토대로 트리를 만드는 것은 아주 간단하다. 루트에서 시작해서, 루트를 포함하는 모든 집합을 돌자. 해당 집합에 매칭된 정점과, 루트를 잇는 간선을 만들어주자. 이렇게 루트에서 모든 가능한 정점들을 이었다면, 이 정점들에 대해서도 자식을 이어줄 필요가 있다. 그래프 탐색을 하듯이, 이들을 큐에 넣어서 BFS를 하고, 그 정점들에 대해서도 똑같은 작업을 시행한다 (물론, 이미 연결된 정점을 다시 이으면 안되는 것은 당연하다.)

  이제 알고리즘의 정당성을 증명하기 위해서는 저 과정이 모든 답이 존재하는 트리에 대해서 절대 "실패하지" 않음을 보이는 것으로 충분하다. 저 과정이 실패한다는 것은, 모든 과정이 끝난 이후 루트에서 연결된 정점이 $N$ 개 미만임을 뜻한다. 그 컴포넌트의 크기를 $K$ 라고 하자. 연결된 $K-1$ 개의 정점은 그에 매칭된 $K-1$ 개의 집합을 가지고 있다. 나머지 $N-K$ 개의 집합은 지금 잡은 컴포넌트의 정점을 전혀 포함하고 있지 않다. 만약에 그렇다고 하면, 즉 그러한 집합 중 하나가 컴포넌트 상의 임의의 정점을 포함한다면, 그 집합은 발견되었을 것이고, 그 집합에 매칭된 정점이 추가되었을 것이기 때문에 가정에 모순이다. 즉, 나머지 $N-K$ 개의 집합의 합집합 크기는 $N-K$ 이하이다. 그렇다면 이 트리에서는 답을 구하는 것이 불가능하다.

  여담으로, 4번째 문단은 지금 글을 쓰면서 증명하는 것이고, 대회 때는 주어진 시간도 없었고 완전히 증명하기엔 시간이 아깝다고 생각해서 그냥 짰고 맞았다.

 

Educational CF #56

• A. $n/2$.
• B. 정렬.
• C. $a_i$ 를 가능한 최소로 유지.
• D. bipartite coloring.
• F는 복잡한 DP 포함 배제였다. 난 매우 복잡했는데 어떻게 그렇게 빨리 풀었는지 잘 모르겠다.. 하다가 힘 빠져서 포기할 뻔 했다.
• G는 abs(x) = max(x, -x) 임을 관찰하면 간단한 구간 최댓값 연습 문제이다. 무슨 약을 먹었기에 E 뒤에 넣었을까..

E번은 귀찮은 과정을 통해서 2D 평면에 점 추가 + 제거 + 개수 세기 문제로 환원될 수 있다. 그렇게 좋은 문제는 아니라고 생각하지만, gritukan의 코드를 보다가 매우 간단한 방법을 찾아서 이를 소개하려고 한다.

일단 위 문제는 2차원 Segment Tree를 만들면 이론적으로는 쉽게 풀 수 있다는 것에 주목하자. 2차원 Segment Tree에서 점 추가는 $O(\log N)$ 개의 1차원 Segment Tree 노드 갱신, 구간 쿼리는 $O(\log N)$ 개의 1차원 Segment Tree 노드 쿼리로 환원된다.

이 때, 이 문제가 Offline이니까, 이 과정들을 한번씩 해 주면서 각 쿼리에서 갱신되는 Segment Tree가 무엇이고 구간 합을 구하는 Segment Tree가 무엇인지 알 수 있다. 진짜 갱신을 하고 구간 합을 구하는 게 아니다. 각 노드마다 Segment Tree를 실제로 만들지도 않는다. 그냥 그러는 시늉만 하고, 실제로는 각 노드에 갱신 / 쿼리 sequence만 저장하는 것이다. 이제 모든 문제는 노드에 대해서 독립적이다. 그리고 각 노드에 저장된 것은 1차원 점 갱신, 구간 합 문제이다. 그건 쉬운 문제니까, 각 노드를 돌면서 Fenwick Tree로 그 문제를 "진짜로" 풀어주면 된다.

그동안은 각 노드에 대해 "압축된 BIT" 를 하는 방법만 알았는데, 이 새로운 방법은 다양한 문제에 대해 일반화되고 구현도 매우 간단하며 효율적이다. 오프라인 2차원 쿼리를 하는 이상적인 방법인 것 같다.

여담으로 이러한 오프라인 2차원 쿼리에 대해 나중에 시간이 나면 (...) 튜토리얼을 써 볼 생각이다. 라인 스위핑이 안 되는 상황에서는 위 방법과 분할 정복이 2차원 쿼리를 하는 이상적인 방법으로 보인다.

COCI 2018/2019 Round 3

3번하고 5번 말고는 문제가 별로 재미가 없다. 나는 Educational과 겹쳐서 시간이 별로 없었다. 3번은 상당히 어려운 문제인 것 같은데 굉장히 앞에 있다. bmerry도 이상하게 풀었던데 공식 풀이의 상태가 약간 의심된다.. 고민해 봐야 할 듯.

5번 문제는 괜찮은 튜토리얼 문제인 것 같다. 옛날에 코드포스에 비슷한게 나왔었고 그때도 writeup을 했으나 제대로 안 쓰여 있으니 그냥 다시 쓰도록 하자 (...)

주어진 그래프에 대해서 스패닝 트리를 하나 잡고, 이 스패닝 트리에 있는 간선은 가중치를 바꾸지 않을 것이라 약속하자. 이렇게 하면 스패닝 트리에 없는 나머지 간선들은 연산의 대상이 되고, 이 간선에 "실제로 배정되어야 할 가중치 값" 역시 알 수 있다. 이 가중치 값만 맞추면 문제의 제약 조건이 지켜진다.

각각의 간선에 대해서 독립적인 문제가 되니, 이제는 그래프를 잊고, 다음과 같이 생각할 수 있다.

• $M-N+1$ 개의 수가 주어진다. subset에 특정한 수를 xor하는 연산을 최소로 실행해서 전체 수를 0으로 만들자.

최소가 아니라 적당히 작은 횟수의 연산이라고 하자. 그러면 단순히 1, 2, 4, 8과 같은 $2^k$ 형태의 수를 모두 해보면, 각각의 비트를 하나 하나 끌 수 있다. 많아야 60번의 연산으로 모든 수를 지울 수 있는 것이다. 하지만 이것이 최소는 아니다.

여기부터는 뭐 길게 얘기할 수도 있긴 하나... 그냥 짧게 하자면, 모든 수를 binary vector로 보고, basis를 구해주면 된다. basis 집합은 선형 독립이기 때문에, 개념적으로 $1, 2, 4, 8$ 과 같은 수랑 다를 바가 없다. basis를 크기 감소 순으로 봐주고, basis의 가장 큰 비트가 켜져 있는 숫자들에 모두 연산을 한꺼번에 실행하자. 그러면 각 연산마다 가장 큰 비트를 항상 날려줄 수 있다. 그리고 이 과정이 실패하는 경우는 없다. basis 크기 만큼의 연산으로 문제를 해결할 수 있고, 이보다 더 적은 횟수로 할 수 없음은 그 개념을 안다면 자명할 것이다.

이 전략을 알면, 스패닝 트리를 뭘 잡는 지는 아무 상관이 없다는 것 역시 알 수 있다. 어떤 스패닝 트리를 잡아도, 사이클에 적혀있는 수들은 이 basis의 선형 결합으로 표현되기 때문이다. 고로 스패닝 트리를 아무거나 잡아도 알고리즘이 정당하다.

지금까지 다룬 내용은 기초적인 선형 대수학으로 커버되고, 이 정도 수학은 PS를 포함해 컴퓨터 과학 전반에 매우 유용하게 쓰이기 때문에 상위권을 노린다면 알아두는 것이 좋다. 관련 연습 문제로는 XOR Maximization 이 있다. 최근 고려대 대회에서도 이 XOR Maximization을 약간 응용한 XOR 포커라는 문제가 나왔다. 이 문제는 여러가지 풀이가 있는데, 내 풀이와 공식 풀이에서 쓰인 아이디어는 간단하지만 상당히 신선했고, 재미있었다.

 

Atcoder Study

ARC 102 F. Revenge of BBuBBBlesort!

가장 핵심적인 관찰은, 스왑의 대상이 되는 숫자들이 서로 인접할 수 없다는 것이다. 이는 $p_{i-1} > p_i > p_{i+1}$ 조건 때문인데, 엄밀하게는 나도 잘 모르겠고, 대충 해 보면 말이 안되는 것 같다는 것을 알 수 있다 (....) 이 관찰을 하면 문제가 굉장히 접근 가능해진다. 모든 스왑의 대상이 되는 숫자들이 2 / 3 이상 떨어져 있는데, 3 이상 떨어져 있으면 그냥 독립적인 이야기니까 (나랑 섞일 수 있는 수가 아니니까) 2만큼 떨어져 있는 chain들의 집합이 된다.

어떠한 수 $i$ 를 대상으로 해서 스왑을 진행한다는 것은 $swap(p_{i-1}, p_{i+1})$ 을 한다는 것과 똑같은 말이다. 그러면 $i, i+2, i+4, \cdots, i + 2k$ 를 대상으로 스왑한다는 것은, $i, i+2, \cdots, i+2k$ 는 전혀 안 건드리고, $i-1, i+1, i+3, \cdots, i+2k+1$ 만 건드린다는 뜻이다. (이들은 그 값이 무조건 바뀐다. 아니면 3개가 증가하기 때문에 그들 양 옆이 안 통한다..) 이렇게 되면 대충 수열을 partition할 수 있다. 현재 제자리에 없는 수들을 전부 모으고, 이 중에 인접한 것이 없는 지 확인하고 (있으면 무조건 -1), 없으면 이제 거리가 2인 애들끼리 묶어준 후 각각에 대해서 문제를 해결하는 것이다. 이렇게 문제가 많이 단순화된다.

이들에 대해서 인접한 숫자를 교환할 수 있으니까 대충 생각하면 버블 소트처럼 항상 정렬이 될 것 같으나, 사실은 그렇지 않다. 왜냐면 두 수를 교환하기 위해서 $p_{i-1} > p_i > p_{i+1}$ 이라는 조건이 있어서, 두 수 사이에 있는 수의 크기가 교환에 영향을 미친다. 이를 조금 더 살펴보자. 일단 구간 $[i-1, i+2k+1]$ 을 정렬했을 때 모든 숫자가 제자리에 있는지를 확인하자 (당연히 확인해야 한다). 그렇지 않다면 결국 $p_i = i, p_{i+2} = i+2 \ldots$ 를 만족할 것이고, 나머지 숫자들은 모두 제자리에 없을 것이다. 최솟값부터 옮겨 보자. 최솟값을 가장 왼쪽으로 옮기기 위해서는, 그 사이에 있는 수들이 모두 바로 오른쪽에 있는 수보다 커야한다. 두번째 최솟값 역시 그를 만족해야 한다. 이를 위해서는, 두번째 최솟값이 첫번째 최솟값보다 무조건 오른쪽에 있어야 한다.. 이런 식으로 논리를 펼쳐 나가면 대략 결론이

• 최종 위치가 왼쪽으로 가는 애들끼리 ($p_i < i$) 놓고 보았을 때 이들은 증가해야 한다.
• 최종 위치가 오른쪽으로 가는 애들끼리 ($p_i > i$) 놓고 보았을 때 이들은 증가해야 한다.

저걸 만족하면 항상 정렬이 가능하다. 증명을 제대로 안 했으나 둘을 따로 본다면 어렵지 않을 것으로 보인다. 아무튼 시간 복잡도는 $O(n\log n)​$ 혹은 그 이하.