T1: 메시지 필터링

문제 개요

총 n개의 채팅방을 순서대로 확인하며, 각 메시지에 bie 부분 문자열이 포함되어 있고 아직 전송한 적 없는 경우에만 전송한다. 전송할 메시지가 없는 채팅방은 특정 문구를 출력한다.

해결 방법

문자열 탐색과 중복 체크가 핵심이다. bie 존재 여부는 단순 순회로 확인하고, 중복 방지를 위해 해싱 기법을 활용한다. 더블 해싱을 적용해 충돌 확률을 최소화한다.

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
const ull BASE_A = 131, BASE_B = 137;
const ull MOD_A = 1000000007, MOD_B = 998244353;

struct HashPair {
    ull h1, h2;
    bool operator<(const HashPair& o) const {
        return h1 != o.h1 ? h1 < o.h1 : h2 < o.h2;
    }
};

HashPair calc_hash(const string& s) {
    ull r1 = 0, r2 = 0;
    for (char ch : s) {
        r1 = (r1 * BASE_A + ch) % MOD_A;
        r2 = (r2 * BASE_B + ch) % MOD_B;
    }
    return {r1, r2};
}

bool contains_target(const string& s) {
    for (size_t i = 0; i + 2 < s.size(); ++i)
        if (s[i] == 'b' && s[i+1] == 'i' && s[i+2] == 'e')
            return true;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("message.in", "r", stdin);
    freopen("message.out", "w", stdout);
    
    int room_cnt;
    cin >> room_cnt;
    
    set<HashPair> sent;
    
    for (int r = 0; r < room_cnt; ++r) {
        int msg_cnt;
        cin >> msg_cnt;
        
        bool any_sent = false;
        for (int m = 0; m < msg_cnt; ++m) {
            string msg;
            cin >> msg;
            
            if (!contains_target(msg)) continue;
            
            auto h = calc_hash(msg);
            if (sent.insert(h).second) {
                cout << msg << '\n';
                any_sent = true;
            }
        }
        
        if (!any_sent)
            cout << "Genshin Impact, start!\n";
    }
    
    return 0;
}

T2: 수정 나비 수집

문제 개요

1번 정점에서 시작해 단위 시간당 거리 1만큼 이동한다. 각 정점 i에는 a_i마리의 수정 나비가 있으며, 인접 정점에 도착한 후 t_i시간이 지나면 사라진다. 서브트리를 완전 탐색하는 전략 하에서 최대 수집량을 구한다.

관찰

t_i ≤ 3이라는 조건이 핵심이다. t_i = 1, 2인 경우와 t_i = 3인 경우를 구분해 접근해야 한다. 서브트리를 모두 방문한 후 돌아오는 경로에서 추가 획득 가능 여부가 달라진다.

동적 계획법 설계

dp[v]: 정점 v의 자식들로 진입하여 얻을 수 있는 최대 나비 수 (정점 v 자체는 제외)
sum[v]: 모든 자식의 dp 값의 합

각 정점에서 두 가지 선택지를 고려한다:

• 특정 자식으로 진입 후 해당 서브트리를 완전 탐색하고 복귀
• 한 자식으로 진입 후 즉시 복귀, t_i = 3인 다른 자식으로 재진입

두 번째 경우를 위해 t_i = 3인 자식들 중 a_i가 가장 큰 두 값을 미리 계산해둔다.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct NodeInfo {
    ll butterfly;
    int disappear_time;
};

int n;
vector<NodeInfo> info;
vector<vector<int>> tree;

vector<ll> subtree_dp;
vector<ll> children_sum;

