2022 IOI 국대교육 1주차 (06/21 ~ 06/24)

1. 국대교육은 아침연습 3문제, 오후실습 3문제로 구성되어있다. 글에 적힌 순서대로 아침연습 123번, 오후실습 123번이다.

2. O는 대회 시간 내로 AC를 받은 문제, △는 업솔빙을 한 문제, X는 업솔빙 안 한 문제이다.

 

06/21

이 날은 학교 수행 때문에 교육을 빠졌다.

 

06/22

BOJ 22491 (Repairing) / X

파이프와 밸브가 여러 개 있고, 밸브를 적절히 잠궈서 끝점에 물이 못 흘러들어가게 해야 한다. 이때, 물이 안 흐르는 구간의 길이의 합을 최소화해야 하고 이 값을 출력해야한다.

 

대충 그래프를 만들었다고 생각하면 끝점에서 bfs 같은걸 돌려서 가장 가까운 밸브들을 전부 잠근 다음 시작점에서 물을 흘려보내서 계산을 하면 될거같다. AC를 받은 사람이 없어서 맞는지는 잘 모르겠지만 아마 맞을 것 같다. 그래프 모델링이 매우매우 귀찮고 지저분할 것 같아서 그냥 안 짰다.

 

BOJ 22484 (A Two Floors Dungeon) / O

던전의 시작점에서 끝점까지 가야하고 이때 최단경로의 길이를 출력해야한다.

 

스위치가 $S$개 있는데 $S \le 10$이니까 그냥 $2^S$가지 상태 모두 생각해서 bfs돌리면 $O(2^S \times WH)$에 문제를 풀 수 있다. 구현이 조금 귀찮다.

 

BOJ 22487 (Do use segment tree) / O

트리가 있고 쿼리 2개를 처리해야한다.

1. $a$에서 $b$로 가는 경로 위의 정점들의 가중치를 $x$로 설정

2. $a$에서 $b$로 가는 경로 위의 정점들의 가중치를 순서대로 적었을 때 최대연속부분합 출력

 

금광세그 + HLD를 짜면 된다. 금광세그를 모른다면 KOI 기출인 "금광"을 풀고 오자.

 

BOJ 7138 (APIO13 robots) / △

로봇 $N$개를 적절히 이동시켜 하나로 합쳐야하는 문제다.

 

일단 각 지점마다 어떤 방향으로 밀었을 때 어디로 가는지 전처리를 해두자. $N \le 9$이므로 $[l...r]$번 로봇이 합쳐져 있고, $(x, y)$에 있다고 모든 상태를 표현하고 저장할 수 있다. 다익스트라나 적절히 변형한 bfs를 돌려서 각 상태에 도달하는데 걸리는 최소 시간을 계산할 수 있다. $N=1$ 데이터와 몇몇 구현 실수로 뇌절을 많이 했다.

 

BOJ 10068 (APIO14 Beads) / O

최종 트리가 주어졌을 때 파란색 간선 가중치 합을 최대화해야 한다.

 

일단, 트리를 만든다고 생각하지 말고 모든 과정을 거꾸로 진행한다고 생각하자. 파란 간선은 2개씩 쌍으로 묶여야 하고, 파란 간선 쌍의 중점이 서로 달라야 한다. 이제 마지막에 남는 정점(마지막에 파란간선 2개만 남는다면 그 중점) 을 기준으로 생각해보면, 그 점과 연결된 서브트리들을 봤을 때 리프쪽부터 차례로 지워나가는 형태로 과정이 진행될 것이다. 이러면 구하려는 답을 트리 dp로 계산이 가능하게 된다.

 

이 방식으로 짜면 부모쪽 트리도 고려해줘야 해서 조금 귀찮은 구현을 해야한다. 마지막 정점을 생각하지 않고 단순히 파란 간선들의 형태를 잘 생각해서 상태 개수가 총 4N인 트리 dp로도 풀 수 있다고 하는데 이건 풀이를 제대로 안 들어서 잘 모르겠다.

 

