GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)

A. Potions

현재 체력 H에서 $P_i$만큼 회복시킬 수 있는 포션을 먹을 때 체력이 X만큼 차면서 X에 가장 가까운 i를 찾는 문제이다.

포션이 오름차순으로 입력되므로 포션과 체력을 더해준 뒤 lower_bound로 문제에서 원하는 포션 인덱스를 구한다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int,int,int> tiii;
const int INF=1e9+1;

int main() {
    fastio
    int n,h,x; cin>>n>>h>>x;
    vector<int> p;
    for(int i=0;i<n;i++) {
        int pi; cin>>pi;
        p.push_back(pi+h);
    }
    cout<<lower_bound(p.begin(),p.end(),x)-p.begin()+1<<endl;
    return 0;
}

B. MissingNo.

주어진 배열 내 빠진 수를 찾는 문제이다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int,int,int> tiii;
const int INF=1e9+1;

int main() {
    fastio
    int n; cin>>n;
    set<int> s;
    while(n--) {
        int x; cin>>x;
        s.insert(x);
    }
    int min_value=*s.begin();
    int max_value=*s.rbegin();
    for(int i=min_value;i<=max_value;i++) {
        if(s.find(i)==s.end()) {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}

C. Remembering the Days

도시 $A_i$와 도시 $B_i$가 길이 $C_i$인 도로로 연결되어 있다.

연결된 모든 도시를 탐색하면서 가장 길게 탐색해야 한다.

도시의 수가 10개(10! = 3628800)이므로 완전탐색 할 수 있고 모든 도시가 연결되어 있지 않아도 연결된 도시는 이동하면서 가장 긴 움직인 길이를 출력해야 한다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int,int,int> tiii;
const int INF=1e9+1;
vector<pii> r[11];

int dfs(int node, int dist, vector<int> &visit) {
    int m=0;
    for(auto it : r[node]) {
        auto [next, road]=it;
        if(!visit[next]) {
            visit[next]=1;
            m=max(m,dfs(next,dist+road,visit));
            visit[next]=0;
        }
    }
    if(!m) return dist;
    return m;
}

int main() {
    fastio
    int n,m; cin>>n>>m;
    for(int i=0;i<m;i++) {
        int a,b,c; cin>>a>>b>>c;
        r[a].push_back({b,c});
        r[b].push_back({a,c});
    }
    int r=0;
    for(int i=1;i<=n;i++) {
        vector<int> visit(11);
        visit[i]=1;
        r=max(r,dfs(i,0,visit));
    }
    cout<<r;
    return 0;
}

D. President

N개의 선거구마다 Takahashi와 Aoki의 지지자들이 $X_i$, $Y_i$만큼 있고 선거구에서 승리한다면 $Z_i$만큼의 의석수를 얻을 수 있다.

최종 의석수에서 Takahashi가 Aoki보다 만으려면 Aoki의 지지자가 Takahashi로 최소 몇명이 움직여야 하는지 출력하는 문제다.

냅색 문제와 같이 DP로 풀 수 있는데 DP[z]는 의석수 z를 확보할 때 최소 움직인 지지자의 수를 의미한다.

#include <bits/stdc++.h>
#define endl '\n'
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int,int,int> tiii;
// const int INF=1e9+1;
const ll INF=1e18;

int main() {
    fastio
    freopen("input.txt","r",stdin);
    int n; cin>>n;
    vector<int> x(n), y(n), z(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i]>>z[i];
    int totz=accumulate(z.begin(),z.end(),0);
    // knapsack
    vector<ll> dp(totz+1,INF);
    dp[0]=0;
    for(int i=0;i<n;i++) {
        // p : i번째 선거구에서 움직여야 하는 최소 사람의 수
        ll p=max(0,(x[i]+y[i])/2+1-x[i]);
        for(int j=totz;j>=z[i];j--) dp[j]=min(dp[j],dp[j-z[i]]+p);
    }
    ll ans=INF;
    for(int i=totz/2+1;i<=totz;i++) ans=min(ans,dp[i]);
    cout<<ans;
    return 0;
}