AtCoder Typical DP Contest 풀이

작성일 | In

서론

AtCoder Typical DP Contest (link)의 풀이입니다. solved.ac 기준 골드 하위권부터 다이아 중위권 정도 범위의 문제를 다룹니다.

TDPC는 2013년에 열린 대회이므로 최근에 유행한 테크닉을 공부하길 원한다면 다른 대회를 참고하는 것이 좋을 수 있습니다. 2026년에 개최된 AtCoder Next DP Contest (link) 도 함께 공부하는 것을 추천합니다.

유형과 solved.ac 기준 체감 난이도는 다음과 같습니다.

문제 유형 난이도
A. コンテスト (Contest) 배낭 문제 G5
B. ゲーム (Game) 게임 이론 G3
C. トーナメント (Tournament) 확률 DP, 트리 DP G2 - P5
D. サイコロ (Dice) 확률 DP, 정수론 G4 - G2
E. 数 (Number) Digit DP P3
F. 準急 (Semiexp) 누적 합 G2 - P5
G. 辞書順 (Lexicographical) 사전순 $K$번째 P5 - P3
H. ナップザック (Knapsack) 배낭 문제, 토글링 P4 - P2
I. イウィ (Iwi) 구간 DP G1 - P4
J. ボール (Ball) 확률 DP, 비트 DP P5 - P3
K. ターゲット (Target) LIS P4
L. 猫 (Cat) 누적 합 P5 - P3
M. 家 (House) TSP, 인접 행렬 제곱 P4 - P2
N. 木 (Tree) 조합론 P3
O. 文字列 (String) 조합론 P1 - D4
P. うなぎ (Eel) 트리 DP, 검은돌 D5 - D3
Q. 連結 (Concat) 비트 DP P3 - P1
R. グラフ (Graph) SCC, 바이토닉 투어 P1
S. マス目 (Grid) Connection Profile DP D3
T. フィボナッチ (Fibonacci) 선형 점화식 D4

제가 작성한 코드는 https://atcoder.jp/contests/tdpc/submissions?f.Status=AC&f.User=justiceHui 에서도 확인할 수 있습니다.

A. コンテスト (Contest)

대회에 $N$개의 문제가 출제되었고, $i$번 문제의 점수는 $p_i$이다. 대회에서 나올 수 있는 서로 다른 점수의 수를 구하는 문제
$1 \le N \le 100$; $1 \le p_i \le 100$

$1, \cdots, i$번 문제만 고려했을 때 $j$점을 만들 수 있을 때 $D(i, j) = 1$ 이라고 합시다. 상태 전이는 $D(i, j) \leftarrow D(i-1, j-A_i)$ 와 같이 나타낼 수 있습니다. $D$ 배열을 일차원 배열로 만들 수도 있고, 구체적인 방법은 이 슬라이드의 29페이지 이후(동적 계획법 - 예시 7. BOJ 12865 평범한 배낭)을 참고하면 됩니다.

시간 복잡도는 $O(N\sum A_i)$입니다.

1
2
3
4
5
6
7
8
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    S = accumulate(A+1, A+N+1, 0);
    D[0] = 1;
    for(int i=1; i<=N; i++) for(int j=S; j>=A[i]; j--) D[j] |= D[j-A[i]];
    cout << accumulate(D, D+S+1, 0) << "\n";
}

bitset 을 이용해 연산량을 $1/64$배 수준으로 줄일 수도 있습니다.

1
2
3
4
5
6
void Solve(){
    int N; cin >> N;
    bitset<10101> D; D[0] = 1;
    for(int i=1,t; i<=N; i++) cin >> t, D |= D << t;
    cout << D.count() << "\n";
}

B. ゲーム (Game)

두 개의 카드 더미가 있다. 첫 번째 더미에 있는 카드는 위에서부터 각각 $a_1, a_2, \cdots, a_A$가, 두 번째 더미에 있는 카드는 위에서부터 $b_1, b_2, \cdots, b_B$가 적혀 있다. 두 명의 플레이어가 번갈아 가며 원하는 카드 더미의 맨 위에 있는 카드 한 장을 갖고 간다. 두 플레이어 모두 자신이 가져간 카드에 적힌 수의 합을 최대화하기 위해 최선을 다할 때, 선공이 가져간 수의 합을 구하는 문제
$1 \le A,B \le 1\,000$

지금까지 첫 번째 더미에서 $i$장, 두 번째 더미에서 $j$장 가져갔을 때, 앞으로 선공이 추가로 얻게 될 점수를 $D(i, j)$라고 합시다.

$i+j$ 가 짝수일 때는 선공 차례이므로 $D(i, j)$를 최대화, $i+j$ 가 홀수일 때는 후공 차례이므로 $D(i, j)$를 최소화해야 합니다. 따라서 $i+j$가 짝수면 $D(i, j) = \max\lbrace D(i+1, j) + A_{i+1}, D(i, j+1) + B_{j+1}\rbrace$, 홀수면 $D(i, j) = \min\lbrace D(i+1, j), D(i, j+1)\rbrace$로 계산하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int f(int i, int j){
    if(i == N && j == M) return 0;

    int &res = D[i][j];
    if(res != -1) return res;
    if((i + j) % 2 == 0){ // maximize
        res = 0;
        if(i < N) res = max(res, f(i+1, j) + A[i+1]);
        if(j < M) res = max(res, f(i, j+1) + B[j+1]);
    }
    else{ // minimize
        res = 1e9;
        if(i < N) res = min(res, f(i+1, j));
        if(j < M) res = min(res, f(i, j+1));
    }
    return res;
}

void Solve(){
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=M; i++) cin >> B[i];
    memset(D, -1, sizeof D);
    cout << f(0, 0) << "\n";
}

C. トーナメント (Tournament)

$2^K$명이 토너먼트에 참가한다. $i$번 사람의 레이팅은 $R_i$이고, 레이팅이 $R_p$인 사람과 $R_q$인 사람이 대결할 때 $p$가 승리할 확률은 $1/(1+10^{(R_q-R_p)/400})$ 이다. $1 \le i \le 2^K$에 대해 $i$번 사람이 승리할 확률을 각각 구하는 문제
$1 \le K \le 10$

세그먼트 트리의 구조를 생각하면, 토너먼트의 과정은 정점이 $2^{K+1}-1$개인 이진 트리로 표현할 수 있습니다. 트리의 $x$번 정점에서의 승자가 $p$일 확률을 $D(x, p)$라고 정의합시다.

어떤 두 사람 $a, b$가 대결할 때 $l$이 승리할 확률을 $f(a, b)$라고 하면, $x$의 왼쪽 구간에 속한 사람 $l$과 오른쪽 구간에 속한 사람 $r$이 각각 올라왔을 때 아래와 같이 상태 전이를 할 수 있습니다.

  • $D(x, l) \leftarrow D(2x, l) \times D(2x+1, r) \times f(l, r)$
  • $D(x, r) \leftarrow D(2x, l) \times D(2x+1, r) \times (1-f(l,r))$

크기가 $2^t$인 구간의 답을 계산하는 데 $O(2^{t/2} \times 2^{t/2}) = O(2^t)$ 만큼의 시간이 걸리고, 크기가 $2^t$인 구간은 $2^K / 2^t = 2^{K-t}$개 존재합니다. 따라서 전체 시간 복잡도는 $O(K\times 2^K)$입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
double f(double rp, double rq){
    return 1 / (1 + pow(10, (rq-rp)/400));
}

