Street Cleaning

문제 요약

무방향 연결 그래프가 주어졌을 때 길이가 1 이상인 path 2개로 분할해야 한다. $(|V| \le 1\,000, |E| \le 50\,000)$

모든 간선은 둘 중 하나의 path에 속해야 하고 한번만 사용되어야 한다.

풀이

path 1개로 분해해야 한다면 이는 간단한 eulerian path/circuit 문제다. 입력이 연결 그래프이기 때문에, 차수가 홀수인 정점만 신경쓰면 된다.

그런 정점이 4개보다 많다면 당연히 불가능하고, 그렇지 않은 경우 경로를 잘 찾으면 된다.

홀수 정점들을 잇는 가상의 간선을 추가한다고 생각해보자. 가상의 간선을 최대 2개 추가하여 모든 정점의 차수를 짝수로 만들 수 있고, 이 그래프에서 eulerian circuit을 찾을 수 있다.

eulerian circuit에서 나온 간선 번호 리스트에서 가상의 간선을 제거해도 path가 3개 이상으로 쪼개지지 않는다. 1개의 path로 분해되었다면 마지막 간선을 나머지 path에게 나눠주면 두 개의 path를 만들 수 있다.

리뷰

홀수 정점 사이에 가상의 간선을 추가한다는 아이디어를 못 떠올렸다. 가상 간선 추가 없이 나만의 구현으로 풀어보려고 했는데 실패했다.

AC를 받기는 했는데, 해당 코드에서 인접 리스트를 reverse하는 것만 추가해도 틀린다. 잘못된 코드인데 데이터가 약해서 뚫린 것 같다. 제대로 된 eulerian circuit 역추적 코드를 다시 짜봐야 한다.

Letter Stamper (Small)

문제 요약

A, B, C로만 이루어진 문자열 $S$을 프린트해야 한다. $(|S|\le100)$

사용할 수 있는 연산은 다음과 같다.

  • push x: 스택에 x push
  • pop: 스택에서 pop
  • print: 스택의 top을 print

처음에 스택은 비어있고, 최종 상태의 스택도 비어있어야 한다. 최소 연산 횟수는?

풀이

현재 스택이 ABC일 때, 다음에 출력해야 하는 값에 대한 최적 전략은 다음과 같다.

  • A: push A, print / pop pop print 중 하나
  • B: pop, print
  • C: print

스택이 ABC일 때 push될 수 있는 값은 A 뿐이다.

즉, 스택은 XYZXYZ… 꼴이다. 6가지 형태가 가능하다.

$D_{i, \text{kind}, \text{size}} :=$ $i$번째 문자까지 출력 / $\text{kind}$ 종류의 스택 / 스택 크기가 $\text{size}$ 일 때, 최소 연산 횟수

$\text{size} \le |S|$이므로 상태는 $O(3!\cdot|S|^2)$개 존재하고, 각 상태에서 상수 번의 전이만 일어나므로 $O(|S|^2)$에 문제를 해결할 수 있다.

$D_{i,\text{kind},0}$과 $D_{i,\text{kind},1}$는 좀 더 신경을 써줘야 한다. $\text{kind}$가 달랐더라도 prefix가 일치하면 전이가 될 수 있기 때문이다.

Letter Stamper (Large)는 $|S| \le 7000$인데 상수가 작지는 않아서 추가적인 처리가 필요하다. 토글링을 하고 $\text{size} \le \frac{|S|}{2}$로 둬서 메모리와 시간을 줄이면 맞을 수 있다. (+ pragma를 박으면 2배 빨라져서 토글링만 해도 통과는 된다)

pop을 lazy하게 하지 않고, $\text{size}$번까지 pop하는 걸 전부 전이하면 $O(|S|^3)$로 풀린다. 이건 약간 억지 $O(|S|^3)$이다.

$D_{c, l, r} :=$ 현재 stack의 top에 $c$가 저장되어 있고, $[l, r]$ 구간을 전부 처리한 후에 같은 $c$가 stack의 top에 있게 할 때, 최소 연산 횟수

리뷰

피라미드도 그렇고 원소가 정확히 3개일 때 특정 순열이 반복되는 꼴이 나온다는 관찰이 종종 보인다.

small은 네제곱 풀이도 돌아간다는 것 같다.