BOJ 7139 (APIO13 Toll) / △

대회 때 정해 시간복잡도 풀이를 짰는데 상수때문에 터졌다... + 서브태스크 4 아이디어를 예전에 스포당했다.

$K$개의 특별한 간선들이 있고, 이들의 가중치를 적절히 정해서 MST를 만들었을 때 특별한 간선으로 얻을 수 있는 통행료의 최댓값을 구해야 한다.

 

일단 $K$가 작기 때문에 MST에 쓰일 간선 조합을 고정해놓고 문제를 푸는 것을 $2^K$번 하자. 쓰이는 간선이 사이클을 이루는 경우는 당연히 생각할 필요가 없기 때문에 무시할 것이다. 쓰일 간선을 정했다면, 그 간선들을 -INF로 해두고, 나머지 특별한 간선의 가중치는 INF로 해둔 다음 MST를 구하자. 특별한 간선을 제외한 나머지 MST 간선들로 이어진 컴포넌트들을 각각 점 하나로 뭉쳐놓고 생각을 하면, 정점이 $x$개이고 $x-1$개의 특별한 간선으로 구성된 트리가 나오게 된다. 이 트리에서 생각을 이어나가자.

 

모든 특별하지 않은 간선에 대해, 이 간선이 정점 $a$와 $b$를 가중치 $w$로 연결하고 있다면, $a$에서 $b$로 가는 경로에 있는 모든 특별한 간선은 가중치가 $w$이하여야 한다. (MST기 때문) 따라서, 이 경로 업데이트를 매번 해주면 각 특별한 간선에 대해 최대 가중치를 구할 수 있고, 문제의 답을 계산할 수 있다. 시간복잡도는 $O(2^K M(K+\log{M}))$ 이다.

 

서브태스크 4부터는 $M$이 엄청 커지기 때문에 저 풀이를 그대로 적용할 수 없다. 그래서 간선의 개수를 줄이는 것을 목표로 할 것이다. 일단 모든 특별한 간선의 가중치를 -INF로 하고 MST를 구하게 된다면, 그 MST에 쓰이는 모든 특별하지 않은 간선은 반드시 모든 경우에 MST에 속하게 된다. 따라서, 이 간선들로 정점들을 합치면 정점 $O(K)$개가 될 것이고, 각 정점 쌍마다 최소 간선을 선택하면 간선은 $O(K^2)$개가 된다. 이러면 문제를 $O(2^K K^3 \log K)$정도에 풀 수 있고 서브태스크 4까지 맞을 수 있다.

 

놀랍게도 여기서 간선의 개수를 더 줄일 수 있다! 정점의 개수를 줄인 상태에서 특별하지 않은 간선으로 MST를 구하고, MST에 쓰이는 간선들만 남겨두면 간선 $O(K)$개로 만들 수 있다. 이렇게 해도 되는 이유는 크루스칼 알고리즘의 작동방식을 생각하면 꽤나 당연하다고 볼 수 있다. 모든 특별하지 않은 간선의 가중치가 다르기 때문에, 크루스칼 알고리즘을 돌리게 되면 반드시 현재 남겨놓은 간선 중에서 MST 간선이 골라진다는 것을 확인할 수 있다. 따라서, 문제를 $O(2^K K^2 \log{K})$에 풀 수 있다. 로그는 유니온파인드, 정렬 등에 의해 붙을 수 있는데 상수 취급해도 무방한 것 같다.

 

06/23

BOJ 8314 (Acyclic Decomposition) / O

유향그래프를 최소 개수의 DAG들로 분할하는 문제이다.

 

$i<j$이고 $i \rightarrow j$인 간선만 남기면 반드시 DAG이고, $i>j$인 경우도 마찬가지이므로 항상 답은 2이하이다. DAG인지 확인하고 답을 출력하면 된다.

 

BOJ 17348 (국제 옥토끼 기구) / △

트리와 쿼리 N 같은 스타일의 문제다.

 