void solve(int cur, int parent) {
    for (int nxt : tree[cur]) {
        if (nxt == parent) continue;
        solve(nxt, cur);
    }
    
    // t_i = 3인 자식들 중 top 2 선별
    int best_idx = 0, second_idx = 0;
    for (int nxt : tree[cur]) {
        if (nxt == parent) continue;
        children_sum[cur] += subtree_dp[nxt];
        
        if (info[nxt].disappear_time == 3) {
            if (info[nxt].butterfly >= info[best_idx].butterfly) {
                second_idx = best_idx;
                best_idx = nxt;
            } else if (info[nxt].butterfly > info[second_idx].butterfly) {
                second_idx = nxt;
            }
        }
    }
    
    // 경우 1: 한 자식으로 들어가서 완전 탐색
    for (int nxt : tree[cur]) {
        if (nxt == parent) continue;
        subtree_dp[cur] = max(subtree_dp[cur], 
            children_sum[cur] + info[nxt].butterfly);
    }
    
    // 경우 2: 한 자식으로 들어가서 즉시 복귀, 다른 t=3 자식으로 재진입
    for (int nxt : tree[cur]) {
        if (nxt == parent) continue;
        
        ll base = children_sum[cur] - subtree_dp[nxt] + info[nxt].butterfly 
                  + children_sum[nxt];
        
        if (nxt != best_idx && best_idx != 0)
            subtree_dp[cur] = max(subtree_dp[cur], base + info[best_idx].butterfly);
        if (nxt != second_idx && second_idx != 0)
            subtree_dp[cur] = max(subtree_dp[cur], base + info[second_idx].butterfly);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("crystalfly.in", "r", stdin);
    freopen("crystalfly.out", "w", stdout);
    
    int tc;
    cin >> tc;
    
    while (tc--) {
        cin >> n;
        info.assign(n + 1, {0, 0});
        tree.assign(n + 1, {});
        subtree_dp.assign(n + 1, 0);
        children_sum.assign(n + 1, 0);
        
        for (int i = 1; i <= n; ++i) cin >> info[i].butterfly;
        for (int i = 1; i <= n; ++i) {
            int t; cin >> t;
            info[i].disappear_time = (t - 1) / 2 + 1; // 1,2→1 / 3→2로 변환
        }
        
        for (int i = 1; i < n; ++i) {
            int u, v; cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        
        solve(1, 0);
        cout << subtree_dp[1] + info[1].butterfly << '\n';
    }
    
    return 0;
}

T3: 장비 최적화

문제 개요

n개의 장비를 순서를 정해 장착한다. 현재까지 사용한 에너지 합이 sum일 때, 장비 i를 장착하면 sum + p_i ≤ m이면 w_{i,p_i}, sum ≥ m이면 0, 그 외에는 w_{i,m-sum}의 효과를 얻는다.

해결 방법

마지막 장비만 특수 효과를 발휘하므로, 마지막 여부를 상태로 포함하는 배낭 문제로 변환한다.

f[i][j][0/1]: 처음 i개 중 선택, 총 에너지 j 사용, 마지막 장비 선택 여부

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    freopen("rpg.in", "r", stdin);
    freopen("rpg.out", "w", stdout);
    
    int item_cnt, energy_limit;
    cin >> item_cnt >> energy_limit;
    
    vector<int> cost(item_cnt + 1);
    vector<vector<ll>> value(item_cnt + 1);
    
    for (int i = 1; i <= item_cnt; ++i) {
        cin >> cost[i];
        value[i].resize(cost[i] + 1);
        for (int j = 1; j <= cost[i]; ++j)
            cin >> value[i][j];
    }
    
    // f[j][0]: 마지막 미선택, f[j][1]: 마지막 선택 완료
    vector<vector<ll>> dp(energy_limit + 1, vector<ll>(2, -1e18));
    dp[0][0] = 0;
    
    for (int i = 1; i <= item_cnt; ++i) {
        auto ndp = dp;
        for (int used = 0; used <= energy_limit; ++used) {
            // 일반 장비로 선택 (마지막이 아님)
            if (used + cost[i] <= energy_limit && dp[used][0] > -1e17) {
                ndp[used + cost[i]][0] = max(ndp[used + cost[i]][0], 
                    dp[used][0] + value[i][cost[i]]);
                ndp[used + cost[i]][1] = max(ndp[used + cost[i]][1], 
                    dp[used][1] + value[i][cost[i]]);
            }
            // 마지막 장비로 선택
            for (int k = 1; k <= cost[i] && used + k <= energy_limit; ++k) {
                if (dp[used][0] > -1e17)
                    ndp[used + k][1] = max(ndp[used + k][1], 
                        dp[used][0] + value[i][k]);
            }
        }
        dp = move(ndp);
    }
    
    ll answer = dp[energy_limit][1];
    for (int j = 0; j <= energy_limit; ++j)
        answer = max(answer, dp[j][0]);
    
    cout << answer << '\n';
    
    return 0;
}