A - Shik and Stone

시작점 \((1, 1)\)에서 경로를 시뮬레이션하며 이동하면 된다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 15;
string grid[MAX_N];
bool visited[MAX_N][MAX_N];

int main() {
    int rows, cols;
    cin >> rows >> cols;
    
    string padding(cols + 2, '.');
    grid[0] = grid[rows + 1] = padding;
    
    for(int i = 1; i <= rows; i++) {
        cin >> grid[i];
        grid[i] = "." + grid[i] + ".";
    }
    
    int x = 1, y = 1;
    if(grid[x][y] != '#') {
        cout << "Impossible";
        return 0;
    }
    
    while(x != rows || y != cols) {
        visited[x][y] = true;
        
        bool down_valid = (grid[x + 1][y] == '#');
        bool right_valid = (grid[x][y + 1] == '#');
        
        if(down_valid ^ right_valid) {
            if(down_valid) x++;
            else y++;
        } else {
            cout << "Impossible";
            return 0;
        }
    }
    
    visited[rows][cols] = true;
    
    for(int i = 1; i <= rows; i++) {
        for(int j = 1; j <= cols; j++) {
            if(!visited[i][j] && grid[i][j] == '#') {
                cout << "Impossible";
                return 0;
            }
        }
    }
    
    cout << "Possible";
    return 0;
}

B - Construct Sequences

우선 \(a_{p_i} = i\)로 설정하여 \(a_{p_i} + b_{p_i} < a_{p_j} + b_{p_j}\) (\(i < j\)) 조건을 만족시키고, 이후 \(\{a_i\}\)는 증가, \(\{b_i\}\)는 감소하도록 조정한다. 이때 \(a_i, b_i\)에 큰 수 \(c_i, d_i\)를 더해 \(c_i + d_i = T\)가 되도록 하여 원래 값의 영향을 제거하고, \(a_i + b_i\)의 대소 관계는 유지한다. \(X\)를 \(n\) 이상인 값으로 설정하고, \(c_i = X \cdot (i - 1)\), \(d_i = X \cdot (n - i)\)로 두면 된다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20005;
const int BASE = 20000;

int main() {
    int n;
    cin >> n;
    
    vector<int> perm(n + 1);
    vector<long long> a(n + 1), b(n + 1);
    
    for(int i = 1; i <= n; i++) {
        int pos;
        cin >> pos;
        a[pos] = i;
    }
    
    for(int i = 1; i <= n; i++) {
        a[i] += (long long)(i - 1) * BASE;
        b[i] += (long long)(n - i + 1) * BASE;
    }
    
    for(int i = 1; i <= n; i++) {
        cout << a[i];
        if(i == n) cout << "\n";
        else cout << " ";
    }
    
    for(int i = 1; i <= n; i++) {
        cout << b[i];
        if(i == n) cout << "\n";
        else cout << " ";
    }
    
    return 0;
}

C - Pushing Balls

\(d_{2i - 1}\) (\(i\)는 음이 아닌 정수)를 \(a\)라고 하자:

• 처음 \(i - 1\)개 공을 움직이면 \(a \gets a + 2x\), 확률 \(\frac{i - 1}{n}\)
• \(i\)번째 공을 왼쪽으로 굴리면 \(a \gets a + 2x\), 확률 \(\frac{1}{2n}\)
• \(i\)번째 공을 오른쪽으로 굴리면 \(a \gets 3a + 3x\), 확률 \(\frac{1}{2n}\)
• 그 외에는 \(a\) 변화 없음, 확률 \(\frac{n - i}{n}\)

따라서 \(a\)의 기댓값은 \(\frac{(2i - 1)(a + 2x) + 3a + 3x + (2n - 2i)a}{2n} = a + \frac{2a + (4i + 1)x}{2n}\).

\(i = 1\)을 대입하면 \(d_1 \gets d_1 + \frac{2d_1 + 5x}{2n}\).

\(d_{2i}\) (\(i\)는 음이 아닌 정수)를 \(b = a + x\)라고 하자:

• 처음 \(i\)개 공을 움직이면 \(b \gets a + 3x\), 확률 \(\frac{i}{n}\)
• \(i + 1\)번째 공을 왼쪽으로 굴리면 \(b \gets 3a + 6x\), 확률 \(\frac{1}{n}\)
• 그 외에는 \(b\) 변화 없음, 확률 \(\frac{2n - 2i - 1}{n}\)

따라서 \(b\)의 기댓값은 \(\frac{2i(a + 3x) + 3a + 6x + (2n - 2i - 1)(a + x)}{2n} = a + x + \frac{2a + (4i + 5)x}{2n}\).

