P1628 合并序列 - 文字列のマージ

指定されたプレフィックスで始まるすべての文字列をマルチセットに格納し（重複を許可し、自動的にソートされる）、出力します。

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<string> input_strings(N);
    for (auto &str : input_strings)
        cin >> str;

    string prefix;
    cin >> prefix;

    multiset<string> results;
    for(const auto &str : input_strings) {
        if(str.length() < prefix.length()) continue;
        if(str.substr(0, prefix.length()) == prefix)
            results.insert(str);
    }

    for(const auto &str : results)
        cout << str << '\n';

    return 0;
}

P1403 約数研究 - 約数のカウント

1からNまでの各数について、その約数の総数を計算します。公式 ans += ⌊N/i⌋ を使用します。

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long total = 0;
    for(int i = 1; i <= N; i++) {
        total += N / i;
    }

    cout << total << '\n';

    return 0;
}

P1644 跳马问题 - 騎士の移動

小さなデータ範囲なので、深さ優先探索（DFS）で全探索します。動的計画法（DP）でも可能ですが、DFSの方が実装が簡単です。

#include <iostream>

using namespace std;

int n, m;
long long count_paths = 0;

void dfs(int x, int y) {
    if(x > n || y > m || x < 0 || y < 0) return;
    
    if(x == n && y == m) {
        count_paths++;
        return;
    }
    
    // 騎士の8方向の移動
    int moves_x[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int moves_y[] = {1, 2, 2, 1, -1, -2, -2, -1};
    
    for(int i = 0; i < 8; i++) {
        dfs(x + moves_x[i], y + moves_y[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    dfs(0, 0);
    cout << count_paths << '\n';

    return 0;
}

P1122 最大子樹和 - 木の部分和最大化

各ノードを根とする部分木の和を計算し、最大値を求めます。子ノードの値が正の場合のみ加算します。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

vector<vector<int>> tree;
vector<int> values;
vector<long long> dp;

long long calculate_subtree_sum(int node, int parent) {
    long long current_sum = values[node];
    
    for(int neighbor : tree[node]) {
        if(neighbor == parent) continue;
        long long child_sum = calculate_subtree_sum(neighbor, node);
        if(child_sum > 0) {
            current_sum += child_sum;
        }
    }
    
    dp[node] = current_sum;
    return current_sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int num_nodes;
    cin >> num_nodes;

    values.resize(num_nodes + 1);
    tree.resize(num_nodes + 1);
    dp.resize(num_nodes + 1);

    for(int i = 1; i <= num_nodes; i++) {
        cin >> values[i];
    }

    for(int i = 1; i < num_nodes; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    calculate_subtree_sum(1, 0);
    
    long long max_sum = LLONG_MIN;
    for(int i = 1; i <= num_nodes; i++) {
        max_sum = max(max_sum, dp[i]);
    }

    cout << max_sum << '\n';

    return 0;
}

P1510 精衛填海 - 0/1ナップサック問題

ナップサック問題ですが、容量vをちょうど満たす必要はなく、v以上の容量でも許されます。そのため、容量を2倍に拡張して計算します。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int volume, num_items, max_energy;
    cin >> volume >> num_items >> max_energy;
    
    vector<int> item_volumes(num_items);
    vector<int> item_energies(num_items);
    
    for(int i = 0; i < num_items; i++) {
        cin >> item_volumes[i] >> item_energies[i];
    }

    vector<long long> dp(2 * volume + 1, INT_MAX);
    dp[0] = 0;
    
    for(int i = 0; i < num_items; i++) {
        for(int j = 2 * volume; j >= item_volumes[i]; j--) {
            if(dp[j - item_volumes[i]] != INT_MAX) {
                dp[j] = min(dp[j], dp[j - item_volumes[i]] + item_energies[i]);
            }
        }
    }

    long long min_energy = INT_MAX;
    for(int j = volume; j <= 2 * volume; j++) {
        if(dp[j] != INT_MAX) {
            min_energy = min(min_energy, dp[j]);
        }
    }

    if(min_energy <= max_energy) {
        cout << max_energy - min_energy << '\n';
    } else {
        cout << "Impossible\n";
    }

    return 0;
}