과거 청산 챌린지 #5

이제 55문제가 남았고, 다4/다3 문제는 9개가 남았다. 다4/다3권의 남은 문제들은 조금 짜기 귀찮거나 상수가 애매한 문제들이 많아서, 다2도 scope에 추가하기로 했다. 다4/다3/다2는 총 20문제가 남아 있는 상태다. 20문제 중에서는 그래도 쉽게 업솔빙할 수 있는 문제가 있었으면 좋겠다.

 

캡처를 할 당시 solved.ac가 먹통이라, 백준 스크린샷으로 대체한다.

 

 

다이아2 문제들은 이름이 기억나는 것들이 많다. 좋은 문제라고 기억하는 것들도 조금 있다. Star Trek 같은 문제는 좋긴 한데 ML이 256MB였던가 하는 문제로 업솔빙을 안 했던 것 같다. 구데기컵 문제도 보인다 (24906). OI 문제들이 많은 것 같은데, 대부분의 OI 문제들은 퀄리티 보장이 어느 정도 되기 때문에 다행이지만, 다4/다3권에서 만난 POI/CEOI 등의 문제들은 ML을 작게 주는 경향이 있어 메모리 억까를 피하는 것도 중요해 보인다.

 

남은 문제: 55 → 50문제

BOJ 20452. Робомарафон

문제 요약은 다음과 같다.

 

$n$개의 로봇이 수직선 위에 있고 $i$번째 로봇은 위치 $x=i$에 있다. 각 로봇 밑에는 신호기가 있으며 이 중 일부만 작동시킬 예정이다. 위치 $x$의 신호기에서 발생한 신호는 시간 $1$ 동안 양옆으로 거리 $1$만큼 전파된다. 즉, 위치 $x$의 신호기에서 시간 $t$에 신호가 발생했다면 위치 $y$의 로봇은 이를 시간 $|x-y|+t$에 받는다. 각 로봇은 신호를 처음으로 받은 뒤 $a_i$초 뒤에 결승점을 통과한다.

 

각 로봇의 등수 $k_i$는 $i$번 로봇보다 일찍 결승점을 통과한 로봇의 수 + 1로 결정된다. 각 로봇에 대해, ($p=1$인 경우) 각 로봇의 최소 등수 또는 ($p=2$인 경우) 각 로봇의 최대 등수를 구해야 한다.

Subtask 1, 2 (20점)

신호기 작동 집합을 고르는 경우가 $O(2^n)$가지 뿐이다. 전부 해 봐도 $O(2^n \cdot n)$이 되어 문제없다.

Subtask 3 (50점)

집합은 $O(2^n)$가지가 있지만, 실제로 그 중 우리가 고려해야 할 유의미한 집합은 그리 많지 않다. 이 서브태스크에서 우리의 목표는 각각의 로봇 $i$에 대해 로봇 $i$가 최소 등수 = 최고 등수 (등수는 작을수록 높으니까) 를 언제 갖는지 살펴봐야 한다. 그런데 이렇게 놓고 보면, 우리는 신호기를 하나만 작동시키는 것이 최적임을 알 수 있다. $i$번 로봇이 사용하게 될 신호기 말고 다른 신호기를 켜게 되면 그건 다른 로봇들에게만 이득이기 때문이다.

 

조금 더 생각해 보면, $i$번 로봇을 최고 등수로 만드려면 $i$번 로봇 밑의 신호기만 켜야 한다는 것을 알 수 있다. WLOG $i$번 로봇 오른쪽의 신호기를 하나 켰다고 하자. 그럼 왼쪽 로봇들 입장에서는 $i$번 로봇을 켰을 때랑 차이가 없고, 오른쪽 로봇들은 더 이득을 보게 되므로, $i$번 로봇에게 손해이다.

 

따라서 각 로봇에 대해, 자기 밑의 신호기만 켰을 때 등수를 구하면 된다. 이건 $O(n \log n)$에 어렵지 않게 구할 수 있다.

Subtask 4, $O(n^3 \log n)$ (53점)

앞과 마찬가지로 유의미한 집합이 무엇이 있는지를 생각해 보자. 로봇 $i$에 대해 어떤 $(l, r)$이 존재해 $l < i < r$이고 $l$은 $i$ 왼쪽에 켜진 가장 오른쪽 로봇, $r$은 $i$ 오른쪽에 켜진 가장 왼쪽 로봇이라고 하자. 이때 $[1, l]$과 $[r, n]$은 모두 켜는 게 최적이고, 나머지는 모두 끄는 게 최적이다. 따라서 이런 $O(n^2)$가지 형태만 봐도 충분하다. 각각에 대해 $O(n \log n)$ 시간 안에 답을 구할 수 있으므로, $O(n^3 \log n)$ 시간에 문제를 해결할 수 있다.