void Go(int node, int s, int e){
    if(s == e){ D[node][s] = 1; return; }
    int m = (s + e) / 2;
    Go(node*2, s, m);
    Go(node*2+1, m+1, e);
    for(int l=s; l<=m; l++){
        for(int r=m+1; r<=e; r++){
            double p = f(A[l], A[r]);
            D[node][l] += D[node*2][l] * D[node*2+1][r] * p;
            D[node][r] += D[node*2][l] * D[node*2+1][r] * (1 - p);
        }
    }
}

void Solve(){
    cin >> K; N = 1 << K;
    for(int i=0; i<N; i++) cin >> A[i];
    Go(1, 0, N-1);
    for(int i=0; i<N; i++) cout << fixed << setprecision(20) << D[1][i] << "\n";
}

D. サイコロ (Dice)

1부터 6까지의 수가 적힌 정육면체 주사위를 $N$번 던졌을 때, 나온 수들의 곱이 $D$의 배수가 될 확률을 구하는 문제
$1 \le N \le 100$; $1 \le D \le 10^{18}$

주사위는 1부터 6까지의 수만 만들 수 있으므로, $D$가 7 이상의 수를 소인수로 갖는다면 답은 0입니다. 따라서 2, 3, 5만으로 구성된 수만 고려해도 충분합니다.

주사위를 $i$번 던져서 2, 3, 5를 각각 $a, b, c$번 만들 확률을 $E(i,a,b,c)$라고 정의합시다. $D \le 10^{18}$ 이므로 $a \le 60, b\le 40, c \le 30$ 정도 범위만 고려해도 괜찮으며, 따라서 제한 시간 안에 답을 구할 수 있습니다. 전체 시간 복잡도는 $O(N \times \log_2 D \times \log_3 D \times \log_5 D) \approx O(\frac{N\log_2^3 D}{3.68})$ 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Solve(){
    cin >> N >> K;
    D[0][0][0][0] = 1;
    for(int i=0; i<N; i++){
        for(int x=0; x<60; x++){
            for(int y=0; y<40; y++){
                for(int z=0; z<30; z++){
                    const auto now = D[i][x][y][z];
                    if(now == 0) continue;
                    for(int d=1; d<=6; d++){
                        int xx = min(x + (d % 2 == 0) + (d % 4 == 0), 59);
                        int yy = min(y + (d % 3 == 0), 39);
                        int zz = min(z + (d % 5 == 0), 29);
                        D[i+1][xx][yy][zz] += now / 6;
                    }
                }
            }
        }
    }

    int x = 0, y = 0, z = 0;
    while(K % 2 == 0) K /= 2, x++;
    while(K % 3 == 0) K /= 3, y++;
    while(K % 5 == 0) K /= 5, z++;
    if(K != 1){ cout << "0\n"; return; }

    double res = 0;
    for(int i=x; i<60; i++) for(int j=y; j<40; j++) for(int k=z; k<30; k++) res += D[N][i][j][k];
    cout << fixed << setprecision(20) << res << "\n";
}

E. 数 (Number)

$N$ 이하의 양의 정수 중, 10진법으로 표기했을 때 각 자릿수의 합이 $D$의 배수인 수의 개수를 구하는 문제
$N \le 10^{10000}$; $1 \le D \le 100$

“$N$ 이하” 라는 조건이 없다면 길이가 $i$이고, 각 자릿수의 합을 $D$로 나눈 나머지가 $j$인 수의 개수 $A(i, j)$를 세면 되겠지만, 귀찮은 조건이 하나 붙어있습니다.

이런 문제는 leading zero를 허용한 채로 항상 길이가 $N$과 동일한 문자열을 만든다고 생각하는 것이 편합니다. 앞에서부터 한 자리씩 결정하면서, 지금까지 $N$을 그대로 따라가고 있는지, 아니면 이미 $N$보다 작아졌는지를 관리하는 변수 $mx$를 포함해서 점화식을 $A(i, j, mx)$와 같이 세우면 됩니다.

이런 유형을 digit dp 라고 부릅니다. 구체적인 구현 방식은 아래 코드를 참고하세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int N, K; string S;
ll D[10101][111][2]; // len, sum, mx

void Solve(){
    cin >> K >> S; N = S.size();
    D[0][0][1] = 1;
    for(int len=0; len<N; len++){
        for(int sum=0; sum<K; sum++){
            for(int mx=0; mx<2; mx++){
                const ll now = D[len][sum][mx];
                if(!now) continue;
                for(int d=0; d<10; d++){
                    if(mx && d > S[len]-'0') break;
                    Add(D[len+1][(sum+d)%K][mx&&d==S[len]-'0'], now);
                }
            }
        }
    }
    cout << (D[N][0][0] + D[N][0][1] - 1 + MOD) % MOD << "\n";
}

F. 準急 (Semiexp)

$N$개의 역이 일렬로 배치되어 있다. 급행 열차는 1번 역에 정차한 뒤, $\lbrace2, 3, \cdots, N-1\rbrace$번 역의 일부에 정차하고, 마지막에 $N$번 역에 정차한다. 연속한 $K$개 이상의 역에 모두 정차하면 안 된다고 할 때, 급행 열차가 정차하는 역의 조합으로 가능한 경우의 수를 구하는 문제
$2 \le K \le N \le 1\,000\,000$

$N-2$개의 역에 대해 각각 정차 여부를 결정하는 문제입니다. 편의상 $2, 3, \cdots, N-1$번 역을 $1, 2\cdots,N-2$ 로 표현합시다. 정차할 역보다는 정차하지 않는 역 기준으로 생각하는 것이 더 편합니다.

조건을 만족하도록 $1, 2, \cdots, i$번 역의 정차 여부를 정했고, $i$번 역에 정차하지 않는 방법의 수를 $D(i)$라고 정의합시다. $i$번 역 직전에 통과한 역이 $j$라면, 그 사이에 있는 $i-j-1$개의 역에 정차를 해야 하고, 이 값은 $K$ 미만이어야 합니다. $i-K \le j < i$ 가 성립해야 하므로, $D(i) = \sum_{j=i-K}^{i-1} D(j)$와 같이 점화식을 세울 수 있습니다.

또한, $i < K$ 이면 $i$번 역이 처음으로 정차하지 않는 역이 될 수 있습니다. 따라서 이 경우 $D(i)$를 1 증가시켜야 합니다.

누적 합 배열을 이용하면 각 상태의 답을 상수 시간에 계산할 수 있으므로 $O(N)$ 시간에 $D$배열을 모두 계산할 수 있으며, 문제의 답은 $\sum_{i=N-K}^{N-2} D(i)$입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll N, K, D[1010101], S[1010101];
ll f(int l, int r){
    if(l > r || r < 0) return 0;
    return (S[r] - (l > 0 ? S[l-1] : 0) + MOD) % MOD;
}

void Solve(){
    cin >> N >> K;
    if(N <= 2){ cout << "1\n"; return; }

    for(int i=1; i<=N-2; i++){
        D[i] = f(i-K, i-1);
        if(i < K) D[i] = (D[i] + 1) % MOD;
        S[i] = (S[i-1] + D[i]) % MOD;
    }
    cout << f(N-K, N-2) << "\n";
}

G. 辞書順 (Lexicographical)

길이가 $N$인 문자열 $S$와 양의 정수 $K$가 주어진다. 중복을 제외하고 $S$의 subsequence 중 사전순 $K$번째인 것을 구하는 문제
$1 \le N \le 10^6$; $1 \le K \le 10^{18}$