풀이는 센트로이드 디컴포지션 + 오프라인 쿼리를 이용한다. 구체적인 풀이는 직접 고민해보도록 하자. 다양한 풀이가 존재하는 것 같다. 여담으로 내 풀이는 세그+스위핑을 사용하고, 이걸 PST로 바꾸면 온라인으로 쿼리당 로그제곱에도 풀 수 있다.

 

BOJ 10137 (Freight) / O

$N$개의 기차가 초기에 모두 위에 있고, 이 기차들을 아래로 보낸다음 다시 위로 보내는데 걸리는 최소 시간을 계산해야한다.

 

일단, $i$번째 기차가 출발할 수 있는 실제 최소 시각을 $T[i]$라 하면, $T[i] = \max (T[i-1]+1, A[i])$이다. ($A$가 입력으로 들어온 수열) 이렇게 입력을 받아두고 생각하자.

$[l...r]$번 기차가 아래로 내려갔고, $r+1$번 기차는 내려가지 않았다고 해보자. 그러면 $[l...r]$기차를 남김없이 모두 다시 위로 올려주는게 항상 최적이다. $dp[i] := ([1...i]$번 기차만 있다고 생각했을 때 답$)$이라고 하고, 마지막에 $[j+1...i]$번 기차가 내려갔다가 올라오는 상황을 생각해보면, i번째 기차가 출발하는 시각은 $\max (T[i], dp[j] + (i-j+1) )$일 것이고, 내려가는데 $s$, 모든 기차가 올라오는데 $(i-j+1)+s$의 시간이 걸린다. 따라서, 다음 점화식이 성립한다.

$$dp[i] = \min_{j<i} ( \max (a[i], dp[j] + len) + len + 2s )$$

(단, $len = i-j+1$)

 

이를 나이브하게 계산하면 $O(N^2)$이기 때문에, 최적화를 해줘야 한다. $j=i-1$인 상태에서 $j$를 1씩 줄여보면서 값들이 어떻게 변하는지 보자. $dp[j]$는 2 이상씩 감소하고, $len$은 정확하게 1 증가한다는 사실을 알 수 있다. (이유는 직접 생각해보자.) 따라서, $\max (a[i], dp[j] + len) = dp[j] + len$이 성립하다가, 어느 순간 이 값이 $a[i]$로 바뀌게 된다. 바뀌는 시점을 $x \rightarrow x-1$이라고 하고, $j$를 줄이면서 $\max (a[i], dp[j]+len) + len$이 어떻게 변하는지 케이스를 나눠서 생각해보자.

 

case 1) $j \ge x$일 때

$j$를 줄이면 $len$은 정확하게 1 증가하고, $dp[j]$는 2 이상 감소하기 때문에, $j=x$일 때 $ (dp[j]+len) + len$가 최소이다.

 

case 2) $j < x$일 때

$j$를 줄여도 $a[i]$는 고정이고, $len$만 1 증가하기 때문에 $j=x-1$일 때 $a[i] + len$가 최소이다.

 

따라서, $j = x-1$일 때랑 $j=x$일 때만 계산하면 $dp[i]$를 알 수 있다.

$x$는 이분탐색을 이용해서 구할 수도 있고, $i$가 증가하면 $x$는 단조증가한다는 사실을 이용해서 투포인터로 계산할 수도 있다. 각각 시간복잡도는 $O(N\log N)$, $O(N)$이고, 둘 다 AC를 받는다.

 

BOJ 17699 (JOISC16/17 Mansion) / △

일렬로 나열된 $N$개의 방이 있고 몇 개의 열쇠가 주어질 때, $x$번 방에서 $y$번 방으로 갈 수 있는지 $Q$번 판별해야 하는 문제이다.

 

$i$번 방에서 도달할 수 있는 방들은 구간으로 나타날 것이고, 이를 $[s_i, e_i]$라고 하자. 이 구간을 모든 $i$에 대해 구하는 것을 목표로 할 것이다. $[x, i]$에 있는 열쇠만을 사용하여 $i+1$번 방으로 갈 수 있는 최대의 $x$를 $l_i$, $[i, y]$에 있는 열쇠만을 사용하여 $i-1$번 방으로 갈 수 있는 최소의 $y$를 $r_i$라고 하자.

 