Subtask 4, $O(n^2 \log n)$ (60점)

로봇 $i$에 집중해서 생각해 보자. $(l, r)$에 관한 경우의 수는 아래 세 가지가 있다.

• $1 \le l < i < r \le n$
• $l = 0$ (로봇 $i$ 왼쪽에 아무 신호기도 작동하지 않음)
• $r = n+1$ (로봇 $i$ 오른쪽에 아무 신호기도 작동하지 않음)

현재는 모든 로봇마다 위 세 가지 케이스에서 생기는 $O(n^2)$가지 경우를 다 보고 있다. 여기서 보는 집합의 수를 조금 줄여 보자.

먼저 첫 번째 케이스를 보자. 각 로봇이 통과하는 시간을 $T_i$라고 하자. 로봇을 다섯 구역으로 나눌 수 있는데, 각각 통과 시간은

• $1 \le x \le l$: $A_x$
• $l < x < i$: $A_x + \min(x - l, r - x)$
• $x = i$: $A_i + \min(i-l, r-i)$
• $i < x < r$: $A_x + \min(x-l, r-x)$
• $r \le x \le n$: $A_x$

그런데 여기서 $i - l = r - i$여야 함을 알 수 있다. 또한 $l = 1$이거나 $r = n$이어야 함을 알 수 있다. 일단 이 사실을 믿으면, 봐야 하는 $(l, r)$의 개수가 $O(n)$개가 되어 $O(n^2 \log n)$에 문제를 해결할 수 있다.

 

이제 저 성질이 왜 성립하는지를 생각해 보자. $r-i \neq i-l$이라면, 양쪽 $l$이나 $r$ 중 더 가까운 쪽의 신호를 듣고 로봇 $i$가 출발한다. 그런데 그러면 먼 쪽을 가까운 쪽과 같은 거리로 옮겨 주는 게 최적이다. 로봇 $i$의 도착 시간은 여전히 같지만 다른 일부 로봇들의 도착 시간이 빨라지기 때문이다. 마찬가지로, 만약 $r-i = i-l$인데 $l \neq 1$이고 $r \neq n$이라면 $l$과 $r$을 각각 양쪽으로 한 칸씩 밀어주면 이득이다. 이 부분을 분석하기 위해서는 "시차"의 개념을 도입하면 편하다.

 

요점은 로봇 $j$ ($j \neq i$)에 대해 중요한 것은 $T_j - T_i$가 얼마냐 작냐는 것이다. 그런데 현재 상황에서

$$
T_j = \begin{cases}
A_j & (1 \le j \le l) \\
A_j + (j-l) & (l < j < i) \\
A_i + (i-l) = A_i + (r-i) & (j=i) \\
A_j + (r-j) & (i < j < r) \\
A_j & (r \le j \le n)
\end{cases}
$$

이다. 따라서 시차 $D_j := T_j - T_i$는 아래와 같이 계산된다.

$$
D_j = \begin{cases}
A_j - A_i - i + l & (1 \le j \le l) \\
A_j - A_i & (l < j < i, i < j < r) \\
A_j - A_i + j - r & (r \le j \le n)
\end{cases}
$$

이 시차가 비감소하도록 $(l, r)$을 변경 가능하다면 항상 그렇게 하는 것이 이득이다. (여기서 비감소는 증가하는 $D_j$ 가 하나도 없는 경우를 말한다.) $l$과 $r$을 양쪽으로 $1$씩 넓히면 $D_j$가 비감소하므로 이렇게 해 주는 것이 이득임을 알 수 있다.

Subtask 4, $O(n \log n)$ (100점)

위 케이스 분석을 두 번째 / 세 번째 케이스에 대해서도 해 보면, $l = 0$인 경우 $r = n$이 최적이고, $r = n+1$인 경우 $l = 1$이 최적임을 알 수 있다. 따라서 사실 각 $i$에 대해 해봐야 하는 $(l, r)$ 쌍이 단 세 개뿐임을 알 수 있다.

 

그렇다면 문제는 $(i, l, r)$ 쌍 $O(n)$개에 대해 등수를 계산하는 문제로 변한다. 이것은 $O(n \log n)$에 할 수 있고, 문제를 해결할 수 있다.

 

한 가지 팁은 Type 1만 Subtask 3처럼 따로 처리하고, Type 2 / 3는 모든 $i$에 대해 $(l, r)$이 같으므로 한번에 처리하는 것이 편하다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, p;

void input();
void naive();
void get_minimum_rank();
void get_maximum_rank();

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    input();
    if(p==1) get_minimum_rank();
    else get_maximum_rank();
}

