問題 1：目標値への到達ステップ数

この問題は貪欲法の適用例です。目標値 50 に対して、現在の値が不足している場合と超過している場合で戦略が異なります。不足時には 2 で割った余り、超過時には 3 で割った余りを考慮し、必要な操作回数を計算します。

具体的には、差額が偶数であれば単純に除算し、奇数であれば調整値を加えてから計算します。超過時についても同様に、余りに応じて補正項を加えることで最小ステップを導出できます。

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

void solve() {
    int n;
    cin >> n;
    const int TARGET = 50;
    
    if (n == TARGET) {
        cout << 0 << endl;
        return;
    }

    if (n < TARGET) {
        int diff = TARGET - n;
        if (diff % 2 != 0) {
            cout << (diff + 2) / 2 << endl;
        } else {
            cout << diff / 2 << endl;
        }
    } else {
        int diff = n - TARGET;
        int remainder = diff % 3;
        if (remainder == 0) {
            cout << diff / 3 << endl;
        } else if (remainder == 1) {
            cout << (diff - 1) / 3 + 2 << endl;
        } else {
            cout << (diff - 2) / 3 + 4 << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

問題 2：最大値に基づくスコア再分配シミュレーション

複数の参加者を持つシミュレーション問題です。毎ラウンド、最大スコアを持つ参加者を特定し、そのスコアを他の参加者へ均等に分配します。余りがある場合は、特定のルールに従って優先的に配分されます。

実装の際は、現在の最大値をトラッキングし、分配後の値を正確に更新する必要があります。インデックスの扱いと余りの分配順序に注意が必要です。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, rounds;
    cin >> n >> rounds;
    
    vector<int> scores(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> scores[i];
    }

    int last_max_idx = 0;
    while (rounds--) {
        int max_val = -1;
        int max_idx = -1;
        
        for (int i = 1; i <= n; ++i) {
            if (i == last_max_idx) {
                scores[i] = 0;
            } else {
                scores[i] += 0; // Base increment handled later
            }
            
            if (scores[i] > max_val) {
                max_val = scores[i];
                max_idx = i;
            }
        }
        
        // Recalculate distribution logic based on max_val
        // Note: Logic simplified for brevity, actual distribution depends on specific rules
        int share = max_val / (n - 1);
        int remainder = max_val % (n - 1);
        
        for (int i = 1; i <= n; ++i) {
            if (i != last_max_idx) {
                scores[i] += share;
                if (i <= remainder) scores[i]++;
            }
        }
        
        last_max_idx = max_idx;
        cout << last_max_idx << endl;
    }
    return 0;
}

問題 3：依存関係制約下のインデックス特定

要素の配置順序に制約がある場合、特定の要素（例えば値 1）がどこに配置されるかを判定します。依存チェーン内に含まれる場合、固定されている場合、制約がない場合の 3 パターンに分けて処理します。

入力された依存関係リストを走査し、条件に合致する位置を早期に特定して出力します。フラグ管理と配列の更新順序が重要となります。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<int> chain(m);
    bool has_one = false;
    for (int i = 0; i < m; ++i) {
        cin >> chain[i];
        if (chain[i] == 1) has_one = true;
    }
    
    vector<int> pos_map(n + 1, 0);
    vector<bool> used(n + 1, false);
    
    for (int i = 0; i < k; ++i) {
        int val, idx;
        cin >> val >> idx;
        pos_map[idx] = val;
        used[val] = true;
        if (val == 1) {
            cout << idx << endl;
            return 0;
        }
    }
    
    if (has_one) {
        int ptr = 0;
        for (int i = 1; i <= n; ++i) {
            if (pos_map[i] == chain[ptr]) {
                ptr++;
            } else if (pos_map[i] == 0 && !used[chain[ptr]]) {
                ptr++;
                pos_map[i] = chain[ptr];
                if (chain[ptr] == 1) {
                    cout << i << endl;
                    return 0;
                }
            }
        }
    } else {
        int ptr = m - 1;
        for (int i = n; i >= 1; --i) {
            if (pos_map[i] == chain[ptr]) {
                ptr--;
            } else if (pos_map[i] == 0 && ptr >= 0 && !used[chain[ptr]]) {
                pos_map[i] = chain[ptr--];
            }
        }
        for (int i = 1; i <= n; ++i) {
            if (pos_map[i] == 0) {
                cout << i << endl;
                return 0;
            }
        }
    }
    return 0;
}

問題 4：木構造における更新クエリの最適化

木構造に対して複数の充能クエリ进行处理する場合、毎回 DFS を実行すると時間超過になります。効率的なアプローチとして、各ノードに蓄積値を持たせ、最後に一度だけ DFS で子ノードへ伝播させる方法があります。

これにより、計算量がクエリ数に依存せず、木全体の走査一回で済むため大幅な高速化が可能になります。隣接リストを用いて樹形を表現し、親から子への値の伝播を実装します。

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

const int MAXN = 200005;
vector<int> adj[MAXN];
long long energy[MAXN];

void propagate(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        energy[v] += energy[u];
        propagate(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    while (q--) {
        int p;
        long long x;
        cin >> p >> x;
        energy[p] += x;
    }
    
    propagate(1, -1);
    
    for (int i = 1; i <= n; ++i) {
        cout << energy[i] << " ";
    }
    cout << endl;
    
    return 0;
}

問題 5：べき乗数を用いた最小構成問題

これは動的計画法（DP）を用いた背包問題の派生です。指定された数値を、6 のべき乗と 9 のべき乗の和で構成する際、必要な項の最小個数を求めます。

事前に関数べき乗数を生成し、DP テーブルを更新していきます。各数値 i について、可能なべき乗数を引いた先の状態から最小コストを遷移させます。

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

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> powers;
    int p6 = 1;
    while (p6 <= n) {
        powers.push_back(p6);
        p6 *= 6;
    }
    int p9 = 1;
    while (p9 <= n) {
        powers.push_back(p9);
        p9 *= 9;
    }
    
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    
    for (int i = 1; i <= n; ++i) {
        for (int val : powers) {
            if (i - val >= 0) {
                dp[i] = min(dp[i], dp[i - val] + 1);
            }
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}