일반적으로 서로 다른 부분 수열의 개수를 세는 문제에서는, 다음 문자를 고를 때 최대한 앞에 있는 위치를 선택해서 일종의 canonical form만 고려하는 것이 편합니다. $F(i,c)$를 $i$보다 뒤에서 $c$가 등장하는 첫 위치라고 정의합시다. $F$ 배열은 뒤에서부터 계산하면 $O(26N)$ 시간에 계산할 수 있습니다.

$D(i)$를 $i$ 또는 그 이후에 있는 문자만 사용해서 만들 수 있는 서로 다른 부분 수열의 개수라고 정의합니다. 주어진 문자열 $S$에서 만들 수 있는 서로 다른 부분 수열의 개수는 $\sum_{c=0}^{25} D(f(0,c))$ 이고, 이 값이 $K$보다 작다면 Eel을 출력하면 됩니다. 뒤에서부터 계산하면 $D(\ast)$도 $O(26N)$ 시간에 계산할 수 있습니다.

$K$번째 부분 수열이 존재한다면, 이를 구하는 것은 어렵지 않습니다. 마지막으로 사용한 문자의 위치를 $x$라고 합시다. $x$의 초깃값은 0입니다.

$c$를 0부터 차례대로 보면서, $K > D(F(x,c))$ 라면 $K$번째 부분 수열은 뒤에 $c$보다 큰 문자를 붙여야 한다는 것을 알 수 있습니다. 따라서 $K$에서 $D(F(x,c))$를 뺀 뒤에 다른 $c$를 확인하면 됩니다.

$K \le D(F(x,c))$ 라면 뒤에 $c$가 붙은 부분 수열 중 우리가 원하는 부분 수열이 있다는 것을 의미합니다. 따라서 $x$를 $F(x,c)$로 이동시킨 뒤 같은 과정을 계속 반복하면 됩니다. 부분 수열의 마지막 문자가 $c$인 경우도 고려해야 하므로 이 경우에도 $K$를 1 감소시켜야 하고, $K = 0$이 되는 순간에 종료하면 됩니다.

$F$와 $D$를 각각 $O(26N)$에 구할 수 있고, $K$번째 부분 수열을 복원하는 것도 $O(26N)$ 시간에 할 수 있습니다. 따라서 전체 시간 복잡도는 $O(26N)$입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void Solve(){
    cin >> S >> K; N = S.size();
    for(int i=1; i<=N; i++) A[i] = S[i-1] - 'a';

    memset(L, -1, sizeof L);
    for(int i=N; i>=1; i--) memcpy(F[i], L, sizeof F[i]), L[A[i]] = i;
    memcpy(F[0], L, sizeof F[0]);

    D[N+1] = 1;
    for(int i=N; i>=1; i--){
        D[i] = 1;
        for(int j=0; j<26; j++) if(F[i][j] != -1) D[i] = min(D[i] + D[F[i][j]], K + 1);
    }

    ll total = 0;
    for(int i=0; i<26; i++) if(F[0][i] != -1) total = min(total + D[F[0][i]], K + 1);
    if(total < K){ cout << "Eel\n"; return; }

    int x = 0;
    while(K > 0){
        for(int i=0; i<26; i++){
            if(F[x][i] == -1) continue;
            if(K <= D[F[x][i]]){ cout << char('a'+i); x = F[x][i]; K--; break; }
            else K -= D[F[x][i]];
        }
    }
    cout << "\n";
}

H. ナップザック (Knapsack)

$N$개의 물건이 있다. $i$번째 물건의 무게는 $w_i$, 가치는 $v_i$, 색깔은 $c_i$이다. 최대 $C$가지 종류의 물건만 선택해 무게의 합을 $W$ 이하로 만들었을 때, 가능한 가치 합의 최댓값을 구하는 문제
$1 \le N \le 100$; $1 \le W, w_i, v_i \le 10^4$; $1 \le C, c_i \le 50$

사용한 색깔의 개수를 관리하기 위해 점화식에 $2^C$짜리 비트 집합을 넣기에는 $C$가 너무 큽니다. 물건들을 색깔 오름차순으로 정렬해 색이 같은 물건끼리 인접한 위치에 오도록 만든 다음, “$i$번 물건과 같은 색을 사용한 적 있는가?” 와 같은 변수를 추가하는 방법을 생각해 볼 수 있습니다.

$D(n,w,c,u)$를 $1, \cdots, n$번 물건만 고려했을 때, 무게의 합이 $w$, 사용한 색깔의 개수가 $c$이면서 $n$번 물건과 같은 색의 물건을 사용한 적 있는지의 여부가 $u$일 때 가능한 가치 합의 최댓값이라고 정의합시다. $c_{i-1}$과 $c_{i}$가 같은지 다른지에 따라 점화식이 조금 다릅니다.

전체 시간 복잡도는 $O(NWC)$입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct Info{ int w, v, c; };
void Max(int &a, int b){ a = max(a, b); }
int N, W, C, D[2][10101][55][2];
Info A[111];

void Solve(){
    cin >> N >> W >> C;
    for(int i=1; i<=N; i++) cin >> A[i].w >> A[i].v >> A[i].c;
    sort(A+1, A+N+1, [](auto a, auto b){ return a.c < b.c; });

    memset(D, 0xc0, sizeof D);
    D[0][0][0][0] = 0;
    for(int i=1; i<=N; i++){
        memset(D[i&1], 0xc0, sizeof D[i&1]);
        for(int w=0; w<=W; w++){
            for(int c=0; c<=C; c++){
                if(A[i-1].c == A[i].c){
                    Max(D[i&1][w][c][0], D[i-1&1][w][c][0]);
                    Max(D[i&1][w][c][1], D[i-1&1][w][c][1]);
                    if(w+A[i].w <= W && c+1 <= C) Max(D[i&1][w+A[i].w][c+1][1], D[i-1&1][w][c][0] + A[i].v);
                    if(w+A[i].w <= W) Max(D[i&1][w+A[i].w][c][1], D[i-1&1][w][c][1] + A[i].v);
                }
                else{
                    Max(D[i&1][w][c][0], D[i-1&1][w][c][0]);
                    Max(D[i&1][w][c][0], D[i-1&1][w][c][1]);
                    if(w+A[i].w <= W && c+1 <= C) Max(D[i&1][w+A[i].w][c+1][1], D[i-1&1][w][c][0] + A[i].v);
                    if(w+A[i].w <= W && c+1 <= C) Max(D[i&1][w+A[i].w][c+1][1], D[i-1&1][w][c][1] + A[i].v);
                }
            }
        }
    }

    int res = 0;
    for(int w=0; w<=W; w++) for(int c=0; c<=C; c++) for(int u=0; u<2; u++) Max(res, D[N&1][w][c][u]);
    cout << res << "\n";
}

I. イウィ (Iwi)

‘i’와 ‘w’로만 구성된 문자열 $s$가 있에서 부분 문자열 ‘iwi’ 를 제거하는 연산을 할 수 있다. 연산을 수행할 수 있는 최대 횟수를 구하는 문제
$1 \le \vert s \vert \le 300$

구간 $[i,j]$에서 수행할 수 있는 연산의 최대 횟수를 $D(i,j)$라고 정의합시다.

구간의 양 끝과 가운데에 있는 적당한 문자 $S_k$를 제거하기 위해서는, $S_i$와 $S_j$는 i, $S_k$는 w 여야 하고, 구간 $[i+1,k-1]$과 $[k+1,j-1]$을 모두 지울 수 있어야 합니다. 즉, $3\times D(i+1,k-1) = k-i-1$과 $3\times D(k+1,j-1) = j-k-1$이 성립해야 합니다. 이 경우 $D(i,j) \leftarrow D(i+1,k-1) + D(k+1,j-1) + 1$ 과 같은 상태 전이를 할 수 있습니다.