int A[400002];

void input(){
    cin >> n >> p;
    for(int i=1; i<=n; i++) cin >> A[i];
}

void experiment(vector<int> &selection, vector<int> &max_rank, vector<int> &min_rank){
    vector<int> vec (1, -1'000'000'000), score (n);
    for(int v: selection) vec.push_back(v);
    vec.push_back(1'000'000'000);

    int pnt = 0;

    for(int i=1; i<=n; i++){
        while(vec[pnt+1] <= i) pnt++;
        score[i-1] = min(i - vec[pnt], vec[pnt+1] - i) + A[i];
    }

    vector<int> sorted = score;
    sort(sorted.begin(), sorted.end());
    for(int i=0; i<n; i++){
        int rank = lower_bound(sorted.begin(), sorted.end(), score[i]) - sorted.begin() + 1;
        max_rank[i] = max(max_rank[i], rank);
        min_rank[i] = min(min_rank[i], rank);
    }
}

void naive(){
    vector<int> max_rank (n), min_rank (n, n+1);
    for(int d=1; d<(1<<n); d++){
        vector<int> vec;
        for(int i=1; i<=n; i++) if(d&(1<<(i-1))) vec.push_back(i);
        experiment(vec, max_rank, min_rank);
    }

    for(int i=1; i<=n; i++){
        cout << (p==1 ? min_rank[i-1] : max_rank[i-1]) << '\n';
    }
}

struct Fenwick{
    int n;
    int tree[400002];

    void init(int _n){
        n = _n;
        fill(tree, tree+n+1, 0);
    }

    void add(int x, int v){
        while(x <= n){
            tree[x] += v;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        return l>r ? 0 : sum(r) - sum(l-1);
    }
} fenwick;

void get_minimum_rank(){
    vector<int> ans (n+2, 1);

    {
        vector<int> values (n);
        for(int i=1; i<=n; i++) values[i-1] = A[i] + i;

        vector<int> sorted = values;
        sort(sorted.begin(), sorted.end());
        fenwick.init(n);
        for(int i=n-1; i>=0; i--){
            int rank = lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin() + 1;
            ans[i+1] += fenwick.sum(rank-1);
            fenwick.add(rank, 1);
        }
    }

    {
        vector<int> values (n);
        for(int i=1; i<=n; i++) values[i-1] = A[i] - i;

        vector<int> sorted = values;
        sort(sorted.begin(), sorted.end());
        fenwick.init(n);

        for(int i=0; i<n; i++){
            int rank = lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin() + 1;
            ans[i+1] += fenwick.sum(rank-1);
            fenwick.add(rank, 1);
        }
    }

    for(int i=1; i<=n; i++) cout << ans[i] << '\n';
}

void get_maximum_rank(){
    vector<int> ans (n+2, 1);

    { // Type 1
        vector<vector<int> > ql (n+2), qr (n+2);
        for(int i=1; i<=n; i++){
            int D = min(i-1, n-i);
            int L = i-D, R = i+D;
            ql[L].push_back(i);
            qr[R].push_back(i);
        }

        { // A[l]
            vector<int> values (A+1, A+n+1);
            sort(values.begin(), values.end());

            fenwick.init(n);
            for(int l=1; l<=n; l++){
                int idx = lower_bound(values.begin(), values.end(), A[l]) - values.begin() + 1;
                fenwick.add(idx, 1);

                for(int i: ql[l]){
                    int idx = lower_bound(values.begin(), values.end(), A[i] + (i-l)) - values.begin() + 1;
                    ans[i] += fenwick.sum(idx-1);
                }
            }

            fenwick.init(n);
            for(int r=n; r>=1; r--){
                int idx = lower_bound(values.begin(), values.end(), A[r]) - values.begin() + 1;
                fenwick.add(idx, 1);

                for(int i: qr[r]){
                    int idx = lower_bound(values.begin(), values.end(), A[i] + (r-i)) - values.begin() + 1;
                    ans[i] += fenwick.sum(idx-1);
                }
            }
        }

        { // A[i] + i
            vector<int> values (n);
            for(int i=1; i<=n; i++) values[i-1] = A[i] + i;
            sort(values.begin(), values.end());

            fenwick.init(n);
            for(int l=1; l<=n; l++){
                int idx = lower_bound(values.begin(), values.end(), A[l] + l) - values.begin() + 1;
                fenwick.add(idx, 1);

                for(int i: ql[l]){
                    int idx = lower_bound(values.begin(), values.end(), A[i] + i) - values.begin() + 1;
                    ans[i] -= fenwick.sum(idx-1);
                }
                ans[l] += fenwick.sum(idx-1);
            }
        }

        { // A[i] - i
            vector<int> values (n);
            for(int i=1; i<=n; i++) values[i-1] = A[i] - i;
            sort(values.begin(), values.end());

            fenwick.init(n);
            for(int r=n; r>=1; r--){
                int idx = lower_bound(values.begin(), values.end(), A[r] - r) - values.begin() + 1;
                fenwick.add(idx, 1);

                for(int i: qr[r]){
                    int idx = lower_bound(values.begin(), values.end(), A[i] - i) - values.begin() + 1;
                    ans[i] -= fenwick.sum(idx-1);
                }
                ans[r] += fenwick.sum(idx-1);
            }
        }
    }
    ans[1] = ans[n] = 0; // 끝은 예외

    { // Type 2
        vector<int> values (n+2);
        for(int i=1; i<=n; i++) values[i] = A[i] + i;

        vector<int> sorted (values.begin() + 1, values.begin() + n + 1);
        sort(sorted.begin(), sorted.end());

        for(int i=1; i<=n; i++){
            int rank = lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin() + 1;
            ans[i] = max(ans[i], rank);
        }
    }

    { // Type 3
        vector<int> values (n+2);
        for(int i=1; i<=n; i++) values[i] = A[i] - i;

        vector<int> sorted (values.begin() + 1, values.begin() + n + 1);
        sort(sorted.begin(), sorted.end());

        for(int i=1; i<=n; i++){
            int rank = lower_bound(sorted.begin(), sorted.end(), values[i]) - sorted.begin() + 1;
            ans[i] = max(ans[i], rank);
        }
    }

    for(int i=1; i<=n; i++) cout << ans[i] << '\n';
}

BOJ 11474. Insider's Information

룸메이트와 10분 정도 토론하고 풀이를 찾았다. 매우 좋은 문제 같다.

 

핵심 아이디어는 해가 항상 존재하므로, 규칙에 등장하는 수 중 적어도 하나는 가운데에 등장할 수 없다는 것이다. 이런 수들은 가장 나중에 고려해도 된다. 이런 수 아무거나 하나를 골라 $x$라 하자. $x$가 들어가는 규칙을 전부 지우고 부분문제를 재귀적으로 해결한 뒤, $x$를 왼쪽 또는 오른쪽 중 더 많은 조건을 만족하는 쪽에 붙이면 된다. 각 step에서 다루는 조건들 중 반 이상이 항상 충족되므로 문제가 풀린다.

 

$x$가 들어가는 규칙을 전부 지웠을 때, 해당 시점에서 $x$가 있는 규칙에만 존재하는 다른 수 $y$가 존재할 수 있다. 구현 시 이 부분을 조심해야 한다.

 

다2는 조금 높은 것 같아서 다4를 줬더니 다3으로 내려갔다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int A[100002], B[100002], C[100002], middle[100002];
int ans[200002];
int L = 100001, R = 100000;
int idx[100002], occ[100002];
vector<int> where[100002];
bool alive[100002];

queue<int> zeroMiddle;

void solve(){
    int x = -1;
    while(!zeroMiddle.empty()){
        int tmp = zeroMiddle.front(); zeroMiddle.pop();
        if(!occ[tmp]) continue;
        x = tmp;
        break;
    }

    if(x == -1) return; // 한계에 도달

    vector<int> triples, adjacent;
    for(int i: where[x]){
        if(!alive[i]) continue;
        triples.push_back(i);
        alive[i] = 0;
        occ[A[i]]--, occ[B[i]]--, occ[C[i]]--;

        middle[B[i]]--;
        if(!middle[B[i]]) zeroMiddle.push(B[i]);
        adjacent.push_back(A[i]);
        adjacent.push_back(B[i]);
        adjacent.push_back(C[i]);
    }

    solve();

    for(int v: adjacent){
        if(v==x) continue;
        if(!idx[v]){
            idx[v] = --L;
            ans[L] = v;
        }
    }

    int ABC = 0, CBA = 0;
    for(int i: triples){
        int a = A[i], b = B[i], c = C[i];
        assert(b != x);
        if(c == x) swap(a, c);

        if(idx[b] < idx[c]) ABC++;
        else CBA++;
    }
    if(ABC >= CBA){
        idx[x] = --L;
        ans[L] = x;
    }
    else{
        idx[x] = ++R;
        ans[R] = x;
    }
}

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> A[i] >> B[i] >> C[i];
        where[A[i]].push_back(i);
        where[B[i]].push_back(i);
        where[C[i]].push_back(i);
        middle[B[i]]++;
        occ[A[i]]++, occ[B[i]]++, occ[C[i]]++;
        alive[i] = 1;
    }

    for(int i=1; i<=n; i++) if(!middle[i]) zeroMiddle.push(i);
    solve();

    for(int i=1; i<=n; i++){
        if(!idx[i]){
            idx[i] = --L;
            ans[L] = i;
        }
    }

    for(int i=L; i<=R; i++) cout << ans[i] << ' ';
}

BOJ 15268. Kitchen Knobs

$7$이 소수이기 때문에, 각 knob은 최대 위치가 유일하게 있거나, 모든 위치가 최대이다. 모든 위치가 최대인 것은 제외하고 생각하고, $A_i$를 $i$번째 knob이 최대가 되는 위치라고 하자.

 

이 문제를 다음과 같이 생각할 수 있다: 처음에 $0$인 배열 $B$가 있는데, 구간에 특정 수를 더하는 연산을 반복할 수 있다. 이 연산을 최소로 해 $A$와 $\bmod 7$로 같게 만들어야 한다.

 

구간 덧셈은 항상 차이값 배열을 생각하면 한쪽에 $+x$, 다른 한쪽에 $-x$처럼 생각할 수 있다. 여기서는 mod 7로 생각하는 것이 좋다. 따라서 차이값 배열에 $0$이 아닌 수들, 즉 $1$부터 $6$까지의 수들을 세고 그들의 개수만으로 문제를 풀어도 된다. 문제를 풀기 위해서는 결국 이 수들을 합이 $7$의 배수가 되는 최대 개수의 그룹들로 나누는 게 된다.

 

$1$이나 $6$의 경우 둘씩 묶는 것이 항상 이득이다. 그 이유는, 만약 최적해에서 이 둘이 같은 그룹에 있었다면 이 둘을 떼어내는 것이 이득이고, 다른 그룹에 있었다고 해도 이 둘을 떼어내고 각 그룹의 나머지를 묶으면 손해가 아니기 때문이다. 마찬가지로 $2$와 $5$, $3$과 $4$에 대해서도 같은 방식으로 할 수 있다.

 

이러면 남는 수의 종류는 최대 세 가지이고 그 총 개수가 최대 $n$개이다. 여기서부터는 세제곱 DP를 통해 답을 구할 수 있다. 시간 복잡도는 $O(n^3)$이다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void init();
void solve();

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    input();
    init();
    solve();
}