\(d_{2i - 1} = a\)일 때, \(d_{2i} - d_{2i - 1} = d_{2i + 1} - d_{2i} = x + \frac{2x}{n}\)이므로 \(\{d_i'\}\)는 여전히 등차수열이다. 또한 \(d_1' = d_1 + \frac{2d_1 + 5x}{2x}\), \(x' = x + \frac{2x}{n}\). 각 단계에서 공 이동 거리의 기댓값은 \(d_1 + x \cdot \frac{(1 + 2n - 1) \cdot (2n - 1)}{2 \cdot 2n} = d_1 + \frac{(2n - 1)x}{2}\)이므로 재귀적으로 계산하면 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    double d, x, total = 0;
    
    cin >> n >> d >> x;
    
    while(n > 0) {
        total += d + (2 * n - 1) * x / 2;
        d += (2 * d + 5 * x) / (2 * n);
        x += 2 * x / n;
        n--;
    }
    
    printf("%.10lf", total);
    return 0;
}

D - Shik and Game

직관적으로 생각하면, 항상 오른쪽으로 이동하다가 특정 지점에서 돌아서 첫 번째 미수령 곰 \(l\)까지 이동한 후 다시 복귀하는 것이 최적이다. 각 곰이 처음 통과부터 마지막 통과까지 소요 시간은 \(2(a_r - a_l)\) (\(T\)초 미만일 경우 대기 가능). \(0\)에서 \(E\)까지 필수 소요 시간 \(E\)초를 제외하고, \(f_i\)를 첫 \(1 \sim i\)번 곰의 동전 수집 최소 추가 시간이라 하면 전이식은 다음과 같다:

[f_i = \max_{j < i}{f_j + \max(2(a_i - a_{j + 1}), T)} ]

두 포인터로 구간 길이가 \(T\) 미만인 첫 왼쪽 끝점을 유지하면서 전이하면 된다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
const long long INF = 1e18;

int main() {
    int n;
    long long length, time_limit;
    vector<long long> positions(MAX_N), dp(MAX_N, INF), helper(MAX_N);
    
    cin >> n >> length >> time_limit;
    
    for(int i = 1; i <= n; i++) {
        cin >> positions[i];
    }
    
    helper[0] = -2LL * positions[1];
    int left = 1;
    
    for(int i = 1; i <= n; i++) {
        while(2 * (positions[i] - positions[left]) > time_limit) {
            left++;
        }
        
        if(left > 1) {
            dp[i] = helper[left - 2] + 2LL * positions[i];
        }
        
        dp[i] = min(dp[i], dp[left - 1] + time_limit);
        helper[i] = min(helper[i - 1], dp[i] - 2LL * positions[i + 1]);
    }
    
    cout << dp[n] + length;
    return 0;
}

E - Shik and Travel

이 문제는 이분 탐색 성질을 가지므로, 잎 노드 간 거리가 \(k\) 이하인 경로가 존재하는지 판단하면 된다. DP를 이용해 서브트리를 완전히 탐색한 후 나가는 것이 최적이므로, 각 서브트리의 첫 번째와 마지막 잎 노드에서 루트까지의 거리만 저장하면 된다. \(f_{u, a, b}\)를 루트 \(u\)의 서브트리에서 시작점에서 루트까지 거리가 \(a\), 끝점에서 루트까지 거리가 \(b\)인 경우의 유효성으로 정의한다. 왼쪽 자식 \(l\), 오른쪽 자식 \(r\)에 대해 시작점과 끝점은 서로 다른 서브트리에 위치해야 하므로 전이는 다음과 같다 (\(w(a, b)\)는 \(a, b\) 사이 간선 가중치):

[f_{u, a, b} = (\bigvee_{c + d + w(l, u) + w(r, u) \le k}{f_{r, a, c} \land f_{l, d, b}}) \lor (\bigvee_{c + d + w(l, u) + w(r, u) \le k}{f_{l, a, c} \land f_{r, d, b}}) ]

이를 최적화하기 위해 \(f_{u, a, b}\)가 \(f_{u, a', b'}\)보다 우월한 경우(\(a \le a'\), \(b \le b'\))는 고려하지 않아도 되므로, 각 \(a\)에 대해 최소 \(b\)만 유지하고, \(a' > a\)에 대해서는 \(b' < b\)가 된다. 각 노드 \(u\)에 대해 \(f_{u, a, b} = 1\)인 최적 쌍 \((a, b)\)만 유지하고, 두 포인터로 두 집합을 병합하면 된다. 시간 복잡도는 \(O(n \log n)\)이다.

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 200005;

vector<pair<long long, long long>> dp[MAX_N];
int parent[MAX_N], children[2][MAX_N];
long long weights[MAX_N];

void merge_pairs(vector<pair<long long, long long>>& result, 
                 vector<pair<long long, long long>>& left,
                 vector<pair<long long, long long>>& right,
                 long long limit, long long weight_l, long long weight_r) {
    if(left.empty() || right.empty()) return;
    
    int idx = 0, size = right.size();
    bool used = false;
    
    for(auto& p : left) {
        while(idx < size - 1 && p.second + right[idx + 1].first + weight_l + weight_r <= limit) {
            idx++;
            used = false;
        }
        if(!used && p.second + right[idx].first + weight_l + weight_r <= limit) {
            result.emplace_back(p.first + weight_l, right[idx].second + weight_r);
            used = true;
        }
    }
}

void add_optimal(vector<pair<long long, long long>>& vec, pair<long long, long long> item) {
    if(vec.empty() || vec.back().second > item.second) {
        vec.push_back(item);
    }
}

bool check_feasibility(long long limit) {
    for(int i = MAX_N - 1; i >= 1; i--) {
        dp[i].clear();
        
        if(children[0][i] == 0) {
            dp[i].emplace_back(0, 0);
        } else {
            vector<pair<long long, long long>> temp1, temp2;
            
            merge_pairs(temp1, dp[children[0][i]], dp[children[1][i]], limit, 
                       weights[children[0][i]], weights[children[1][i]]);
            merge_pairs(temp2, dp[children[1][i]], dp[children[0][i]], limit, 
                       weights[children[1][i]], weights[children[0][i]]);
            
            int j = 0, k = 0;
            int sz1 = temp1.size(), sz2 = temp2.size();
            
            while(j < sz1 && k < sz2) {
                if(temp1[j] < temp2[k]) {
                    add_optimal(dp[i], temp1[j++]);
                } else {
                    add_optimal(dp[i], temp2[k++]);
                }
            }
            
            while(j < sz1) add_optimal(dp[i], temp1[j++]);
            while(k < sz2) add_optimal(dp[i], temp2[k++]);
        }
    }
    
    return !dp[1].empty();
}

int main() {
    int n;
    cin >> n;
    
    for(int i = 2; i <= n; i++) {
        cin >> parent[i] >> weights[i];
        if(children[0][parent[i]] == 0) {
            children[0][parent[i]] = i;
        } else {
            children[1][parent[i]] = i;
        }
    }
    
    long long low = 0, high = 2e10, mid, answer = high;
    
    while(low <= high) {
        mid = (low + high) / 2;
        if(check_feasibility(mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    cout << answer;
    return 0;
}

F - Shik and Copying String

과정을 시각화하면 시간을 세로축, 위치를 가로축으로 하는 격자 그래프에서 오른쪽 또는 아래쪽으로 이동하는 꺾은 선으로 표현할 수 있다.

탐욕적으로 접근하면, 꺾은 선이 목표 위치에 도달했을 때는 아래로 직진하는 것이 최적이며, 그렇지 않은 경우 오른쪽으로 이동하는 것도 손해가 없다. 오른쪽으로 꺾이는 위치들(마지막 행 제외)을 유지한다. 예를 들어 \((2, 3)\) 위치. 각 오른쪽 꺾임 위치는 왼쪽 아래 방향으로 한 칸씩 이동하며, 큐를 사용해 위에서 아래로 세로 좌표를 관리한다. 새로운 꺾은 선이 정확히 아래로 내려오는 경우(이전 꺾임점이 없는 경우)를 제외하면 앞에 새로운 오른쪽 꺾임점이 추가된다. 오른쪽 꺾임점의 현재 위치는 원래 위치에서 해당 점 위에 있는 꺾임점 개수를 뺀 값이다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int length;
    string source, target;
    
    cin >> length >> source >> target;
    source = "#" + source;
    target = "#" + target;
    
    if(source == target) {
        cout << "0";
        return 0;
    }
    
    int src_idx = length, tgt_idx = length, max_steps = 0;
    queue<int> bend_points;
    
    while(tgt_idx > 0) {
        while(tgt_idx > 1 && target[tgt_idx - 1] == target[tgt_idx]) {
            tgt_idx--;
        }
        
        src_idx = min(src_idx, tgt_idx);
        
        while(src_idx > 0 && source[src_idx] != target[tgt_idx]) {
            src_idx--;
        }
        
        if(src_idx == 0) {
            cout << "-1";
            return 0;
        }
        
        while(!bend_points.empty() && bend_points.front() - (int)bend_points.size() >= tgt_idx) {
            bend_points.pop();
        }
        
        if(src_idx < tgt_idx) {
            bend_points.push(src_idx);
        }
        
        max_steps = max(max_steps, (int)bend_points.size() + 1);
        tgt_idx--;
    }
    
    cout << max_steps;
    return 0;
}