더 이상 확장이 불가능한 구간 $[i, j]$의 필요충분조건은 $r_i > j$ 이면서 $l_j < i$인 것이다. 고정된 $i$에 대해 생각을 해보면 이를 만족하는 $j$는 여러 개가 있을 것이고, 그 중 최댓값을 $mx$라고 하면 $[i, mx]$ 구간에 있는 모든 $k$에 대해, $s_k \ge i$를 만족해야한다. 따라서, 모든 $i$에 대해 보면서 이러한 range update를 해주면 모든 $s_i$를 정확하게 구할 수 있고, $e_i$도 마찬가지로 계산이 가능하다. 세그먼트 트리를 이용하면 이 과정을 $O(N\log N)$에 해줄 수 있다.

 

별해) 방문할 수 있는 구간의 초기값을 $[i, i]$로 두고, 왼쪽으로 최대한 늘리고, 오른쪽으로 최대한 늘리고, 다시 왼쪽으로 최대한 늘리고, ... 이 과정을 반복해보자. 한 쪽 방향으로 최대한 늘리는 것은 적절한 전처리와 자료구조를 이용해 $O(\log N)$에 할 수 있다. 이 과정을 모든 $i$에 대해 했을 때, 나오는 구간의 개수는 $O(N)$개라는 사실을 증명할 수 있고, 따라서 메모이제이션을 섞으면 $O(N \log N)$에 문제를 풀 수 있다. 증명은 되게 까다로운 편이다.

 

BOJ 17694 (JOISC16/17 Sparklers) / △

초기에 1명한테만 불꽃이 있을 때, $N$명 모두에게 불꽃을 전달해주기 위한 최소 속도를 구해야 한다.

 

일단 parametric search를 한다고 생각을 하자. 즉, 속도 $s$를 고정해두고 가능한지 판별할 것이다. 불꽃을 갖고 있는(혹은 갖고 있었던) 사람들은 구간으로 나타날 것이고, 최적의 전략은 이들이 겹쳐있는 상태로 같이 움직이는 것이다. (증명은 따로 안 하겠다) 또한, $x$명의 사람이 겹쳐있는 것은 불꽃의 지속시간이 $xt$인 것과 동일하다. $dp[l][r]$을 $[k-l, k+r]$ 구간의 사람이 불꽃을 유지하면서 한 곳에 모여있을 수 있는지를 나타낸다고 하자. 일단 불꽃이 유지되려면 $A[r] - A[l] \le 2st(r-l)$이 성립해야하고, $dp[l][r]$이 참이려면 $dp[l-1][r]$, $dp[l][r-1]$ 중 하나가 성립해야한다. 이를 이용하면 $dp[l][r]$에 대한 점화식을 얻을 수 있고, $O(N^2 \log X)$에 문제를 풀 수 있다.

 

이제, 이 과정을 최적화해야하는데, 이 부분은 https://psforhobby.tistory.com/31 를 참고하자. 

 

BOJ 17738 (JOISC13/14 Voltage) / △

무향그래프가 주어지면 $(s_i, e_i)$ 간선에 대해 $s_i$와 $e_i$의 색은 같게 하면서, 나머지 모든 간선에 대해 양 끝점의 색이 다르게 2-coloring을 할 수 있는 $(s_i, e_i)$ 간선의 개수를 구하는 문제이다.

 

일단 기존 그래프가 이분그래프면 단절선들이 답이 되고, 홀수사이클이 있다면 답이 될 수 있는 간선은 모든 홀수사이클에 속해야 한다.

 

dfs를 돌려서 dfs tree를 만들고 색칠을 해놓자. back edge 중 같은 색을 잇는 back edge를 odd edge, 나머지 back edge를 even edge라고 하자. 답의 조건을 생각해보면 모든 even edge는 답이 아니고, odd edge는 정확히 1개만 있을 때만 답에 포함된다.