large는 $O(TN)$ 풀이가 있다. push를 하는 경우에 대해서 그리디 같은 처리가 가능한 것 같다.

$\text{kind}$를 3!개가 아니라 ABC, CBA 2개에 대해서만 관리해도 풀 수 있는 것 같다.

Erasing Matrix

문제 요약

$N \times M$ 행렬 $A$가 주어진다. $(2 \le N, M \le 500)$

인접한 칸 2개를 골라 정수 $k$를 더하는 연산을 사용할 수 있다.

모든 칸을 0으로 만드는 연산 시퀀스를 찾아라. 연산 도중에 각 칸의 값이 음수가 되어서는 안된다. 불가능하다면 불가능하다고 판별해라.

시퀀스의 길이는 $10^6$ 이하이면 된다.

풀이

관찰

  • $\sum A_{i,j} \equiv 1 \pmod 2$이면 불가능이다.
  • 초기에 $+\infty$을 다 주고 시작하면, $k<0$에 대해서만 고려해도 된다.
  • 음수 조건을 무시해도 좋다. 전부 0으로 만들 수 있다면, $k$가 큰 연산부터 수행함으로써 음수 조건을 만족시킬 수 있다.
  • 수행 가능한 모든 연산에 대해서 연립방정식을 세우면 변수는 $2NM-N-M$개, 식은 $NM$개 존재한다.
  • 답이 될 수 있는 모든 시퀀스에 대해서 $\sum k$는 같다.
  • $2 \times 2$ 행렬에서 $A_{1,1}, A_{1,2}, A_{2,1}$을 0으로 만드는 모든 시퀀스에 대해서, $\Delta A_{2,2}=A_{1,1}-A_{1,2}-A_{2,1}$이다.

앞에서부터 그리디하게 만들어보고 가능한지 판단하면 될 것 같다.

맞았다.

리뷰

불가능 필요충분조건을 생각하진 못했다. constructive하게 만들어보고 판단하는 전략을 세웠다.

필요충분은 체스판에서 검은 색에 놓여있는 원소의 합과 하얀 색에 놓여있는 원소의 합이 같다였다. 나도 나름 될 것 같다는 강한 예감을 가지고 코딩에 들어갔는데, 이 필요충분을 찾았으면 확신을 가지고 짤 수 있었을 것 같다.

인접한 칸에 대한 연산 $\rightarrow$ 체스판에서 다른 색으로의 전이 류의 접근이 되게 많이 보인다.

Equivalent Pipelines

문제 요약

크기가 $N$인 트리가 $d$개 주어질 때, 모든 $i$에 대해서 $i$번째 트리와 equivalent한 트리의 minimum index를 구하여라. $(N \cdot d \le 500\,000)$

$v_{T}(u, v)$: $T$에서 $u$와 $v$를 잇는 경로 중 minimum weight

$T_1$과 $T_2$가 equivalent하다: $v_{T_1}(u, v)=v_{T_2}(u, v)$ for all $1 \le u, v \le N$

풀이

해싱을 어떻게 잘 할 것인가?

global minimum weight 간선을 기준으로 트리가 쪼개진다고 볼 수 있다. 이 구조가 재귀적으로 반복된다.

거꾸로 리프부터 생각해보면 크루스칼의 공에서 쓰는 MST랑 비슷하다. 가중치가 같은 간선에 대해서만 한번에 합쳐지도록 해주면 정규화할 수 있을 것 같다.

$weight_u := $ $u$가 생성될 때의 간선의 가중치

$leaf_u :=$ $u$가 나타내고 있는 정점셋의 정점 번호 중 minimum

그렇게 생성한 $T$의 $weight_u \neq weight_{parent_u}$인 모든 정점에 대해서 $(weight_u, leaf_u, weight_{parent_u}, leaf_{parent_u})$ 튜플을 만든다. $weight_u = weight_{parent_u}$인 경우에는 더미 정점이므로 건너뛴다. 이 튜플들을 정렬하면 인코딩이 끝난다. 입력으로 주어진 트리를 크기 $O(N)$짜리 배열로 정규화했다.

$N \cdot d$가 작으므로 이 벡터를 통째로 맵에 넣어서 체크해도 된다.

Fenced In (Platinum)

문제 요약