int n;
int A[505];

void input(){
    cin >> n;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;

        vector<string> vs;
        for(int j=0; j<7; j++){
            vs.push_back(s);
            rotate(s.begin(), s.begin()+1, s.end());
        }

        if(vs[0] == vs[1]){
            n--, i--;
            continue;
        }
        A[i] = max_element(vs.begin(), vs.end()) - vs.begin();
    }

    if(!n){
        cout << 0;
        exit(0);
    }
}

int cnt[7];
int base;

void init(){
    for(int i=0; i<=n; i++){
        int v = (A[i+1] - A[i] + 7) % 7;
        cnt[v]++;
    }
    for(int i=1; i<=3; i++){
        int v = min(cnt[i], cnt[7-i]);
        base += v;
        cnt[i] -= v, cnt[7-i] -= v;
    }
}

int Ac, Av, Bc, Bv, Cc, Cv;
int DP[170][255][505];
vector<tuple<int, int, int> > units;

void solve(){
    for(int i=1; i<=6; i++){
        if(!cnt[i]) continue;
        if(!Av) Av = i, Ac = cnt[i];
        else if(!Bv) Bv = i, Bc = cnt[i];
        else if(!Cv) Cv = i, Cc = cnt[i];
        else exit(1);
    }
    if(Ac > Bc) swap(Ac, Bc), swap(Av, Bv);
    if(Bc > Cc) swap(Bc, Cc), swap(Bv, Cv);
    if(Ac > Bc) swap(Ac, Bc), swap(Av, Bv);

    assert(Ac <= 170 && Bc <= 250 && Cc <= 501);

    for(int i=0; i<=7 && i<=Ac; i++) for(int j=0; j<=7 && j<=Bc; j++) for(int k=0; k<=7 && k<=Cc; k++){
        if((i+j+k) == 0 || (i*Av+j*Bv+k*Cv)%7) continue;
        bool out = true;
        for(auto [a, b, c]: units) if(a<=i && b<=j && c<=k){
            out = false;
            break;
        }
        if(out) units.push_back({i, j, k});
    }

    for(int i=0; i<=Ac; i++) for(int j=0; j<=Bc; j++) for(int k=0; k<=Cc; k++) DP[i][j][k] = -1e9;
    DP[0][0][0] = 0;
    for(int i=0; i<=Ac; i++) for(int j=0; j<=Bc; j++) for(int k=0; k<=Cc; k++){
        if(DP[i][j][k] < 0) continue;
        for(auto [a, b, c]: units){
            if(i+a > Ac || j+b > Bc || k+c > Cc) continue;
            DP[i+a][j+b][k+c] = max(DP[i+a][j+b][k+c], DP[i][j][k]+1);
        }
    }

    int add = Ac + Bc + Cc - DP[Ac][Bc][Cc];
    cout << base + add;
}