dfs tree에 존재하는 간선에 대해 생각을 해보자. 이 간선을 지우게 되면 dfs tree는 2개의 컴포넌트 $A$와 $B$로 쪼개지게 된다. $A$와 $B$를 잇는 even edge가 존재한다면 이는 답이 될 수 없다. odd edge의 경우, 모든 odd edge가 끝점이 각각 $A$와 $B$에 존재해야한다.

 

따라서, odd edge의 경우 경로에 있는 모든 간선에 1을 더하고, even edge의 경우 경로에 있는 모든 간선에 -INF를 더했을 때, 답이 되는 간선은 가중치가 odd edge의 개수와 동일한 간선들이다. 이는 HLD를 이용해서 무지성으로 구현해도 되고, dfs를 적절히 돌려서 계산할 수도 있다.

 

06/24

BOJ 18184 (분할하기) / O

평범한 construction 문제다. 집합 $\left\{0, 1, \ldots , 2^N-1 \right\}$을 두 집합 $S$와 $T$로 분할해야하는데, $S$의 임의의 두 원소의 bitwise OR 값이 $S$에 속해야하고, $T$도 마찬가지다. 이때, $|S| = K$를 만족하는 분할을 찾는 문제이다.

 

$S_i := \left\{ x | x\&(2^{i+1}-1) = 2^{i} \right\}$라고 정의하자. ($\&$는 bitwise AND이다.) 즉, 마지막 $i+1$개의 비트가 $100 \ldots 00$인 수들의 집합이다. $|S_i| = 2^{N-i-1}$이고, $S_i$는 조건을 만족하며, $S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_j}$도 조건을 만족하는 집합이다. 따라서, $K$에서 켜진 비트에 대해 $S_i$들을 합집합 해주면 답을 구할 수 있다. $K=2^N$인 경우는 예외처리를 해줘야 한다.

 

BOJ 17671 (JOISC18/19 Antennas) / △

$N$개의 안테나가 있고 $[l, r]$ 구간에서 서로 통신 가능한 안테나 쌍 중 높이 차이의 최댓값을 출력하는 $Q$개의 쿼리를 처리해야한다.

 

$i<j$이면서, 통신 가능한 쌍의 $H_i - H_j$의 최댓값을 구하는 것을 목표로 하자. $H_i$의 부호를 뒤집고 동일한 과정을 한 번 더 하면 문제에서 요구하는 답을 구할 수 있다. $ans[i] = ($통신 가능한 $j>i$에 대해 $H_i - H_j$의 최댓값$)$라고 하고, 스위핑을 하면서 이 값을 세그에서 갱신할 것이다.

 

$i$번 안테나는 $i+A[i]$이상, $i+B[i]$이하인 안테나를 볼 때만 $ans[i]$가 갱신되기 때문에, $i+A[i]$에 도달하면 $i$번 값을 세그에서 켜주고, $i+B[i]+1$에 도달하면 세그에서 꺼주자. 현재 $j$를 보고 있으면 세그에서 $[j-B[j], j-A[j]]$구간에 대해 업데이트를 해야하는데, 이 중 켜진 $i$에 대해 $ans[i] = \max(ans[i], H[i] - H[j])$로 업데이트를 해줘야 한다. 이 두 가지 연산은 lazy propagation을 이용한 세그먼트 트리로 구현할 수 있고, 답은 $r$까지 $ans[i]$를 계산했을 때 세그에 $[l, r]$구간 쿼리를 날리면 구할 수 있다. 시간복잡도는 $O((N+Q)\log N)$이다.

 

BOJ 20197 (COCI20/21 3D Histogram) / X

3차원 히스토그램이 주어지고 히스토그램에 포함되는 최대 직육면체 부피를 구해야 한다.

 

분할정복 + 세그먼트트리 + cht로 해결 가능하다고 한다. 여러 케이스를 따져야 하고 구현도 더러워보여서 업솔빙할 생각이 없다.

 

BOJ 17643 (CEOI19 Amusement Park) / O