$(0, 0)$과 $(A, B)$를 꼭짓점으로 하는 직사각형이 있다. 여기에 $N$개의 가로 펜스, $M$개의 세로 펜스가 존재해서 $(N+1) \cdot (M+1)$개의 구역이 생긴다. $(1 \le A, B \le 10^9, 1 \le N, M \le 25\,000)$

인접한 임의의 두 구역을 선택하여 그 사이에 있는 펜스를 없앨 수 있다.

모든 구역을 연결시키기 위해서 없애야 하는 펜스 길이 합의 최솟값은?

풀이

MST다. 크루스칼처럼 접근하면 $dx$나 $dy$를 가중치로 하는 간선으로 생각하고 minimum부터 보면 된다.

분할정복과 세그먼트 트리 등을 이용하면 별로 생각 안하고 풀 수 있을 것 같다.

나이브하게 하기에는 정점이 너무 많다. 하지만 같은 $dx$나 $dy$가 $O(N), O(M)$개씩 있으니, 사이클이 생기지 않는 선에서 그 행 또는 열의 모든 펜스를 한번에 지워줘도 된다.

이때 사이클이 생기지 않는 선에서 지우게 되는 펜스의 개수가 중요한데, 이건 그때까지 처리한 $dx$ 개수와 $dy$ 개수에 의해 결정된다는 걸 알 수 있다.

지운 펜스 개수가 $(N+1) \cdot (M+1) - 1$이 될 때까지 반복한다.

Bali Sculptures

문제 요약

길이가 $N$인 수열 $Y$과 상수 $A, B$이 주어진다. $Y$를 partition $A \le k \le B$개로 나눌 수 있을 때, 각 partition의 sum을 bitwise or한 결과의 minimum을 구하여라.

풀이

이 문제는 마지막 서브태스크가 나머지 서브태스크의 superset이 아니다. $N \le 100 \vee ( N \le 2000 \wedge A=1)$에서 각각을 나눠서 풀면 된다.

$N \le 100$

큰 비트부터 보면서 정답이 $2^k$를 포함하지 않을 수 있다면 어떻게든 포함하지 않는게 이득이다.

$D_{i, j} :=$ $2^k$를 추가로 포함시키지 않으면서, 앞에서부터 $i$까지 봤을 때 / $j$개의 partition으로 쪼갤 수 있는지 여부

$[l, r]$이 partition으로 선택될 수 있다는 것은, (sum&(~fixed_prefix)) < (1<<k)라는 것이다. 큰 비트부터 그리디를 했기 때문에 그 비트들이 정답에 포함될지 여부는 이미 결정돼있다. 때문에 sum이 그 비트들을 포함해도 무시해줄 수 있다.

$D_{N,A}, D_{N,A+1}, \cdots, D_{N,B}$ 중에 하나라도 true이면 정답에 $2^k$를 포함시키지 않을 수 있다.

$O(N^2)$의 상태에 대해서 $O(N)$의 복잡도로 전이해주면 $O(N^3)$로 DP table을 전부 구할 수 있고, 답의 상한인 $100 \cdot 10^9=10^{11}$의 비트수만큼을 반복하여 답을 구할 수 있다.

$N \le 2000 \wedge A = 1$

partition 개수가 작을수록 이득이다.

정답인지 확인하는 파트를 생각해보면 $D_{N,i}=\text{true}$인 $i \le B$가 있는지만 중요하다. 이를 위해서는 조건을 만족하는 $\min i$만 알면 충분하다.

$P_i :=$ 앞에서부터 $i$까지 봤을 때 / $2^k$를 추가로 포함시키지 않으면서 쪼갤 수 있는 최소 partition 개수

$N \le 100$과 비슷하게 전이해주면 $O(N^2)$로 DP table을 전부 구할 수 있다. $P_N \le B$ 부등식을 통해 $2^k$가 정답에 포함되는지를 알 수 있다. 마찬가지로 답의 상한인 $2\,000 \cdot 10^9$의 비트수만큼을 반복하여 답을 구할 수 있다.

리뷰

두 번째 케이스를 풀 때, 첫 번째 DP에서 그래프 모델링 -> 최단경로까지 뻗어나갔다가 그냥 min을 저장하면 된다는 걸 깨달았다.

결국 구해야 되는 것이 뭔지를 정확하게 인지하자.