그렇지 않은 경우, 모든 연산은 적당한 $i \le k < j$에 대해 $[i,k]$에 속한 연산과 $[k+1,j]$에 속한 연산으로 나눠서 생각할 수 있습니다. 따라서 $D(i,j) \leftarrow D(i,k) + D(k+1,j)$ 와 같은 상태 전이를 할 수 있습니다.

$j-i$가 증가하는 순서대로 점화식을 계산하면 $O(N^3)$ 시간에 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Check(int a, int b, int c){
    if(S[a] != 'i' || S[b] != 'w' || S[c] != 'i') return false;
    if(D[a+1][b-1] * 3 != b-a-1 || D[b+1][c-1] * 3 != c-b-1) return false;
    return true;
}

void Solve(){
    cin >> S; N = S.size();
    for(int d=0; d<N; d++){
        for(int i=0, j=i+d; j<N; i++, j++){
            for(int k=i; k<=j; k++){
                D[i][j] = max(D[i][j], D[i][k] + D[k+1][j]);
                if(Check(i, k, j)) D[i][j] = max(D[i][j], D[i+1][k-1] + D[k+1][j-1] + 1);
            }
        }
    }
    cout << D[0][N-1] << "\n";
}

J. ボール (Ball)

수직선 위에 $N$개의 물건이 있다. $i$번째 물건의 위치는 $x_i$이다. $x$를 겨냥해 공을 던지면 $x-1,x,x+1$ 중 한 곳에 각각 1/3의 확률로 날아가서, 해당 위치에 있는 물건을 쓰러뜨린다. 모든 물건을 쓰러뜨리기 위해 공은 던져야 하는 횟수의 기댓값을 최소화하는 문제
$1 \le N \le 16$; $0 \le x_i \le 15$; $x_i$는 모두 서로 다름

현재 물건이 있는 위치를 비트로 나타낸 뒤, 물건이 $bit$에 있을 때 모든 물건을 쓰러뜨리기 위해 공을 던져야 하는 횟수의 기댓값을 $D(bit)$ 라고 정의합시다. $D(bit)$를 계산할 때 $D(bit)$이 필요한 경우가 있어서 조심해야 합니다.

위치 $p$를 겨냥해서 공을 던지는 상황을 생각해 봅시다. 공은 $p-1$, $p$, $p+1$ 중 한 곳으로 날아가게 되는데, 이중 실제로 물건이 있는 위치의 수에 따라 식이 어떻게 되는지 관찰해 봅시다.

  • 3개: $D(bit) = \lbrace D(X) + D(Y) + D(Z) \rbrace / 3 + 1$
    $D(bit) = \lbrace D(X) + D(Y) + D(Z) + 3\rbrace / 3$
  • 2개: $D(bit) = \lbrace D(X) + D(Y) + D(bit) \rbrace / 3 + 1$
    $D(bit) = \lbrace D(X) + D(Y) + 3 \rbrace / 2$
  • 1개: $D(bit) = \lbrace D(X) + 2D(bit) \rbrace / 3 + 1$
    $D(bit) = D(X) + 3$
  • 0개: 공을 안 던지는 게 이득

다행히 일차 방정식을 풀면 일반적인 점화식 꼴이 나오는 것을 확인할 수 있습니다.

위 식을 그대로 코드로 옮기면 좌표의 범위를 $X$라고 할 때 $O(X\times 2^X)$ 시간에 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
double f(int bit){
    if(bit == 0) return 0;
    double &res = D[bit];
    if(res >= 0) return res;

    res = 1e9;
    for(int p=-1; p<=16; p++){
        double sum = 0; int hit = 0;
        for(int i=p-1; i<=p+1; i++){
            if(0 <= i && i < 16 && (bit >> i & 1)) sum += f(bit ^ (1<<i)), hit++;
        }
        res = min(res, (sum + 3) / hit);
    }
    return res;
}

void Solve(){
    cin >> N;
    for(int i=0,t; i<N; i++) cin >> t, S |= 1 << t;
    fill(D, D+(1<<16), -1);
    cout << fixed << setprecision(20) << f(S) << "\n";
}

K. ターゲット (Target)

$K$개의 원 $C_1, C_2, \cdots, C_K$가 있을 때, 모든 $i$에 대해 $C_i$가 $C_{i+1}$에 strictly 포함되어 있다면 이 원들의 나열을 크기가 $K$인 과녁이라고 부른다.
$N$개의 원이 있다. $i$번째 원의 중심은 $(x_i,0)$이고 반지름은 $r_i$이다. 만들 수 있는 과녁의 최대 크기를 구하는 문제
$1 \le N \le 10^5$; $0 \le x_i \le 10^8$; $1 \le r_i \le 10^8$

중심의 $y$좌표가 모두 $0$이므로 원 대신 수직선 상의 구간 $[x_i-r_i, x_i+r_i]$ 라고 바꿔서 생각하면, 시작점이 감소하고 끝점이 증가하도록 몇 개의 구간을 선택하는 문제가 됩니다.

모든 구간을 시작점 내림차순, 시작점이 같다면 끝점 내림차순으로 정렬한 뒤, 끝점 좌표를 이용해 LIS를 구하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Solve(){
    int N; cin >> N;
    vector<pair<int,int>> A; A.reserve(N);
    for(int i=0; i<N; i++){
        int x, r; cin >> x >> r;
        A.emplace_back(x-r, x+r);
    }
    sort(A.begin(), A.end(), greater<>());

    vector<int> L;
    for(auto [_,i] : A){
        if(L.empty() || L.back() < i) L.push_back(i);
        else *lower_bound(L.begin(), L.end(), i) = i;
    }
    cout << L.size() << "\n";
}

L. 猫 (Cat)

수직선 위에 $N$마리의 고양이가 있다. 두 고양이 $i, j$의 친밀도는 $f_{i,j}$이고, 어떤 고양이의 행복도는 거리가 1 이하에 있는 고양이들과의 친밀도의 합이다.
고양이 $N$마리의 위치를 수직선 위에 오름차순으로($x_1 < x_2 < \cdots < x_N$) 배치하려고 한다. 좌표는 정수가 아니어도 된다. 모든 고양이의 행복도의 총합을 구하는 문제
$1 \le N \le 1000$; $-1000 \le f_{i,j} \le 1000$; $f_{i,i} = 0$; $f_{i,j} = f_{j,i}$

편의상 거리가 1 이하인 두 고양이 쌍의 $f_{i,j}$값의 합을 구한 뒤 마지막에 2배해서 출력할 것입니다.

$i$번째 고양이와 거리가 1 이하인 가장 왼쪽 고양이의 번호를 $L_i$라고 합시다. 고양이의 좌표는 증가해야 하므로 $L_{i-1} \le L_i$가 성립해야 하며, $L_1 \le L_2 \le \cdots \le L_N$이 되도록 고양이를 배치할 수 있습니다. 이를 이용해 점화식을 세울 수 있습니다.

$1, 2, \cdots, i$번째 고양이만 고려했을 때, $L_i = j$ 일 때 가능한 최댓값을 $D(i,j)$라고 정의합시다. $L_{i-1} \le L_i = j$가 성립해야 하므로 $D(i,j) = \min_{1\le k\le j} D(i-1,k) + \sum_{t=j}^{i-1} f_{i,t}$로 계산할 수 있습니다.

