백준19618 벽 칠하기

작성일 | In

문제 링크

  • http://icpc.me/19618

문제 출처

  • 2020 APIO 1번

사용 알고리즘

  • DP

시간복잡도

  • $O(\sqrt{400\,000}N)$

풀이

$\sum f(k)^2 \leq 400\,000$이므로 $f(k) \leq \sqrt{400\,000}$입니다.

$i$번째 구간을 $j$번째 일꾼으로 칠할 수 있다면 $table(i, j) = 1$, 그렇지 않으면 $table(i, j) = 0$으로 정의합시다. $table$에서 1인 셀의 개수는 최대 $\sqrt{400\,000}N$입니다.
어떤 위치에 지령을 내릴 수 있다는 것은, 위에서 정의한 $table$을 원통처럼 둥글게 말았을 때 $1$로 구성된 길이가 $M$ 이상인 우하향 대각선이 있다는 것을 의미합니다.

$D(i, j)$를 $table(i, j)$로 끝나는 우햐향 대각선의 최대 길이로 정의합시다. 토글링을 이용해 시간복잡도 $O(\sqrt{400,000}N)$, 공간복잡도 $O(M)$에 DP Table을 채울 수 있습니다.

$D(i, \ast) \geq M$이라면 구간 $[i-M+1, i]$를 칠할 수 있다는 것을 의미합니다. 이렇게 칠할 수 있는 구간을 다 모은 다음에 그리디하게 색칠해주면 최소 지령 횟수를 알 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> color[101010];
int able[101010], dp[2][101010];

inline int Mod(int a, int b){ a %= b; a += b; a %= b; return a; }

int minimumInstructions(int N, int M, int K, vector<int> wall, vector<int> _, vector<vector<int>> v) {
    n = N; m = M; k = K;
    for(int i=0; i<m; i++) for(auto j : v[i]) color[j].push_back(i);
    for(int i=0; i<n; i++){
        if(i-2 >= 0) for(auto j : color[wall[i-2]]) dp[i&1][j] = 0;
        for(auto j : color[wall[i]]){
            dp[i&1][j] = dp[i-1&1][Mod(j-1, m)] + 1;
            if(dp[i&1][j] >= m) able[i] = 1;
        }
    }
    int ret = 0, pv;
    for(int i=n-1; ~i;){
        pv = i; while(pv<i+m && !able[pv]) pv++;
        if(pv >= i+m) return -1;
        i = pv-m; ret++;
    }
    return ret;
}