첫 ICPC 인터넷 예선이 끝났고 (끝난지 몇일 되었지만..) 우리팀(Taste Why Frame - 맞맛 왜 틀)은 1차 한국 지역 본선 진출자 명단에 확정되었다.
그렇지만 여러모로 아쉬웠다. ICPC 인터넷 예선이 시작되자 마자 웹사이트가 터졌고, 배부받은 문제지의 프린트 상태가 매우 좋지 않아 문제를 제대로 읽을 수 없었다. 그래서 문제지를 새로 달라고 요청했는데 있던 문제지를 그냥 가지고 가는 바람에 꽤 긴 시간 동안 아무것도 하지 못했다.
더욱이 대회 진행중에 I, C번을 AC받은 이후로 B, H, K, L번이 채점이 되지 않았다. (그나마 K, L같은 경우 한번 WA를 받았지만 이후로 계속 Pending이 되었다)
결국 제출한 문제가 맞았는지 틀렸는지도 모른채 대회가 끝났다.
결국 4 solve밖에 하지 못했지만 대회 중 및 끝난 후에 생각해본 풀이를 작성해 보려 한다. 아직 생각해 보지 못한 문제는 풀이를 생략하고 추후에 추가해 나가도록 하겠다.
현재 A, B, C, D, F, H, I, J, L문제들에 대해서만 풀이를 작성하였다.
I. Registration
ID, pw 출력하는 등록 문제. 터져가는 서버를 뚫어 무사히 제출했다.
A. All you need is dating
데이트를 하고 싶어 하는 IC학교의 $m$명, PC학교의 $n$명의 학생들이 있다. ($1 \le m \le 100$, $1 \le n \le 100$)
$k$개의 쌍 $v$, $u$가 주어지는데, 해당 쌍은 IC학교 학생 $v$가 PC학교 학생 $u$와 데이트를 하고 싶어함을 나타낸다. ($1 \le k \le 10,000$)
그리고 각각의 학생들에게는 최소 데이트 횟수와 최대 데이트 횟수가 정해져 있다. 한 학생의 데이트 횟수는 반드시 최소와 최대 데이트 횟수 사이에 위치해야 한다.
이런 상황에서 모든 조건을 만족시킬 수 있다면 데이트 할 수 있는 최대 쌍을 구하고 아니라면 -1을 출력하는 문제다.
풀이
Network flow 로 flow를 모델링 할 수 있다. 하지만 최솟값 즉, 각 간선에 lower bound가 존재하기 때문에 lower bound를 만족하면서 플로우를 이을 수 있는지 판단해야 한다.
이런 상황에서 lower bound를 만족 가능한지 판단하는 것을 Circulation Problem라고 하고 가능 할때의 max flow를 구하는 것을 Maximum Flow with Edge Demands라고 한다.
이러한 flow를 통틀어 LR-Flow를 이라 하는데, 다음의 방법을 통해 Circulation Problem을 해결할 수 있다.
구하려는 플로우 모델 $G = (V, E)$에 대해 $G$에서의 소스를 $s$, 싱크를 $t$라 하자. 이때 함수 $l, u: E \rightarrow \mathbb{R}$에 대해 각 간선에 흐르는 flow인 $f(e)$는 $l(e) \le f(e) \le u(e)$를 만족해야 한다. 이를 만족하는 경우를 가능한 플로우(feasible flow)라 하자. $l(e) = 0$일 경우 가능한 플로우가 된다. 하지만 $l(e) > 0$인 경우에 대해서는 가능한 플로우인지 확인하는 과정이 필요하다. 이를 위해 새로운 그래프 $G’ = (V’, E’)$를 다음과 같이 정의한다.
- 모든 정점 $v \in V$에 대해 $c’(s’ \rightarrow v) = \sum_{u \in V} l(u \rightarrow v)$
- 모든 정점 $v \in V$에 대해 $c’(v \rightarrow t’) = \sum_{w \in V} l(v \rightarrow w)$
- 모든 간선 $u \rightarrow v \in E$에 대해 $c’(u \rightarrow v) = u(u \rightarrow v) - l(u \rightarrow v)$
- $c’(t \rightarrow s) = \infty$
이때 다음과 같이 $L$을 정의한다.
\[L:= \sum_{v \in V} c'(s' \rightarrow v) = \sum_{v \in V} c'(v \rightarrow t') = \sum_{u \rightarrow v \in E} l(u \rightarrow v)\]이러한 $G’$에서의 가상의 소스 $s’$에서 가상의 싱크 $t’$으로 max flow를 구했을 때 $s’$에서 나가는 모든 flow와 $t’$으로 들어가는 모든 flow가 같다면 즉, $L$값을 가지고 있다면 $G$는 가능한 플로우이다.
자세한 증명은 문서을 참조하라.
위 방법 말고도 MCMF를 사용하는 방법도 있는듯 하다.
위 방법을 이용하여 불가능 할경우, -1을 출력하고 가능할 경우 maximum flow를 돌려 답을 출력하면 될 것이다.
B. Balanced String
0과 1로 이루어진 이진 문자열이 있다. 이때, 균형잡힌 문자열이란 0과 1의 개수 차이가 1이하인 문자열을 말한다. 뿐만 아니라 해당 문자열의 모든 prefix도 균형잡힌 문자열이여야 한다.
양의 정수 $n$이 주어졌을 때, 길이가 $n$인 이진 문자열 중에서 균형잡힌 문자열의 개수를 16769023로 나눈 나머지 값을 구하라. ($1 \le n \le 100,000$)
풀이
모든 prefix도 균형잡힌 문자열이어야 하므로 가장 직관적인 DP 테이블을 다음과 같이 정의할 수 있다.
\[DP[i][j] = \left\{\begin{matrix} \text{길이가 }j\text{이고 0과 1의 개수가 같은 문자열의 개수} & (i = 0) \\ \text{길이가 }j\text{이고 0이 1보다 1개 많은 문자열의 개수} & (i = 1) \\ \text{길이가 }j\text{이고 1이 0보다 1개 많은 문자열의 개수} & (i = 2) \end{matrix}\right.\]DP 점화식은 다음과 같다.
\[DP[0][j] = DP[1][j - 1] + DP[2][j - 1]\] \[DP[1][j] = DP[0][j - 1]\] \[DP[2][j] = DP[0][j - 1]\]C. Byte Coin
1일 부터 $n$일 까지 $n$일 동안 바이트 코인의 가격 $s_i$가 주어지고 초기 현금 $W$가 주어졌을 때, $n$일 동안 각 날에 매수/매도를 하여 현금을 최대화 하는 문제다. ($1 \le n \le 15$, $1 \le W \le 100,000$, $1 \le s_i \le 50$)
풀이
가격이 내려갈 때는 모두 팔고 가격이 올라갈 때는 모두 사면 된다.
모두 팔 경우 가격이 더 내려갔을 때 더이상 팔 코인이 없으므로 최대 이익을 얻을 수 있고, 모두 살 때는 가격이 더 올라갔을 때 살 돈이 없으므로 최저가에 코인을 구매할 수 있다. 그리고 마지막 날에 모두 팔면 된다.
이때 주의할 점은 $W = 100,000$이고 $n = 15$일 때, 15일 동안 $s_i=1, 50, 1, 50, \dots$일 경우 $100,000 \times 50^{7}$으로 돈이 커질 수 있기 때문에 변수형 범위를 고려해 주어야 한다.
D. Canal
유클리드 직교좌표 평면 위에 존재하는 마을이 있다. 해당 마을에 존재하는 $n$개의 집들의 좌표가 각각 주어진다. 각 집의 좌표의 범위는 $-10^9$이상 $10^9$이하이다. 한 좌표에 여러 집이 존재할 수 있다. ($1 \le n \le 300,000$)
이때 $x$축, $y$축에 각각 평행한 canal을 건설하려고 한다. canal이 집을 지나도 상관 없다.
이런 상황에서 두 canal까지의 거리가 최대인 집까지의 거리가 최소로 만들려고 할때, 해당 거리를 구하라.
풀이
값 $d$를 정하고 최대 집까지 거리를 $d$로 만들 수 있는지 확인하는 것을 다음과 같이 빠르게 해결할 수 있다.
먼저 $y$축에 평행한 canal을 결정하자. 최대 집까지의 거리는 $d$이므로 최대 가로 거리가 $2d$가 되도록 집들을 순차적으로 deque 등의 자료구조에 갱신해 가면서 Line sweeping을 한다. 이때에는 deque을 이용한다고 치자.
각 갱신에 대해서 deque에 포함되지 않은 집들은 $y$축에 평행한 canal과 거리가 $d$보다 큰 것은 자명하다. 그렇다면 해당 집들과 최대 $d$거리 내에 있는 $x$좌표와 평행한 canal이 존재할 수 있는지 판단해야 한다. 이는 해당 집들의 $y$좌표를 $p_y$라 할 때, $\max{p_y} - \min{p_y} \le 2d$인지 판단하면 된다.
deque을 갱신하는 데에 $O(N)$, $\max{p_y} - \min{p_y} \le 2d$를 구하는 데에 $O(\log{N})$이라 하면 정해진 $d$에 대해 Line sweeping을 하는데 최대 $O(N\log{N})$이 든다는 것을 알 수 있다.
따라서 파라매트릭 서치를 통해 구간 $L$에서 $d$의 최솟값을 구하면 $O(N\log{N}\log{L})$에 해결할 수 있을 것이다.
E. Choreography
$m$명의 멤버가 있고 일직선상의 무대에서 춤을 춘다. 무대는 $n$개의 닫힌 구간으로 나뉘어 있다. 각 구간의 길이는 $r$이다. 다음은 각 멤버들이 지켜야할 규칙이다. ($1 \le m \le n \le 5,000$, $1 \le r \le 10,000$)
- R1) 각 멤버는 구간에 위치해 있어야 한다.
- R2) 한 구간에는 두 명 이상의 멤버가 있을 수 없다.
- R3) 임의의 두 멤버가 존재하는 두 구간은 겹치지 않는다.
$a \le c$인 두 구간 $[a, b]$, $[c, d]$는 $c \le b$일 때 겹친다.
- R4) 각 단계 마다 오직 한 명의 멤버만 다른 구간으로 이동할 수 있다. 다시말해 두 명 이상의 멤버가 한 단계에서 동시에 움직일 수 없다.
- R5) 다른 구간으로 이동할 때, 원래 있었던 구간과 겹치는 구간에만 이동할 수 있다.
이때, 규칙 R3에 의해 이동하려는 구간이 다른 멤버를 포함하고 있는 어떤 구간과 겹치면 이동할 수 없다.
- R6) 집합 $S$는 멤버들이 처음 있던 구간들을 포함한다.
- R7) 집합 $E$는 멤버들이 마지막에 있던 구간들을 포함한다.
집합 $S$와 $E$는 입력으로 주어진다.
모든 규칙들을 만족하면서 $S$에서 $E$로 가는 최소한의 단계를 구하라.
풀이
F. Dryer
$n$개의 옷들이 존재한다. 각 옷은 손상을 입지 않고 말려질 수 있는 최대 온도 $t_i$를 가지고 있고, 젖은 정도를 나타내는 $w_i$를 가지고 있다. 임의의 옷 $i$에 대해 $T \le t_i$ 온도에서 말리면 $m_i = 30 + (t_i - T)w_i$ 분의 시간이 걸린다. 당신은 옷을 최대 $k$그룹으로 나누어 드라이어에 돌리려고 한다. 옷을 손상시키지 않을 때, 최소 시간을 구하라. ($1 \le n \le 1,000$, $1 \le k \le 3$, $40 \le t_i \le 100$, $0 \le w_i \le 100$)
풀이
옷 하나를 $m_i = 30 + (t_i - T)w_i$로 표현할 수 있다. 이때, 다음과 같은 형태로 변형할 수 있다.
\[m_i = 30 + (t_i - T)w_i = 30 + t_iw_i - Tw_i\]여기서 $T$를 제외한 모든 값이 $i$에 관한 식이다. 따라서 $a_i=-w_i$, $b_i=30+t_iw_i$일 때, $x$를 온도 $y$를 시간이라 하면 $y=a_ix+b_i$인 선형 식으로 표현할 수 있다.
여기서 하나의 드라이어 즉, 하나의 그룹 $G$는 온도 $G_t$하나로 표현할 수 있다. 이때 $G$에 포함될 수 있는 옷은 $x = G_t$에서 $30 \le y$인 경우이다. (옷이 손상 될 때는 $t_i < T$인 경우이고 이런 경우에 $m_i < 30$이 되기 때문이다)
이를 이용하면 그룹 $k$개 각각의 온도 $G_kt$를 결정하고 모든 옷을 드라이 할 수 있는지에 대해 판단할 수 있다. 그렇다면 시간을 $t$로 결정했을 때 $30 \le y \le t$를 판단하여 모든 옷을 $t$분 내에 드라이 할 수 있는지 판단할 수 있다.
하지만 해당 판단을 하는 것이 중요한데, 그룹 $k$개를 결정하고 판단하는 경우에는 $O(n(\max{t_i})^k)$이 소요되어 TLE가 될 것이다. 따라서 그룹을 brute force로 결정하지 않고 옷들에 대해 $O(n)$탐색하며 $30 \le y \le t$인 온도 구간을 저장하고 각 구간들의 끝 지점을 정렬하여 먼저 끝나는 지점에 그룹을 결정하는 방식으로 $k$개 이하로 그룹을 결정했을 때 모든 옷을 드라이 할 수 있는지 판단하는 방식으로 $O(n\log{n})$에 해결해야 한다.
이후 불가능하면 $t$를 늘리고, 가능하다면 줄이는 parametric search로 $t$의 최솟값을 구하면 $O(n\log{n}\log{\max{t_i}})$에 해결할 수 있을 것이다.
G. Enumeration
$n$개의 영어 소문자를 가지고 있는 집합 $\Sigma$가 있다. $\Sigma$에서 $k$개의 알파벳을 뽑아서 $k$개로 중복없이 만들 수 있는 단어들을 사전순으로 나열하려고 한다. 이들 각각을 k-word라고 하자.
k-word인 $S$와 $T$가 주어졌을 때, 모든 k-word를 사용하여 $S$부터 $T$까지 나열하려고 한다. 이때, 이웃해 있는 k-word는 $k-1$개의 알파벳만 공통으로 가지고 있어야 하며 1개의 알파벳은 반드시 달라야 한다.
이러한 조건을 만족하는 k-word를 순서대로 나열하시오.
풀이
H. Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명했다. 자연수 $n$이 주어질 때, $n$을 제곱수 합으로 표현할 때 제곱수들의 최소 개수를 구하라. ($1 \le n \le 50,000$)
풀이
최대 4개로 적게 표현됨이 증명되었다는 것을 이용하여 다음과 같이 DP테이블을 정의한다.
\[DP[n] = n\text{을 제곱수 합으로 표현할 때 최소 개수}\]처음에는 $O(\sqrt{N})$으로 돌면서 $DP[n] = 1$인 경우를 갱신한다.
다음에는 $O(N)$을 돌면서 $DP[n] = 1$인 경우에 대해 $DP[n] = 2$인 경우를 갱신한다.
이와 같이 $DP[n] = 3$인 경우를 갱신하고 $DP[n] = 4$인 경우를 갱신한다.
따라서 $O(\sqrt{N} + 3N\sqrt{N})=O(N\sqrt{N})$만에 해결할 수 있다.
J. Star Trek
$n$개의 행성을 순서대로 지나간다. 이웃한 행성 사이의 거리가 주어지고 각 행성마다 준비 시간 $p$와 우주선의 이동시간 $s$가 주어진다. 어떤 행성에 들리면 준비시간이 들지만 거리 1을 이동할 때 드는 시간이 해당 행성에 주어진 우주선의 이동시간이 된다. 첫 번째 행성은 반드시 들린다. 이때, 마지막 행성에 도착할 때의 최소 시간을 구하라. ($3 \le n \le 100,000$, $0 \le p \le 10^9$, $1 \le s \le 10^5$)
풀이
다음과 같이 DP 테이블을 정의할 수 있다.
\[DP[v] = v\text{ 까지 왔을 때 최소 비용}\]그렇다면 $d_v$를 시작 행성에서 부터 $v$행성 까지의 거리라고 하면 DP식은 다음과 같다.
\[DP[v] = \min_{0 \le i < v}{(DP[i] + p_i + s_i(d_v - d_i))}\]하지만 해당 식은 $O(N^2)$이므로 주어진 범위 내에서 TLE가 날 것이다. 그렇다면 DP식을 최적화 할 수 있는지 풀어본다.
\[DP[v] = \min_{0 \le i < v}{(DP[i] + p_i + s_id_v - s_id_i))} = \min_{0 \le i < v}{(s_id_v + DP[i] + p_i - s_id_i))}\]이때 $DP[i] + p_i-s_id_i$는 모두 $i$에 관한 식이므로 $A[i] = DP[i] + p_i-s_id_i$ 라 하자. 그렇다면 $x = d_v$일 때 $y = s_ix + A[i]$인 선형식으로 나타낼 수 있다. 이런 형태의 DP는 Convex hull trick을 이용해 최적화 할 수 있다.
하지만 $s_i$는 단조 수열이 아니기 때문에 일반적인 Convex hull trick으로 풀 수 없다. 따라서 Dynamic segment tree를 이용한 Convex hull trick을 이용해야 한다. 이를 이용하면 $O(N\log{N})$로 최적화 하여 해결할 수 있다.
K. Steel Slicing
$x$축 상에 늘어져 있는 히스토그램이 있다. 하지만 일반적인 히스토그램과는 다르게 아래로도 높이를 가진다. 이때, 히스토그램 내부에 그릴 수 있는 두 면이 $x$축에 평행한 사각형 중 면적이 가장 큰 사각형의 면적을 구하라.
풀이
L. Two Machines
$n$개의 작업 $t_n$이 주어진다. 두 개의 기계 $A$, $B$가 있는데 작업 $t_n$을 $A$에서 실행하면 $a_n$시간이 들고 $B$에서 실행하면 $b_n$시간이 든다. ($1 \le n, a_i, b_i \le 250$)
각 $t_n$을 $A$ 또는 $B$에 배정하여 모든 작업을 완료할 수 있는 최소 시간을 구하라.
풀이
스케쥴링 문제와 비슷하여 그리디를 생각해 봤었지만, 주어진 범위가 매우 작은것을 봐서는 DP를 의도하고 낸 문제일 것으로 생각된다.
$A$와 $B$ 두 상태를 한번에 고려해야 하므로 두 상태를 한번에 기록할 수 있는 소요 시간의 차이를 인자로 생각해 줄 수 있다. 따라서 다음과 같이 DP테이블을 정의한다.
\[DP[i][j][k] = i\text{번째 작업을 선택할 때, }A\text{와 }B\text{의 시간 차이가 }j\text{인 경우 최소시간}\]이때, $k$는 $A$ 또는 $B$를 나타낸다. 각 $i$에 대해 탐색하면서 $i-1$상태에 대해 $A$에 할당해 주는 경우와 $B$에 할당해 주는 경우에 대해 업데이트 해준다.