naive 하게 계산하면 시간 복잡도가 $O(N^3)$이 되지만, $D(i-1, \ast)$의 prefix min과 $f_{i,\ast}$의 prefix sum을 이용하면 $O(N^2)$에 계산할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> F[i][j];
    for(int i=1; i<=N; i++) partial_sum(F[i]+1, F[i]+N+1, F[i]+1);
    memset(D, 0xc0, sizeof D); D[1][1] = 0;
    for(int i=2; i<=N; i++){
        int mx = D[i-1][1];
        for(int j=1; j<=i; j++){
            mx = max(mx, D[i-1][j]);
            D[i][j] = mx + F[i][i] - F[i][j-1];
        }
    }
    cout << *max_element(D[N]+1, D[N]+N+1) * 2 << "\n";
}

M. 家 (House)

$H$개의 층이 있고, 모든 층의 구조가 동일한 건물이 있다. 각 층에는 $R$개의 방이 있고, 두 방을 양방향으로 연결하는 통로가 몇 개 있다. 또한, 임의의 정수 $h,r$에 대해, $h$층의 $r$번 방에서 $h-1$층의 $r$번 방으로 내려갈 수 있다. $H$층의 $1$번 방에서 출발해 같은 방을 두 번 이상 방문하지 않고 $1$층의 $1$번 방으로 이동하는 경로의 수를 세는 문제
$2 \le H \le 10^9$; $1 \le R \le 16$

우선 한 층 안에서만 이동해서 $i$번 방에서 $j$번 방으로 가는 경로의 수 $M_{i,j}$를 계산합시다. 시작점 $i$가 고정되어 있을 때 TSP와 같은 비트 DP를 이용해 $O(R^2\times 2^R)$ 시간에 계산할 수 있습니다. 이를 $R$번 수행해야 하므로 $M_{i,j}$를 모두 계산하는 데 $O(R^3\times 2^R)$ 시간이 걸립니다.

정점이 $R$개 있고, $i$에서 $j$로 가는 간선이 $M_{i,j}$개 있는 새로운 그래프를 생각해 봅시다. 간선을 타고 한 번 이동한 다음 한 층 밑으로 내려간다고 생각하면, 이 문제는 새로운 그래프의 1번 정점에서 출발해서 간선을 따라 총 $H$번 이동해서 다시 1번 정점으로 돌아오는 walk의 개수를 세는 문제가 됩니다.

간선을 $i$번 타고 이동해서 $u$번 정점에서 $v$번 정점으로 가는 경우의 수를 $D(i,u,v)$라고 정의하면, $D(1,u,v) = M_{u,v}$이고, $i > 1$ 이면 $D(i,u,v) = \sum D(i-1,u,x)\times M_{x,v}$ 입니다. $O(HR^3)$ 시간에 답을 구할 수 있지만 $H \le 10^9$라서 제한 시간 안에 문제를 해결할 수 없습니다.

하지만 점화식을 다시 잘 살펴보면, 행렬 곱셈과 똑같다는 것을 알 수 있습니다. 즉, $D(i,u,v) = (M^i)_{u,v}$입니다. 따라서 점화식을 계산하는 대신, 단순히 $M^H$를 $O(R^3 \log H)$ 시간에 구하는 것으로 문제를 해결할 수 있습니다.

행렬 $M$을 구하는 데 $O(R^32^R)$, 이후 행렬의 거듭 제곱을 구하는 데 $O(R^3 \log H)$ 만큼의 연산이 필요하므로, 전체 시간 복잡도는 $O(R^32^2 + R^3 \log H)$ 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
vector<vector<ll>> Mul(const vector<vector<ll>> &a, const vector<vector<ll>> &b){
    int n = a.size(), m = b.size(), k = b[0].size();
    vector<vector<ll>> res(n, vector<ll>(k));
    for(int i=0; i<n; i++) for(int t=0; t<m; t++) for(int j=0; j<k; j++) res[i][j] = (res[i][j] + a[i][t] * b[t][j]) % MOD;
    return res;
}

vector<vector<ll>> Pow(vector<vector<ll>> a, ll b){
    int n = a.size();
    vector<vector<ll>> res(n, vector<ll>(n));
    for(int i=0; i<n; i++) res[i][i] = 1;
    for(; b; b>>=1, a=Mul(a,a)) if(b & 1) res = Mul(res, a);
    return res;
}

ll K, N, D[1<<16][16];
vector<int> G[16];

vector<ll> Get(int st){
    memset(D, 0, sizeof D);
    D[1<<st][st] = 1;
    for(int bit=0; bit<(1<<N); bit++){
        for(int i=0; i<N; i++){
            if(D[bit][i] == 0) continue;
            for(auto j : G[i]) if(~bit >> j & 1) Add(D[bit|1<<j][j], D[bit][i]);
        }
    }
    vector<ll> res(N);
    for(int bit=0; bit<(1<<N); bit++) for(int i=0; i<N; i++) Add(res[i], D[bit][i]);
    return res;
}

void Solve(){
    cin >> K >> N;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int t; cin >> t;
            if(t) G[i].push_back(j);
        }
    }

    vector<vector<ll>> M(N);
    for(int i=0; i<N; i++) M[i] = Get(i);
    cout << Pow(M, K)[0][0] << "\n";
}

N. 木 (Tree)

$N$개의 정점이 있고, $N-1$개의 간선을 그려 트리를 만들려고 한다. 간선을 그리는 도중에, 지금까지 그린 간선들이 항상 연결되어 있도록 유지하려고 할 때, 간선을 그리는 순서로 가능한 경우의 수를 구하는 문제
$2 \le N \le 1000$; 간선은 입력으로 주어짐

모든 간선이 연결되도록 간선을 그리는 것은, 첫 번째로 그릴 간선을 고정하면 트리의 위상 정렬 개수를 구하는 것과 비슷하게 할 수 있습니다. 구체적으로, 처음에 그릴 간선을 녹여서 두 정점을 하나의 정점으로 합치고 나면, 남은 간선을 그리는 순서를 정하는 방법의 수는 rooted tree의 위상 정렬 개수와 같습니다. 따라서 rooted tree의 위상 정렬 개수를 $O(N)$에 셀 수 있다면 전체 문제를 $O(N^2)$ 시간에 해결할 수 있습니다.

$v$의 자식 정점 $c_1, c_2, \cdots, c_k$에 대해, 각 자식을 루트로 하는 서브트리의 크기를 $s_i$, 그 서브트리의 위상 정렬 개수를 $d_i$라고 합시다. $v$를 루트로 하는 서브트리의 위상 정렬의 순서를 구한다고 하면, $v$는 맨 앞에 와야 하니까 논외로 하고 남은 $\sum c_i$개의 순서를 정해야 합니다.

이는 색깔이 $i$인 공이 $c_i$개 있는 상황에서 모든 공을 순서대로 나열한 다음, 앞에 있는 공부터 차례대로 보면서 공의 색깔에 해당하는 서브트리의 정점을 하나씩 가져가는 것이라고 생각할 수 있습니다. 공을 나열하는 방법의 수는 $\frac{(\sum c_i)!}{\prod s_i!}$ 이므로, $v$를 루트로 하는 서브트리의 위상 정렬 개수는 $\prod d_i \times \frac{(\sum c_i)!}{\prod s_i!} $로 계산할 수 있습니다.

$1!, 2!, \cdots, N!$ 의 모듈러 곱셈 역원을 미리 전처리하면 트리 하나의 위상 정렬 개수를 $O(N)$ 시간에 구할 수 있으므로, 전체 문제를 $O(N^2)$ 시간에 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
pair<ll,ll> DFS(int v, int b=-1){
    ll dp = 1, sz = 1;
    for(auto i : G[v]){
        if(i == b) continue;
        auto [d,s] = DFS(i, v);
        dp = dp * d % MOD;
        dp = dp * Inv[s] % MOD;
        sz += s;
    }
    dp = dp * Fac[sz-1] % MOD;
    return {dp, sz};
}

