Codeforces 1093F. Vasya and Array (DP)

日付: 12月 19, 2018

[Problem - 1093F - Codeforces](https://codeforces.com/contest/1093/problem/F)
## Problem
Given an array $A$ of $n$ integers, each element is each -1 or between 1 and $k$. You change each -1 into a number between 1 and $k$, and the result array does not contain a range of length $len$ of the same number. Calculate how many ways to do this.

**Constraints:** $1\le n \le 10^5,\ 1 \le k \le 100,\ 1 \le len \le n$

## Solution
If we define $f_{i,j,k}$ as the number of ways to fill $A[1,i]$ with the last element is $j$ and the length the suffix of the same number is $k$, it seems easy to solve. However, $len$ is too large and we cannot include it in dp state.

Let's define:
* $f_{i,j}$ - The number of valid ways to fill $A[1\cdots i]$ with the last element is $j$
* $s_i$ - The number of valid ways to fill $A[1\cdots i]$. $s_i = \sum_{j=1}^k f_{i,j}$
* $p_{i,j}$ - The rightmost position of a number $j$ in $A[1\cdots i]$.

Initially, if $A_i=j$ or $A_i=-1$, $f_{i,j} = s_{i-1}$. But when these conditions are met:
* $i >= len$.
* All elements in $A[i-len+1 \cdots i]$ are either -1 or $j$ (this can be checked by $p$)

There exist cases when $A[i-len+1 \cdots i]$ are all filled to $j$ (notice that $A[i-len]$ couldn't be $j$ because these cases are already substracted at position $i-1$). The number of such bad cases are $s_{i-len}-f_{i-len,j}$

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)
constexpr int madd(int x, int y, int m) { return (0LL + x + y + m + m) % m; }

const int N = 1e5 + 5, M = 998244353;
int n, k, len, C[N], F[N][105], P[N][105], S[N];

int main() {
    scanf("%d%d%d", &n, &k, &len);
    FI(i, 1, n) scanf("%d", C + i);
    FI(i, 1, n) FI(j, 1, k) { P[i][j] = P[i - 1][j]; if (C[i] == j) P[i][j] = i; }
    S[0] = 1;
    FI(i, 1, n) FI(j, 1, k) {
        if (C[i] != -1 && C[i] != j) F[i][j] = 0;
        else {
            F[i][j] = S[i - 1];
            bool ok = true;
            if (i < len) ok = false;
            FI(jj, 1, k) if (jj != j && P[i][jj] > i - len) ok = false;
            if (ok) F[i][j] = madd(F[i][j], madd(-S[i - len], F[i - len][j], M), M);
        }
        S[i] = madd(S[i], F[i][j], M);
    }
    printf("%d\n", S[n]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1093F. Vasya and Array (DP)

コメント

コメントを投稿