C. Clone Ranran

本問題は、自身のクローンを作成する時間と、問題を作成する時間のバランスを取って最小の総時間を求めるものです。

クローンを作成する回数を全探索します。クローンを作成するたびに人数は2倍になるため、対数オーダーの探索で済みます。各ステップにおいて、必要な問題数を現在の人数で割ったもの（切り上げ）を作成時間に乗算し、クローン作成時間と合算して最小値を更新します。

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

void solve() {
    long long clone_time, problem_time, target_problems;
    cin >> clone_time >> problem_time >> target_problems;
    
    long long min_cost = 1e18;
    long long current_people = 1;
    long long clone_count = 0;
    
    while (current_people <= target_problems) {
        long long required_problems = (target_problems + current_people - 1) / current_people;
        long long current_cost = clone_time * clone_count + problem_time * required_problems;
        min_cost = min(min_cost, current_cost);
        
        current_people *= 2;
        clone_count++;
    }
    
    long long required_problems = (target_problems + current_people - 1) / current_people;
    long long current_cost = clone_time * clone_count + problem_time * required_problems;
    min_cost = min(min_cost, current_cost);
    
    cout << min_cost << "\n";
}

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

E. Find Maximum

関数 f(x) は、x を3進数で表現した際の「各桁の数字の合計」と「桁数」の和として定義されます。このスコアを最大化するためには、3進数表現において可能な限り多くの 2 を含む数を構成する必要があります。

上限値 R の3進数表現を基準とし、ある桁の数字を1減らし、それより下の桁をすべて 2 で埋めた候補値を生成します。この候補値が下限値 L 以上であれば、そのスコアを計算して最大値を更新します。

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

long long calc_score(long long val) {
    if (val == 0) return 1;
    long long sum = 0, len = 0;
    long long temp = val;
    while (temp > 0) {
        sum += temp % 3;
        temp /= 3;
        len++;
    }
    return sum + len;
}

void solve() {
    long long L, R;
    cin >> L >> R;
    
    vector<int> digits;
    long long temp = R;
    while (temp > 0) {
        digits.push_back(temp % 3);
        temp /= 3;
    }
    reverse(digits.begin(), digits.end());
    
    long long max_score = calc_score(R);
    
    for (size_t i = 0; i < digits.size(); ++i) {
        if (digits[i] == 0) continue;
        
        long long candidate = 0;
        for (size_t j = 0; j < i; ++j) {
            candidate = candidate * 3 + digits[j];
        }
        candidate = candidate * 3 + (digits[i] - 1);
        for (size_t j = i + 1; j < digits.size(); ++j) {
            candidate = candidate * 3 + 2;
        }
        
        if (candidate >= L) {
            max_score = max(max_score, calc_score(candidate));
        }
    }
    
    cout << max_score << "\n";
}

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

F. Hotel

3人1組のチームに対して、シングルルームとダブルルームの料金が与えられます。ダブルルームは同性の2人でしか利用できないという制約があるため、チーム内の性別の構成を確認します。

男性が2人以上、または女性が2人以上いる場合は、「シングル1室＋ダブル1室」または「ダブル2室」の割り当ても候補に加え、最小コストを計算します。

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

void solve() {
    int teams, cost_single, cost_double;
    cin >> teams >> cost_single >> cost_double;
    
    long long total_cost = 0;
    for (int i = 0; i < teams; ++i) {
        string members;
        cin >> members;
        
        int males = 0, females = 0;
        for (char c : members) {
            if (c == 'M') males++;
            else females++;
        }
        
        long long min_cost = 3LL * cost_single;
        
        if (males >= 2 || females >= 2) {
            min_cost = min(min_cost, (long long)cost_double + cost_single);
            min_cost = min(min_cost, 2LL * cost_double);
        }
        
        total_cost += min_cost;
    }
    
    cout << total_cost << "\n";
}

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

G. Perfect Word

長さ1の文字列は常に「完全な単語」です。長さ2以上の文字列については、先頭の文字を除いた部分列と、末尾の文字を除いた部分列の両方が完全な単語である場合、その文字列も完全な単語となります。

文字列を長さの昇順でソートし、ハッシュセット等を用いて完全な単語を記録しながら動的に判定を行うことで、最も長い完全な単語の長さを求めることができます。

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

void solve() {
    int n;
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; ++i) {
        cin >> words[i];
    }
    
    sort(words.begin(), words.end(), [](const string& a, const string& b) {
        return a.length() < b.length();
    });
    
    unordered_set<string> perfect_words;
    int max_len = 0;
    
    for (const string& w : words) {
        if (w.length() == 1) {
            perfect_words.insert(w);
            max_len = max(max_len, 1);
        } else {
            string prefix = w.substr(0, w.length() - 1);
            string suffix = w.substr(1);
            
            if (perfect_words.count(prefix) && perfect_words.count(suffix)) {
                perfect_words.insert(w);
                max_len = max(max_len, (int)w.length());
            }
        }
    }
    
    cout << max_len << "\n";
}

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

J. Strange Sum

問題の制約により、選択する要素のインデックスの差に関する条件が課されています。結果として、配列から選択できる正の要素は最大で2つまでに制限されます。

したがって、配列を降順にソートし、先頭から最大2つの正の値を加算するだけで最適解が得られます。正の値が存在しない場合は0を出力します。

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

void solve() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    sort(arr.rbegin(), arr.rend());
    
    long long max_sum = 0;
    int count = 0;
    for (int i = 0; i < n && count < 2; ++i) {
        if (arr[i] > 0) {
            max_sum += arr[i];
            count++;
        } else {
            break;
        }
    }
    
    cout << max_sum << "\n";
}

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

L. Tree

条件1を満たす集合は「パス（鎖）」、条件2を満たす集合は「アンチチェーン」と見なせます。部分集合の数を最小化するためには、葉ノードから順にアンチチェーンを形成していくのが最適です。

深さ優先探索（DFS）を用いて、各ノードから葉までのパスの長さを計算します。最も長いパス以外を独立したパスとしてカウントし、パスの長さごとの本数を記録します。最後に、アンチチェーンとして削除するパスの長さを全探索し、「残りのパスの数＋削除した回数（アンチチェーンの数）」の最小値を求めます。

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

vector<int> chain_counts;

int dfs(const vector<vector<int>>& adj, int u, int parent) {
    vector<int> child_depths;
    for (int v : adj[u]) {
        if (v != parent) {
            child_depths.push_back(dfs(adj, v, u));
        }
    }
    
    if (child_depths.empty()) {
        return 1;
    }
    
    sort(child_depths.begin(), child_depths.end());
    int num_children = child_depths.size();
    
    for (int i = 0; i < num_children - 1; ++i) {
        chain_counts[child_depths[i]]++;
    }
    
    return 1 + child_depths.back();
}

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        adj[i].push_back(p);
        adj[p].push_back(i);
    }
    
    chain_counts.assign(n + 1, 0);
    int tree_max_depth = dfs(adj, 1, 0);
    chain_counts[tree_max_depth]++;
    
    int total_chains = accumulate(chain_counts.begin(), chain_counts.end(), 0);
    int min_subsets = total_chains;
    
    int removed_chains = 0;
    for (int i = 0; i <= tree_max_depth; ++i) {
        removed_chains += chain_counts[i];
        int current_subsets = (total_chains - removed_chains) + i;
        min_subsets = min(min_subsets, current_subsets);
    }
    
    cout << min_subsets << "\n";
}

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