void Solve(){
    cin >> N;
    for(int i=1,u,v; i<N; i++) cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
    Fac[0] = 1;
    for(int i=1; i<=N; i++) Fac[i] = Fac[i-1] * i % MOD;
    Inv[N] = Pow(Fac[N], MOD-2);
    for(int i=N-1; i>=0; i--) Inv[i] = Inv[i+1] * (i+1) % MOD;

    ll res = 0;
    for(int i=1; i<=N; i++){
        for(auto j : G[i]){
            if(i > j) continue;
            auto [dp1,sz1] = DFS(i, j);
            auto [dp2,sz2] = DFS(j, i);
            ll now = Fac[N-2] * Inv[sz1-1] % MOD * Inv[sz2-1] % MOD;
            now = now * dp1 % MOD * dp2 % MOD;
            res = (res + now) % MOD;
        }
    }
    cout << res << "\n";
}

O. 文字列 (String)

‘a’ 를 $freq_1$개, ‘b’를 $freq_2$개, … , ‘z’를 $freq_{26}$개 사용하면서, 인접한 문자가 서로 다른 문자열의 개수를 구하는 문제
$0 \le freq_i \le 10$

편의상 a, b, c, … , z 대신 $0, 1, 2, \cdots, 25$를 사용합니다. $freq$ 배열을 0-based로 만들면 $i$를 $freq_{i}$개 사용한다고 생각할 수 있습니다.

$0,1,\cdots,i$를 모두 사용해서 문자열을 만들 때, 인접한 두 문자가 동일한 쌍(bad pair)가 $j$인 경우의 수를 $D(i, j)$라고 정의합시다. 또한, $S_i = freq_0 + freq_1 + \cdots freq_i$라고 정의합시다. $D(i, j)$ 상황에서 $i+1$번 문자를 삽입하는 상황을 생각해 보면, 이미 길이가 $S_i$인 문자열이 있으므로 문자를 삽입할 수 있는 위치가 $S_i+1$개 있고, 이중 $j$개의 위치가 bad pair 인 상황입니다.

$freq_{i+1}$개의 문자를 $k$개의 블록으로 분할한 뒤, 그중 $x$개는 bad pair에, 나머지 $k-x$개는 good pair에 배치합시다. $k$개의 블록으로 분할하는 방법의 수는 $freq_{i+1}-1\choose k-1$, $x$개의 블록을 bad pair에 배치하는 방법의 수는 $j\choose x$, $k-x$개의 블록을 good pair에 배치하는 방법의 수는 $S_i+1-j\choose k-x$입니다. 이 경우 bad pair는 $x$개 감소한 뒤에 $freq_{i+1}-k$개 증가하므로, 상태 전이는 다음과 같이 나타낼 수 있습니다.

\[\displaystyle D(i+1,j-x+freq_{i+1}-k) \leftarrow D(i,j)\times {freq_{i+1}-1 \choose k-1} \times {j\choose x} \times {S_i+1-j\choose k-x}\]

가능한 모든 $1 \le k \le freq_{i+1}$, $0 \le x \le \min(j,k)$에 대해 위 식을 이용해 점화식을 계산하면 답을 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Solve(){
    Comb[0][0] = 1;
    for(int n=1; n<333; n++){
        Comb[n][0] = 1;
        for(int k=1; k<=n; k++) Comb[n][k] = (Comb[n-1][k-1] + Comb[n-1][k]) % MOD;
    }

    for(int i=0; i<26; i++){
        int t; cin >> t;
        if(t) C.push_back(t);
    }
    partial_sum(C.begin(), C.end(), back_inserter(S));

    D[0][C[0]-1] = 1;
    for(int i=0; i+1<C.size(); i++){
        for(int j=0; j<=S[i]; j++){
            const ll now = D[i][j];
            if(!now) continue;
            for(int k=1; k<=C[i+1]; k++){
                for(int x=0; x<=min(j,k); x++){
                    ll split = Comb[C[i+1]-1][k-1];
                    ll bad   = Comb[j][x];
                    ll good  = Comb[S[i]+1-j][k-x];
                    ll way   = split * bad % MOD * good % MOD;
                    ll j_nxt = j - x + C[i+1] - k;
                    D[i+1][j_nxt] = (D[i+1][j_nxt] + now * way) % MOD;
                }
            }
        }
    }
    cout << D[C.size()-1][0] << "\n";
}

P. うなぎ (Eel)

$N$개의 정점으로 구성된 트리가 주어지면, 길이가 0이 아닌 vertex disjoint path를 $K$개 선택하는 방법의 수를 구하는 문제
$2 \le N \le 1\,000$; $1 \le K \le 50$

트리 DP를 합시다. $v$를 루트로 하는 서브트리에서 만들어지는 경로는 세 가지로 분류할 수 있습니다.

  1. $v$를 포함하지 않는 경로
  2. $v$와 $v$의 자식 2개를 포함하는 경로
  3. $v$와 1개 이하의 $v$의 자식을 포함하는 경로

이중 (3)은 $v$의 부모 정점과 연결될 수도 있습니다. 따라서 점화식을 두 가지로 나눠서 생각하는 것이 좋아 보입니다.

  • $Close(v,k) :=$ $v$를 루트로 하는 서브트리에서 $k$개의 경로를 선택하고, $v$에서 부모로 올라가는 간선은 사용하지 않는 경우의 수
  • $Open(v,k) := $ $v$를 루트로 하는 서브트리에서 $k$개의 경로를 선택하고, 그중 한 경로가 $v$에서 부모로 올라가는 간선을 사용하는 경우의 수

$v$가 리프일 때는 close 이면서 길이가 0이 아닌 경로를 만들 수 없으므로 $Close(v,0) = 1$ 이고 나머지는 $0$이며, open 인 경로를 하나 만들 수 있으므로 $Open(v,1) = 1$입니다.

$v$가 리프가 아니면 자식 정점의 dp값을 합쳐야 합니다. 자식 정점들을 합칠 때, $v$와 자식을 연결하는 간선을 $i$ ($0\le i\le 2$)개 사용하면서 경로를 $x$개 만드는 경우의 수를 $sub(i,x)$라고 정의합시다. $v$의 자식 $c$를 추가하면 $sub$ 배열은 아래와 같이 변합니다.

  • $sub(i,x+y) \leftarrow sub(i,x) \times Close(c,y)$ ($0 \le i \le 2$)
  • $sub(i+1,x+y) \leftarrow sub(i,x) \times Open(c,y)$ ($0 \le i \le 1$)

모든 자식을 합친 후에 아래와 같이 $Close(v,\ast)$와 $Open(v,\ast)$를 계산할 수 있습니다.

  • $Close(v,k) = sub(0,k) + sub(1,k) + sub(2,k+1)$
  • $Open(v,k) = sub(0,k-1) + sub(1,k)$

$Close(v,k) \leftarrow sub(2,k+1)$은 $v$로 향하는 두 경로를 합쳐서 하나의 close 경로(2)를 만드는 것, $Open(v,k) \leftarrow sub(0,k-1)$는 $v$로 시작해 올라가는 새로운 경로(3)를 만드는 것을 나타냅니다.