유향그래프가 주어지고, 이 중 몇 개의 간선을 골라서 방향을 바꿀 것이다. 그렇게 해서 만든 그래프가 DAG일 때, 바꾼 간선의 개수만큼 점수를 얻는다. $2^M$가지 경우에 대해 이 점수를 전부 더해서 $MOD$로 나눈 나머지를 출력해야 한다.

 

어떤 집합을 선택했을 때 DAG라면, 그 여집합을 선택해도 DAG이므로, 답은 DAG의 개수에 $\frac{M}{2}$를 곱한 것이라는 것을 알 수 있다. 따라서, DAG의 개수만 세주면 충분하다.

 

$dp[msk] := (msk$에서 켜진 비트에 해당하는 점만 있다고 생각했을 때 DAG의 개수$)$ 라고 하자. $submsk$에서 켜진 비트에 해당하는 점들이 indegree가 0인 DAG의 개수는 $I[submsk] \times dp[msk \oplus submsk]$라는 것을 알 수 있다. ($I[z]$는 $z$에서 켜진 비트에 해당하는 점들이 독립집합을 이루면 1, 아니면 0이다.)

포함과 배제의 원리에 의해,

$$dp[msk] = \sum _{submsk \subseteq msk}{(-1)^{|submsk|-1} \times I[submsk] \times dp[msk \oplus submsk]}$$

가 성립하고, 이는 $O(3^N)$에 계산할 수 있다.

 

여담으로 나는 답이 DAG의 개수에 $\frac{M}{2}$를 곱한 값이라는 사실을 관찰하지 못 했고, 포함과 배제의 원리를 이용해서 답을 직접 계산했다.

 

BOJ 17644 (CEOI19 Magic Tree) / O

루트가 있는 트리가 주어지고, 정점에 최대 1개의 열매가 열릴 수 있을 때, 적절한 순서로 간선을 잘라서 얻을 수 있는 돈의 최댓값을 구해야 한다.

 

$dp[v][t] := ($정점 $v$의 서브트리에서, 시각 $t$에 얻을 수 있는 돈의 최댓값$)$라고 하면 간단한 $O(NK)$ dp를 돌릴 수 있다. 실제 고려해야하는 $t$들은 $v$의 서브트리에 있는 열매들이 열리는 시각뿐이므로, $dp[v]$는 $v$의 서브트리 크기에 비례하는 양의 정보만 저장하면 충분하다. 따라서, 적절한 자료구조와 small-to-large trick을 이용해서 문제를 $O(N\log^2 N)$ 정도에 해결할 수 있다. 나는 세그트리를 사용해서 구현이 길고 디버깅을 오래했는데, std::multiset 등을 이용하면 더 쉽고 간단하게 짤 수 있다고 한다.

 

BOJ 16029 (CEOI18 Fibonacci) / X

수열 $A$가 주어진다. 모든 $N$이하 자연수 $i$에 대해, $F_{A[1]}+ F_{A[2]} + \cdots + F_{A[i]}$를 서로 다른 피보나치 수들의 합으로 나타내는 방법의 수를 $MOD$로 나눈 나머지를 출력해야 한다.

 

먼저, 한 가지 함수를 정의하자.

$S(str) = (str[i] = 1$인 $i$에 대해 $F_i$를 모두 더한 값$)$ (단, $str$은 1-based 무한이진수열이다.)

예시로, $S(101101000...) = F_{1} + F_{3} + F_{4} + F_{6}$이다.

 

일단, 어떤 수 $x$를 서로 다른 피보나치 수들의 합으로 나타내는 방법의 수를 구해보자. Zeckendorf's theorem라는 게 있는데, 요약하면 임의의 자연수는 인접하지 않은 피보나치 수들의 합으로 나타내는 방법이 항상 존재하고, 이는 유일하다는 정리이다. 이 방식으로 $x$를 전개해놓고 생각하자. 즉, $x = F_{a_1} + F_{a_2} + \cdots + F_{a_k}$, $a_1 < a_2 < \cdots < a_k$라고 하자. 또한, 편의상 $a_0 = 0$이라고 하자.

 