BOJ 33054. It's Mooin' Time

이 문제는 옛날에 틀렸다기보다는 다른 문제에 제출해야 하는데 잘못 제출해서 여기 있게 되었다.

$L = 1$

각 지점을 $M$으로 만드는 비용을 모두 구한 뒤 정렬해 앞부터 누적합을 구하면 된다.

$L = 2$

일단 보자마자 백업처럼 풀릴 것 같다는 생각은 들었다. 하지만 이런 방향으로 풀면 전체 문제와 거리가 조금 멀어질 것 같다고 느꼈다.

 

다른 방식으로 분할 정복을 이용한 방식을 생각해 보자. 왼쪽 반절 / 오른쪽 반절로 나누고, 비용 함수를 합치는 것이다. 이때 비용 함수가 볼록이어야 하므로 minimum 등을 구할 수 있다. 이때 가운데에서 넣는 경우까지 세어야 하기 때문에 구간별로 왼쪽 끝 / 오른쪽 끝을 포함하냐 마냐로 나눠 비용 함수 네 개를 구해야 한다. 이런 식으로 하면 $O(n \log n)$에 푸는 것이 가능하다. 상수가 다소 크다. 나는 세그먼트 트리 형태로 구현했다.

$L = 3$

여기까지 왔다면 사실 $L = 2$ 형태에서 케이스만 $9$개로 늘어난 똑같은 형태의 문제가 된다. 그대로 짜면 맞는다.

 