두 서브트리를 합칠 때 $O(K^2)$ 만큼의 연산이 필요하므로 전체 시간 복잡도는 $O(NK^2)$입니다. 두 서브트리를 합칠 때 $\min(\vert T_1\vert, K) \times \min(\vert T_2\vert, K)$ 만큼의 연산만 하도록 구현하면 $O(NK)$가 되지만, 이 문제에서는 굳이 그렇게 구현할 필요는 없습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int N, K;
ll Close[1010][55], Open[1010][55];
ll sub[3][55], prv[3][55];
vector<int> G[1010];

void Apply(int v){
    memcpy(prv, sub, sizeof prv);
    memset(sub, 0, sizeof sub);
    for(int i=0; i<3; i++) for(int x=0; x<=K+1; x++) for(int y=0; x+y<=K+1; y++) Add(sub[i][x+y], prv[i][x] * Close[v][y] % MOD);
    for(int i=0; i<2; i++) for(int x=0; x<=K+1; x++) for(int y=0; x+y<=K+1; y++) Add(sub[i+1][x+y], prv[i][x] * Open[v][y] % MOD);
}

void DFS(int v, int b=-1){
    bool leaf = true;
    for(auto i : G[v]) if(i != b) DFS(i, v), leaf = false;
    if(leaf){ Close[v][0] = Open[v][1] = 1; return; }

    memset(sub, 0, sizeof sub); sub[0][0] = 1;
    for(auto i : G[v]) if(i != b) leaf = false, Apply(i);

    for(int i=0; i<=K; i++){
        Close[v][i] = (sub[0][i] + sub[1][i] + sub[2][i+1]) % MOD;
        Open[v][i] = ((i?sub[0][i-1]:0) + sub[1][i]) % MOD;
    }
    for(int i=0; i<=K; i++) Close[v][i] %= MOD, Open[v][i] %= MOD;
}

void Solve(){
    cin >> N >> K;
    for(int i=1; i<N; i++){
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    DFS(1);
    cout << Close[1][K] << "\n";
}

Q. 連結 (Concat)

$N$개의 이진 문자열 $w_1,w_2,\cdots,w_N$이 주어진다. 중복을 허용해서 문자열을 원하는 만큼 이어 붙여서 길이가 $L$인 문자열을 만들 때, 만들 수 있는 서로 다른 문자열의 개수를 구하는 문제
$1 \le N \le 510$; $1 \le \vert w_i \vert \le 8$; $1 \le L \le 100$

문자열을 직접 $w_i$들의 나열로 분할하거나, 문자열 뒤에 $w_i$를 붙여넣는 방식으로 세면 같은 문자열을 여러 번 세어서 올바르지 않은 답을 구하게 될 수 있습니다.

중복을 피하기 위해 $\vert w_i\vert \le 8$ 이라는 점을 이용합니다. 문자열 뒤에 비트를 하나씩 추가하면서, 이 문자열이 $w_i$들의 나열로 만들 수 있는지를 관리합니다. $\vert w_i\vert \le 8$ 이므로 최근 8개의 비트만 점화식의 상태에 넣어도 항상 올바르게 판정할 수 있습니다. 구체적으로, 점화식의 상태로 마지막 8비트의 값과 마지막 8자리에서 각각 끝나는 문자열을 $w_i$의 나열로 만들 수 있는지를 관리합니다.

$D(len, lst, end) :=$ 길이가 $len$이고, 마지막 8비트가 $lst$, 마지막 8자리에서 끝낼 수 있는지 여부가 $end$인 문자열의 개수라고 정의합시다. $end$에서 $2^i$를 나타내는 비트가 켜져 있다면 $len-i$번째 비트에서 끝나는 문자열을 만들 수 있음을 의미합니다.

길이가 0인 문자열은 항상 만들 수 있으므로 초기 상태는 $D(0,0,1) = 1$입니다. 문자열의 맨 뒤에 $d \in \lbrace0, 1\rbrace$을 추가하면 $lst \leftarrow (lst\times 2+d) \mod 256$, $end \leftarrow end\times 2 \mod 256$으로 갱신됩니다. 이후 지금까지 만든 문자열의 suffix가 $w_i$와 일치하고, 길이가 $len-\vert w_i\vert$인 문자열을 만들 수 있었다면 $end$의 최하위 비트를 켜서 상태를 갱신할 수 있습니다.

$W =- \max\vert w_i\vert$ 라고 하면 상태 공간의 크기는 $O(L\times 2^{2W})$이고 각 상태의 답을 $O(W)$ 시간에 구할 수 있으므로 전체 시간 복잡도는 $O(2^{2W}WL)$입니다. 각 상태의 답을 $O(N)$ 시간에 구하면 시간 초과를 받습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int N, L, A[9][256];
ll D[111][256][256];

void Solve(){
    cin >> N >> L;
    for(int i=1; i<=N; i++){
        string s; cin >> s;
        int now = 0;
        for(auto c : s) now = now << 1 | c-'0';
        A[s.size()][now] = 1;
    }

    D[0][0][1] = 1;
    for(int len=0; len<L; len++){
        for(int last=0; last<256; last++){
            for(int end=0; end<256; end++){
                const ll now = D[len][last][end];
                if(!now) continue;
                for(int d=0; d<2; d++){
                    int nxt_last = (last << 1 | d) & 255;
                    int nxt_end = (end << 1) & 255;
                    for(int i=1, p=2; i<=8; i++, p*=2){
                        if(A[i][nxt_last&(p-1)] && (end >> (i-1) & 1)) nxt_end |= 1;
                    }
                    Add(D[len+1][nxt_last][nxt_end], now);
                }
            }
        }
    }

    ll res = 0;
    for(int last=0; last<256; last++) for(int end=0; end<256; end++) if(end & 1) Add(res, D[L][last][end]);
    cout << res << "\n";
}

R. グラフ (Graph)

$N$개의 정점으로 구성된 유향 단순 그래프가 있다. 아래 연산을 최대 2번 할 수 있다.

  • 원하는 정점을 하나 고르고, 그 정점에서 출발해 자유롭게 움직인다.
  • 한 번 이상 방문한 정점을 모두 검은색으로 칠한다.

검은색으로 칠할 수 있는 정점 개수를 최대화하는 문제
$1 \le N \le 300$

같은 정점을 여러 번 방문할 수 있으므로 어떤 SCC 안에 들어가면 그 안의 모든 정점을 방문할 수 있습니다. 따라서 SCC를 압축해서 DAG로 만든 뒤, 각 정점의 가중치를 SCC의 크기로 두고 진행합시다.

두 사람이 원하는 지점에서 시작해서 항상 위상 정렬 순으로 정점을 방문한다고 생각합시다. 구체적으로, 두 사람이 각각 마지막으로 방문한 정점이 $x, y$ ($x \le y$) 일 때 지금까지 검은색으로 칠한 정점의 수의 최댓값을 $D(x, y)$라고 정의합시다.

$x, y$에서 갈 수 있는 정점 $z$에 대해, $D(x, y) + W_z \rightarrow D(y,z), D(x,z)$ 와 같이 갱신하면 되는데, 이때 $x = y$가 되는 경우와 점화식을 갱신하는 순서를 잘 고려해야 합니다. $\max(x,y)$가 증가하는 순서대로 계산하면 중복이나 빠뜨리는 케이스 없이 잘 계산할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int N, K, A[333][333], C[333], S[333], D[333][333];
vector<int> G[333], R[333], V;

void DFS1(int v){ C[v] = -1; for(auto i : G[v]) if(!C[i]) DFS1(i); V.push_back(v); }
void DFS2(int v, int c){ C[v] = c; S[c] += 1; for(auto i : R[v]) if(C[i] == -1) DFS2(i, c); }

void GetSCC(){
    for(int i=1; i<=N; i++) if(!C[i]) DFS1(i);
    reverse(V.begin(), V.end());
    for(auto i : V) if(C[i] == -1) DFS2(i, ++K);

    memset(A, 0, sizeof A);
    for(int i=1; i<=K; i++) A[0][i] = 1;
    for(int i=1; i<=N; i++) for(auto j : G[i]) if(C[i] != C[j]) A[C[i]][C[j]] = 1;
}

void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> A[i][j];
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(A[i][j]) G[i].push_back(j), R[j].push_back(i);
    GetSCC();

    memset(D, 0xc0, sizeof D); D[0][0] = 0;
    for(int i=1; i<=K; i++){
        for(int x=0; x<i; x++){
            for(int y=x; y<i; y++){
                if(A[x][i]) D[y][i] = max(D[y][i], D[x][y] + S[i]);
                if(A[y][i]) D[x][i] = max(D[x][i], D[x][y] + S[i]);
                if(A[x][i] && A[y][i]) D[i][i] = max(D[i][i], D[x][y] + S[i]);
            }
        }
    }

    int res = 0;
    for(int i=0; i<=K; i++) for(int j=i; j<=K; j++) res = max(res, D[i][j]);
    cout << res << "\n";
}