$F_x$를 썼고, $F_{x-1}, F_{x-2}$를 안 쓴 상태에서 $F_x$를 $F_{x-1} + F_{x-2}$로 바꾸는 시행을 "펼친다"고 하자. 이때, 얻을 수 있는 모든 fibonacci representation(서로 다른 피보나치 수들의 합으로 나타내는 방법)은 Zeckendorf representation에서 펼치는 시행을 유한 번 반복해 얻을 수 있다. 이는 따로 증명하지 않을 것이다. (사실 증명을 모른다.)

 

펼칠 수 있는 최대횟수를 먼저 구해보면, $a_i$는 최대 $\lfloor \frac{a_i-a_{i-1}-1}{2} \rfloor$번 펼칠 수 있고, $a_{i-1}$을 한번이라도 펼쳤고 $a_i$와 $a_{i-1}$의 거리가 짝수라면, $a_i$는 추가로 한 번 더 펼칠 수 있다.

 

예시를 들어 생각해보자.

$S(...100000100...) = S(...011000100...) = S(...010110100...)$ 를 생각해보면, 초기에 인접한 $a_i$의 거리는 6이었기 때문에 최대 2번 펼칠 수 있다.

마지막 상태에서 오른쪽 1을 펼치면 $S(...010110011...)$이 될 것이고, 이 상태에서 왼쪽 1을 한 번 더 펼쳐서 $S(...010101111...)$로 만들 수 있다.

 

따라서, 다음과 같은 dp를 돌려서 답을 구할 수 있다.

$dp[i][0]:=(a_i$까지 봤을 때 $a_i$를 펼치지 않은 fibonacci representation의 개수$)$

$dp[i][1]:=(a_i$까지 봤을 때 fibonacci representation의 개수$)$

(단, $dp[0][0] = dp[0][1] = 1$)

 

$$dp[i][0] = dp[i-1][0]$$

$$dp[i][1] = \begin{cases}
dp[i-1][1] \times \frac{a_i-a_{i-1}+1}{2} \quad &(\text{if}\;2 \nmid a_i-a_{i-1})\\
dp[i-1][1] \times \frac{a_i-a_{i-1}}{2} + (dp[i-1][1] - dp[i-1][0]) \quad &(\text{if}\;2 \mid a_i-a_{i-1})\\
\end{cases}$$

 

이제, 2가지 최적화를 해야한다.

1. 현재 값에 $F_i$를 더했을 때 Zeckendorf representation을 빠르게 갱신

2. Zeckendorf representation가 변할 때, dp값을 빠르게 갱신

 

일단 2번부터 생각해보자. 위 dp식을 행렬로 다시 적어보면

$$\begin{pmatrix}
    dp[i][0] \\
    dp[i][1]
\end{pmatrix}
=
\begin{pmatrix}
    dp[i-1][0] \\
    dp[i-1][1]
\end{pmatrix}
\begin{pmatrix}
    0 & x \\
    1 & y
\end{pmatrix}$$

와 같이 적을 수 있다. ($x$와 $y$는 적당한 상수) 이렇게 표현하면, 이 행렬들을 세그먼트 트리와 같은 자료구조에 담아서 빠르게 답을 업데이트해줄 수 있다.

 

1번의 경우, Zeckendorf representation을 다음과 같은 "블록"들로 쪼개서 관리할 것이다. $10101...01$꼴의 부분문자열과 $000...0$꼴의 부분문자열을 "블록"이라고 하고, Zeckendorf representation를 이 블록들로 쪼개서 저장하자. $F_i$가 더해지면 상수 개의 블록을 쪼개고 합쳐서 Zeckendorf representation를 갱신해줄 수 있고, 행렬들도 적절히 갱신해주면 답을 빠르게 계산할 수 있다.

 

이 과정을 적절한 자료구조나 트릭(sqrt decomposition 등)을 이용해서 충분히 빠르게 풀면 100점을 받을 수 있다.