참고로 내 코드는 353MB 정도가 나왔다. 백준은 ML을 2048MB를 주어서 가능하지만 USACO는 ML이 256MB라서 MLE가 났을 것이다. 메모리를 더 줄이는 방법이 궁금하다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void input();
void solve();

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    input();
    solve();
}

int n, L;
int A[300005];
ll C[300005];

void input(){
    cin >> L >> n;
    string s;
    cin >> s;
    for(int i=1; i<=n; i++) A[i] = (s[i-1] == 'M' ? 1 : 0);
    for(int i=1; i<=n; i++) cin >> C[i];
}

void solve1(){
    vector<ll> costs;
    for(int i=1; i<=n; i++){
        if(A[i] == 1) costs.push_back(0);
        else costs.push_back(C[i]);
    }

    sort(costs.begin(), costs.end());

    ll sum = 0;
    for(int i=1; i<=n; i++){
        sum += costs[i-1];
        cout << sum << '\n';
    }
}

void update(vector<ll> &res, vector<ll> v1, vector<ll> v2, ll add = -1){
    if(v1.empty() || v2.empty()){
        return;
    }

    int n = v1.size(), m = v2.size();
    for(int i=n-1; i>=1; i--) v1[i] -= v1[i-1];
    for(int i=m-1; i>=1; i--) v2[i] -= v2[i-1];

    int k = (add == -1 ? 0 : 1);
    int a=1, b=1, c=0;
    res.push_back(0);

    ll d1 = (a<n ? v1[a] : LLONG_MAX);
    ll d2 = (b<m ? v2[b] : LLONG_MAX);
    ll d3 = (c<k ? add : LLONG_MAX);
    while(a<n || b<m || c<k){
        if(d1 < d2 && d1 < d3){
            res.push_back(d1), a++;
            d1 = (a<n ? v1[a] : LLONG_MAX);
        }
        else if(d2 < d3){
            res.push_back(d2), b++;
            d2 = (b<m ? v2[b] : LLONG_MAX);
        }
        else{
            res.push_back(d3), c++;
            d3 = LLONG_MAX;
        }
    }

    for(int i=1; i<(int)res.size(); i++) res[i] += res[i-1];
}

void choose_better(vector<ll> &res, vector<ll> cand){
    if(res.size() < cand.size()) res.swap(cand);
    for(int i=1; i<(int)cand.size(); i++) res[i] = min(res[i], cand[i]);
}

namespace L2{
    const ll INF = 1e18;
    ll S[300005];

    struct segTree{
        vector<ll> res[1<<20][2][2];

