A - Yet Another Tetris Problem

n個の整数a_iが与えられます。各操作では、任意のiについてa_iを2増やすか、すべてのa_iを1減らすことができます。すべての値を0にできるか判定してください。

解法：すべての値の偶奇が一致する場合のみ可能です。

#include <iostream>
using namespace std;

void solve() {
    int n, first, val;
    cin >> n >> first;
    first %= 2;
    bool valid = true;
    for (int i = 1; i < n; i++) {
        cin >> val;
        valid &= (val % 2 == first);
    }
    cout << (valid ? "YES" : "NO") << endl;
}

int main() {
    int tests;
    cin >> tests;
    while (tests--) solve();
    return 0;
}

B - Yet Another Palindrome Problem

n個の整数からなる配列が与えられます。長さ3以上の回文部分列が存在するか判定してください。

解法：距離が2以上離れた等しい値の組が存在すれば可能です。

#include <iostream>
#include <vector>
using namespace std;

void check() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j < n; j++) {
            if (arr[i] == arr[j]) {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

int main() {
    int cases;
    cin >> cases;
    while (cases--) check();
    return 0;
}

C - Frog Jumps

n+2個のマスがあり、各マスにはLまたはRの方向指示があります。カエルが0番目のマスからn+1番目のマスに到達するための最小ジャンプ距離dを求めてください。

解法：連続するRマスの間の最大距離が答えです。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void calculate() {
    string directions;
    cin >> directions;
    vector<int> positions;
    positions.push_back(0);
    
    for (int i = 0; i < directions.length(); i++) {
        if (directions[i] == 'R') {
            positions.push_back(i + 1);
        }
    }
    positions.push_back(directions.length() + 1);
    
    int max_gap = 0;
    for (int i = 1; i < positions.size(); i++) {
        max_gap = max(max_gap, positions[i] - positions[i - 1]);
    }
    cout << max_gap << endl;
}

int main() {
    int test_count;
    cin >> test_count;
    while (test_count--) calculate();
    return 0;
}

D - Pair of Topics

2つの配列a,bが与えられます。a_i + a_j > b_i + b_j を満たす順序対(i,j) (i < j)の個数を求めてください。

解法：a_i - b_i > b_j - a_j と変形し、BITを使用して数えます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class FenwickTree {
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 1) {}
    
    void update(int index) {
        while (index < tree.size()) {
            tree[index]++;
            index += index & -index;
        }
    }
    
    int query(int index) {
        int total = 0;
        while (index > 0) {
            total += tree[index];
            index -= index & -index;
        }
        return total;
    }
};

int main() {
    int n;
    cin >> n;
    vector<long long> diff(n);
    vector<long long> values;
    
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        diff[i] = x;
    }
    
    for (int i = 0; i < n; i++) {
        long long y;
        cin >> y;
        diff[i] -= y;
        values.push_back(diff[i]);
        values.push_back(-diff[i]);
    }
    
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    
    vector<int> compressed_a(n), compressed_b(n);
    for (int i = 0; i < n; i++) {
        compressed_a[i] = lower_bound(values.begin(), values.end(), diff[i]) - values.begin() + 1;
        compressed_b[i] = lower_bound(values.begin(), values.end(), -diff[i]) - values.begin() + 1;
    }
    
    FenwickTree bit(values.size());
    long long result = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        result += bit.query(compressed_a[i] - 1);
        bit.update(compressed_b[i]);
    }
    
    cout << result << endl;
    return 0;
}

E - Sleeping Schedule

1日h時間の世界で、n回の睡眠をとります。各睡眠時刻が[l,r]の範囲内にある場合を"良い睡眠"とします。最大の良い睡眠回数を求めてください。

解法：動的計画法を使用します。

#include <iostream>
#include <algorithm>
using namespace std;

const int INF = -1e9;
int dp[2001][2000];

int main() {
    int n, h, l, r;
    cin >> n >> h >> l >> r;
    
    vector<int> sleep_times(n + 1);
    for (int i = 1; i <= n; i++) cin >> sleep_times[i];
    
    for (int j = 1; j < h; j++) dp[0][j] = INF;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < h; j++) {
            int option1 = dp[i - 1][(j - sleep_times[i] + 1 + h) % h];
            int option2 = dp[i - 1][(j - sleep_times[i] + h) % h];
            dp[i][j] = max(option1, option2) + (j >= l && j <= r);
        }
    }
    
    int answer = *max_element(dp[n], dp[n] + h);
    cout << answer << endl;
    return 0;
}

F - Maximum White Subtree

各ノードが白(1)または黒(0)で色付けされた木が与えられます。各ノードについて、そのノードを含む連結部分木での(白ノード数 - 黒ノード数)の最大値を求めてください。

解法：木DPと全方位木DPを使用します。

#include <iostream>
#include <vector>
using namespace std;

vector<int> color;
vector<vector<int>> graph;
vector<int> dp;
vector<int> answer;

void dfs1(int node, int parent) {
    dp[node] = color[node] ? 1 : -1;
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        dfs1(neighbor, node);
        if (dp[neighbor] > 0) {
            dp[node] += dp[neighbor];
        }
    }
}

void dfs2(int node, int parent) {
    answer[node] = dp[node];
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        
        int original_node = dp[node];
        int original_neighbor = dp[neighbor];
        
        if (dp[neighbor] > 0) {
            dp[node] -= dp[neighbor];
        }
        if (dp[node] > 0) {
            dp[neighbor] += dp[node];
        }
        
        dfs2(neighbor, node);
        
        dp[node] = original_node;
        dp[neighbor] = original_neighbor;
    }
}

int main() {
    int n;
    cin >> n;
    
    color.resize(n + 1);
    graph.resize(n + 1);
    dp.resize(n + 1);
    answer.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    dfs1(1, 0);
    dfs2(1, 0);
    
    for (int i = 1; i <= n; i++) {
        cout << answer[i] << " ";
    }
    
    return 0;
}