S. マス目 (Grid)

$H\times W$ 크기의 격자가 있다. $(1, 1)$과 $(H, W)$를 포함해 일부 칸을 검은색으로 칠해서, 칠해진 칸들만 이용해 $(1, 1)$과 $(H, W)$를 연결하려고 한다. 가능한 색칠 방법의 수를 구하는 문제
$2 \le H \le 6$; $2 \le W \le 100$

전형적인 Connection Profile DP 문제입니다. USACO Guide 의 DP on Broken Profile 문서에서 여러 튜토리얼을 확인할 수 있습니다.

간단한 아이디어만 소개하자면, 첫 번째 열부터 차례대로 보면서, 가장 최근 열의 칸들 간의 연결 상태를 표현하는 유니온 파인드 배열 자체를 DP의 상태로 넣는 방식입니다. 이때 상태의 수를 줄이기 위해 유니온 파인드 배열을 그대로 넣는 것보다는 정규화를 해서 넣는 것이 좋습니다.

$(1, 1)$과 연결된 칸을 항상 $0$번으로 고정하면 구현이 조금 편해집니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
struct union_find{
    vector<int> p;
    union_find(int n) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int v){ return v == p[v] ? v : p[v] = find(p[v]); }
    void merge(int u, int v){ p[find(u)] = find(v); }
};

union_find Build(const vector<int> &v){
    int n = v.size();
    union_find uf(n);
    for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(v[i] != -1 && v[i] == v[j]) uf.merge(i, j);
    return uf;
}

vector<int> Normalize(vector<int> v, int root_pos){
    int n = v.size(), cnt = 0;
    vector<int> conv(n, -1);
    if(root_pos != -1 && v[root_pos] != -1) conv[v[root_pos]] = 0;

    for(int i=0; i<n; i++){
        if(v[i] == -1) continue;
        if(conv[v[i]] == -1) conv[v[i]] = ++cnt;
        v[i] = conv[v[i]];
    }
    return v;
}

vector<int> Next(vector<int> v, int bit){
    int n = v.size(), cnt = max(0, *max_element(v.begin(), v.end()));
    vector<int> row(n);
    for(int i=0; i<n; i++) row[i] = bit >> i & 1;

    vector<int> res(n, -1);
    for(int i=0; i<n; i++) if(row[i]) res[i] = v[i] != -1 ? v[i] : ++cnt;

    int pos = find(res.begin(), res.end(), 0) - res.begin();
    if(pos == res.size()) pos = -1;

    auto uf = Build(res);
    for(int i=1; i<n; i++) if(res[i-1] != -1 && res[i] != -1) uf.merge(i-1, i);
    for(int i=0; i<n; i++) if(res[i] != -1) res[i] = uf.find(i);
    return Normalize(res, pos);
}

int N, M;
map<vector<int>, ll> D[111];

void Solve(){
    cin >> N >> M;

    for(int bit=0; bit<(1<<N); bit++){
        vector<int> state(N, -1);
        for(int i=0; i<N; i++) if(bit >> i & 1) state[i] = i;
        for(int i=1; i<N; i++) if(state[i-1] != -1 && state[i] != -1) state[i] = state[i-1];
        state = Normalize(state, 0);
        D[0][state] += 1;
    }

    for(int i=0; i+1<M; i++){
        for(auto [state,val] : D[i]){
            for(int bit=0; bit<(1<<N); bit++){
                auto nxt = Next(state, bit);
                D[i+1][nxt] = (D[i+1][nxt] + val) % MOD;
            }
        }
    }

    ll res = 0;
    for(auto [state,val] : D[M-1]) if(state.back() == 0) res = (res + val) % MOD;
    cout << res << "\n";
}

T. フィボナッチ (Fibonacci)

$a_1 = a_2 = \cdots = a_K = 1$ 이고 $i > K$ 이면 $a_i = a_{i-1} + \cdots + a_{i-K}$ 로 정의되는 수열 $a$의 $n$번째 항 $a_n$을 구하는 문제
$2 \le K \le 1\,000$; $1 \le N \le 10^9$

현재 값이 이전 $K$개의 항의 선형 결합으로 결정되는 선형 점화식의 $N$번째 항을 빠르게 계산하는 문제입니다. 다양한 방법이 존재하며, Problem Solving 범위에서는 $O(KN)$, $O(K^3 \log N)$, $O(K^2\log N)$, $O(K \log K \log N)$ 시간에 계산하는 방법들이 잘 알려져 있습니다.

구체적인 방법은 키타마사법 설명을 참고하세요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using poly = vector<ll>;
void Add(ll &a, ll b){ if((a += b) >= MOD) a -= MOD; }
void Sub(ll &a, ll b){ if((a -= b) < 0) a += MOD; }

poly Mul(const poly &a, const poly &b){
    poly res(a.size() + b.size() - 1);
    for(int i=0; i<a.size(); i++) for(int j=0; j<b.size(); j++) Add(res[i+j], a[i] * b[j] % MOD);
    return res;
}

poly Mod(const poly &a, const poly &b){
    poly res = a;
    for(int i=res.size()-1; i>=b.size()-1; i--) for(int j=0; j<b.size(); j++) Sub(res[i+j-b.size()+1], res[i] * b[j] % MOD);
    res.resize(b.size()-1);
    return res;
}

poly PowMod(poly a, ll b, const poly &mod){
    poly res{1};
    for(; b; b>>=1, a=Mod(Mul(a,a),mod)) if(b & 1) res = Mod(Mul(res, a), mod);
    return res;
}

// A[n] = c[1]A[n-1] + c[2]A[n-2] + ... + c[k]A[n-k]
//      = d[0]A[0] + d[1]A[1] + ... + d[k-1]A[k-1] for some d[*]
// given A[0..k-1], c[1..k], and n, return A[n] in O(k^2 log n)
ll Kitamasa(poly c, poly a, ll n){
    if(n < a.size()) return a[n];
    poly f(c.size() + 1);
    for(int i=0; i<c.size(); i++) f[i] = c[i] ? MOD - c[i] : 0;
    f.back() = 1;
    poly d = PowMod({0, 1}, n, f);

    ll res = 0;
    for(int i=0; i<c.size(); i++) Add(res, a[i] * d[i] % MOD);
    return res;
}

void Solve(){
    int k, n; cin >> k >> n;
    cout << Kitamasa(vector<ll>(k,1), vector<ll>(k,1), n-1) << "\n";
}