        void solve(int i, int l, int r){
            if(l==r){
                res[i][0][0] = {0};
                res[i][0][1] = {0};
                res[i][1][0] = {0};
                res[i][1][1] = {};
                return;
            }
            int m = (l+r)>>1;
            solve(i*2, l, m);
            solve(i*2+1, m+1, r);

            for(int l=0; l<2; l++) for(int r=0; r<2; r++){
                vector<ll> cv;
                update(res[i][l][r], res[i*2][l][0], res[i*2+1][0][r]);
                update(cv, res[i*2][l][1], res[i*2+1][1][r], S[m]);
                choose_better(res[i][l][r], cv);
            }

            for(int j=i*2; j<=i*2+1; j++) for(int l=0; l<2; l++) for(int r=0; r<2; r++){
                res[j][l][r].clear();
                res[j][l][r].shrink_to_fit();
            }
        }
    } tree;

    void solve2(){
        for(int i=1; i<n; i++) S[i] = (!A[i] ? C[i] : 0) + (A[i+1] ? C[i+1] : 0);
        S[n] = INF;

        tree.solve(1, 1, n);

        vector<ll> ans = tree.res[1][0][0];
        assert((int)ans.size() >= n/2+1);

        for(int i=1; i<=n/2; i++){
            ll val = ans[i];
            cout << val << '\n';
        }
    }
}

void solve2(){
    L2::solve2();
}

namespace L3{
    const ll INF = 1e18;
    ll S[300005];

    struct segTree{
        vector<ll> res[1<<20][3][3];

        void solve(int i, int l, int r){
            if(l==r){
                res[i][0][0] = {0};
                res[i][0][1] = {0};
                res[i][1][0] = {0};
                return;
            }
            if(l+1==r){
                res[i][0][0] = {0};
                res[i][0][1] = {0};
                res[i][0][2] = {0};
                res[i][1][0] = {0};
                res[i][1][1] = {0};
                res[i][2][0] = {0};
                return;
            }
            if(l+2==r){
                res[i][0][0] = {0, S[l]};
                res[i][0][1] = {0};
                res[i][0][2] = {0};
                res[i][1][0] = {0};
                res[i][1][1] = {0};
                res[i][1][2] = {0};
                res[i][2][0] = {0};
                res[i][2][1] = {0};
                return;
            }
            int m = (l+r)>>1;
            bool lm = l<m, mr = m+1<r;
            solve(i*2, l, m);
            solve(i*2+1, m+1, r);

            for(int l=0; l<3; l++) for(int r=0; r<3; r++){
                update(res[i][l][r], res[i*2][l][0], res[i*2+1][0][r]);
                if(lm){
                    vector<ll> cv;
                    update(cv, res[i*2][l][2], res[i*2+1][1][r], S[m-1]);
                    choose_better(res[i][l][r], cv);
                }
                if(mr){
                    vector<ll> cv;
                    update(cv, res[i*2][l][1], res[i*2+1][2][r], S[m]);
                    choose_better(res[i][l][r], cv);
                }
            }

            for(int j=i*2; j<=i*2+1; j++) for(int l=0; l<3; l++) for(int r=0; r<3; r++){
                res[j][l][r].clear();
                res[j][l][r].shrink_to_fit();
            }
        }
    } tree;

    void solve3(){
        for(int i=1; i<=n-2; i++) S[i] = (!A[i] ? C[i] : 0) + (A[i+1] ? C[i+1] : 0) + (A[i+2] ? C[i+2] : 0);
        S[n-1] = S[n] = INF;

        tree.solve(1, 1, n);

        vector<ll> ans = tree.res[1][0][0];
        assert((int)ans.size() >= n/3+1);

        for(int i=1; i<=n/3; i++){
            ll val = ans[i];
            cout << val << '\n';
        }
    }
}

void solve3(){
    L3::solve3();
}

void solve(){
    if(L==1) solve1();
    if(L==2) solve2();
    if(L==3) solve3();
}

BOJ 19681. Star Trek

문제 풀이 자체는 어렵지 않으나 ML이 32MB라 조심해야 하는 문제이다.

 

핵심 아이디어는 맨 오른쪽 트리부터 생각하며, 선승이 이기는 루트의 개수를 구하는 것이다. $i$번 트리에서 선승이 이기는 configuration (여기서 configuration은 $i$번 트리에서 시작하는 루트와, 그 오른쪽 edge의 정보로, 총 $n^{2(D-i)+1}$가지가 있다) 개수를 알고 있다면, $i-1$번 트리에서 선승이 이기는 configuration이 몇 개 있는지 세는 것이다. 상황을 정리해 보면 결국 간선이 $i$번 트리에서 선승이 승리하는 (또는 패배하는) 상황으로 이어질 때 $i$번 트리에서 승리할 수 있는 시작 정점과 간선에 이어진 정점의 쌍을 세는 문제가 되고, 이 결과는 $i$에 상관없이 일정하다. 결국 문제 상황을 행렬 거듭제곱으로 바꿀 수 있고, 행렬에 들어가는 각 원소는 rerooting DP를 통해 알아낼 수 있다.

 

