A: 別の注文方法

料理とセットで購入する場合、特定のドリンクが定価 \(P\) から割引価格 \(Q\) へ変更される。セット購入しない場合は、別のドリンクリストから任意の価格のものを選ぶことができる。支払い額を最小化する問題である。

実装方針は単純である。セット割引適用時の支払い額 \(Q + \min(A)\) と、割引なしの定価 \(P\) を比較し、小さい方を出力すればよい。\(O(N)\) で計算可能である。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n_items;
    long long base_price, discount_price;
    if (!(std::cin >> n_items >> base_price >> discount_price)) return 0;

    long long min_alt_price = 1e18;
    for (int i = 0; i < n_items; ++i) {
        long long price;
        std::cin >> price;
        if (price < min_alt_price) min_alt_price = price;
    }

    long long result = std::min(base_price, discount_price + min_alt_price);
    std::cout << result << "\n";
    return 0;
}

B: 厳密に優位な製品

\(N\) 種類の製品が存在し、それぞれ価格と機能の集合が与えられる。ある製品 \(j\) が製品 \(i\) に対して「厳密に優位」であるための条件は以下の3つを全て満たすことである。

• 製品 \(j\) の価格は製品 \(i\) 以下である (\(P_j \le P_i\))
• 製品 \(j\) は製品 \(i\) の全機能を含む
• 価格がより安いか、または機能数がより多い (\(P_j < P_i\) または \(|F_j| > |F_i|\))

制約が小さいため、全ての製品ペアを総当たりで検証すればよい。機能の包含関係は、ソート済みの配列に対する std::includes を用いることで効率的に判定できる。計算量は \(O(N^2 \cdot M)\) 程度に収まり、十分高速である。

#include <iostream>
#include <vector>
#include <algorithm>

struct Product {
    long long price;
    std::vector<int> features;
};

bool solve() {
    int n_products, m_features_total;
    std::cin >> n_products >> m_features_total;

    std::vector<Product> items(n_products);
    for (auto &item : items) {
        std::cin >> item.price;
        int k;
        std::cin >> k;
        item.features.resize(k);
        for (auto &f : item.features) std::cin >> f;
        std::sort(item.features.begin(), item.features.end());
    }

    for (int i = 0; i < n_products; ++i) {
        for (int j = 0; j < n_products; ++j) {
            if (i == j) continue;
            if (items[j].price <= items[i].price) {
                if (items[i].features.size() > items[j].features.size()) continue;
                bool contains_all = std::includes(items[j].features.begin(), items[j].features.end(),
                                                  items[i].features.begin(), items[i].features.end());
                if (contains_all && (items[j].price < items[i].price || items[j].features.size() > items[i].features.size())) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << (solve() ? "Yes" : "No") << "\n";
    return 0;
}

C: 反転可能

文字列 \(S\) とその逆順文字列 \(S^R\) は同一のアイテムとして扱う。入力として \(N\) 個の文字列が与えられたとき、重複を除いたユニークなアイテム数を求める。

各文字列について、辞書順で小さい方（\(S\) か \(S^R\) のいずれか）を代表元として選択し、std::unordered_set に格納することで重複排除を行う。最終的なセットの要素数が答えとなる。

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

int main() {
    int n_strings;
    std::cin >> n_strings;

    std::unordered_set<std::string> canonical_forms;
    for (int i = 0; i < n_strings; ++i) {
        std::string s;
        std::cin >> s;
        std::string rev = s;
        std::reverse(rev.begin(), rev.end());
        canonical_forms.insert(std::min(s, rev));
    }
    std::cout << canonical_forms.size() << "\n";
    return 0;
}

D: 平穏なチーム

\(N\) 人の参加者を \(T\) 個のグループに分ける問題である。ただし、指定された \(M\) 組の人物同士は同じグループに入れてはならない。条件を満たす分割方法の総数を出力する。

\(N\) と \(T\) の制約が小さいため、深さ優先探索による全探索が適用可能である。各参加者に対して順にグループを割り当て、既に配置された参加者との衝突をチェックする。グループの区別をなくして数え上げる場合、割り当てるグループ番号を「現在使用中の最大番号 + 1」までに制限する正規化を行うことで、同一の分割を重複して数えるのを防ぐことができる。探索の末端で、使用グループ数が \(T\) に一致するかを検証する。

#include <iostream>
#include <vector>

int N, T, M;
std::vector<std::vector<bool>> conflict;
std::vector<int> group_assignment;
long long valid_ways = 0;

void dfs(int person_idx, int used_groups_max) {
    if (person_idx == N) {
        if (used_groups_max == T - 1) {
            valid_ways++;
        }
        return;
    }

    for (int g = 0; g <= used_groups_max + 1 && g < T; ++g) {
        bool ok = true;
        for (int p = 0; p < person_idx; ++p) {
            if (group_assignment[p] == g && conflict[person_idx][p]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            group_assignment[person_idx] = g;
            dfs(person_idx + 1, std::max(used_groups_max, g));
        }
    }
}

int main() {
    std::cin >> N >> T >> M;
    conflict.assign(N, std::vector<bool>(N, false));
    group_assignment.resize(N);

    for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u; --v;
        conflict[u][v] = conflict[v][u] = true;
    }

    dfs(0, -1);
    std::cout << valid_ways << "\n";
    return 0;
}