결과적으로 $O(n + \log D)$에 문제를 해결할 수 있다. 문제 자체가 어렵지는 않은데 ML이 작고 행렬 값을 알아내기 위핸 tree DP를 정확하게 가져가는 것이 중요하다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1'000'000'007;

ll n; ll D;
vector<int> edge[100002];

int win[100002], winRoot[100002], sz[100002];
int winWin[100002], winWinRoot[100002], winLose[100002], winLoseRoot[100002];

void dfs1(int x, int p=-1){
    if(p!=-1) edge[x].erase(find(edge[x].begin(), edge[x].end(), p));
    sz[x] = 1;

    int loseCnt = 0;
    for(int y: edge[x]){
        dfs1(y, x);
        if(!win[y]) loseCnt++;
        sz[x] += sz[y];
    }
    win[x] = !!loseCnt;

    if(loseCnt == 0){
        winWin[x] = 0;
        winLose[x] = 1;
        for(int y: edge[x]) winLose[x] += (sz[y] - winLose[y]);
    }
    else if(loseCnt == 1){
        winWin[x] = sz[x];
        for(int y: edge[x]) if(!win[y]){
            winLose[x] = sz[x] - winLose[y];
            break;
        }
    }
    else winWin[x] = winLose[x] = sz[x];
}

void dfs2(int x, int p, int psz, int pwin, int pwinwin, int pwinlose){
    int loseCnt = 0;
    vector<int> loseY;
    if(!pwin) loseCnt++, loseY.push_back(p);
    {
        for(int y: edge[x]) if(!win[y]){
            loseCnt++;
            if((int)loseY.size() < 2) loseY.push_back(y);
        }
        winRoot[x] = !!loseCnt;
        if(loseCnt >= 2) winWinRoot[x] = winLoseRoot[x] = n;
        else if(loseCnt == 1){
            winWinRoot[x] = n;
            winLoseRoot[x] = n - (loseY[0] == p ? pwinlose : winLose[loseY[0]]);
        }
        else{
            winWinRoot[x] = 0;
            winLoseRoot[x] = winLose[x] + (psz - pwinlose);
        }
    }

    int overall_sum = 1 + psz - pwinlose;
    for(int y: edge[x]) overall_sum += (sz[y] - winLose[y]);

    for(int y: edge[x]){
        int newLoseCnt = loseCnt - !win[y], newWinWin, newWinLose;
        if(newLoseCnt >= 2){
            newWinWin = n;
            newWinLose = n - sz[y];
        }
        else if(newLoseCnt == 1){
            newWinWin = n;
            int other = (loseY[0] == y ? loseY[1] : loseY[0]);
            newWinLose = n - sz[y] - (other == p ? pwinlose : winLose[other]);
        }
        else{
            newWinWin = 0;
            newWinLose = overall_sum - (sz[y] - winLose[y]);
        }

        dfs2(y, x, n - sz[y],
             !!(loseCnt - !win[y]),
             newWinWin,
             newWinLose);
    }
}

struct Matrix{
    ll m[2][2];

    Matrix(){
        memset(m, 0, sizeof(m));
    }
    Matrix(ll a, ll b, ll c, ll d){
        m[0][0] = a % MOD, m[0][1] = b % MOD, m[1][0] = c % MOD, m[1][1] = d % MOD;
    }

    friend Matrix operator*(const Matrix A, const Matrix B){
        Matrix ret;
        for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++){
            ret.m[i][k] = (ret.m[i][k] + A.m[i][j] * B.m[j][k]) % MOD;
        }
        return ret;
    }
};

Matrix mpow(Matrix x, ll y){
    if(!y) return Matrix(1, 0, 0, 1);
    if(y&1) return mpow(x, y-1) * x;
    Matrix tmp = mpow(x, y/2);
    return tmp * tmp;
}

int main(){
    #ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    #endif

    cin >> n >> D;
    for(int i=1; i<n; i++){
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    dfs1(1);
    dfs2(1, -1, 0, 1, 0, 0);

    ll wws = accumulate(winWinRoot+1, winWinRoot+n+1, 0LL);
    ll wls = accumulate(winLoseRoot+1, winLoseRoot+n+1, 0LL);
    ll wc = count(winRoot+1, winRoot+n+1, 1), lc = n - wc;

    Matrix P (winWinRoot[1], winLoseRoot[1], n-winWinRoot[1], n-winLoseRoot[1]);
    Matrix M (wws, wls, n*n-wws, n*n-wls);
    Matrix ans = P * mpow(M, D-1);
    ll realAns = (ans.m[0][0] * wc + ans.m[0][1] * lc) % MOD;
    cout << realAns;
}