Atcoder Weekday Contest 056
Atcoder Weekday Contest 056 풀이
6/24/2026 · 4 min read
각 레시피의 기본점 를 배열에 저장해두고, M개 요리마다 어떤 레시피를 썼는지·아레인지점이 얼마인지만 보고 누적하면 끝.
ll n, m, res;
auto solve = [](){
ri(n, m);
vl v(n + 1);
for(int i = 1; i <= n; i++) ri(v[i]);
while(m--){
ll a,b; ri(a, b);
res += (v[a] + b);
}
po(res);
};Time
절전모드로 바꾸면 가 되니, 절약량은 가 클수록 커진다. 그러니 전체 소비전력을 최소화하려면 절약량이 가장 큰, 즉 가 가장 큰 기기 대를 골라 절전모드로 돌리는 게 최적. 내림차순 정렬 후 앞 개만 반으로 깎아주면 된다.
ll n, k, res;
auto solve = [](){
ri(n, k);
vl v(n);
ri(v);
sort(rall(v));
for(int i = 0; i < k; i++) res += (v[i] / 2);
for(int i = k; i < n; i++) res += v[i];
po(res);
};Time
구간 합이 이하면서 길이가 최대인 구간을 찾는 문제. 가 전부 양수라 오른쪽 끝 을 늘릴수록 구간합이 단조증가하니, 을 한 칸씩 늘리다가 합이 를 넘으면 왼쪽 끝 을 줄여 다시 이하로 맞추는 투 포인터로 해결가능.
ll n,k,mx;
auto solve = [](){
ri(n, k);
vl v(n + 1);
for(int i = 1; i <= n; i++){
ri(v[i]);
}
ll cur = 0;
ll l = 1;
for(ll r = 1; r <= n; r++){
cur += v[r];
while(cur > k){
cur -= v[l];
l++;
}
mx = max(mx, r - l + 1);
}
po(mx);
};Time
AtCoder문제 보기
D - Dividing the Flower Bed into Sections
업솔빙 예정;;
라서 들러야 하는 지점은 출발지 까지 합쳐 최대 16개뿐이고, 나머지 노드는 그냥 지나가는 길이다. 배송지도 지나가기만 하면 자동으로 완료되니 별도 처리가 필요 없다. 그래서 이 16개 지점 사이의 최단거리만 다익스트라로 미리 구해두고, 그 위에서 외판원 문제처럼 비트마스크 DP로 "모든 배송지를 들르고 S로 복귀하는 최소 비용"을 구하면 된다.
ll n,m,k,s;
vector<vector<pll>> g;
ll I[22];
ll dp[16][1 << 16];
vector<ll> dijkstra(vector<vector<pair<ll, ll>>>& g, int st){
vector<ll> dist(n + 1, iinf);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
pq.push({dist[st] = 0, st});
while(pq.size()){
auto [cdist, cur] = pq.top(); pq.pop();
if(dist[cur] < cdist) continue;
for(const auto& [cost, nxt] : g[cur]){
if(dist[nxt] > cdist + cost) pq.push({dist[nxt] = cdist + cost, nxt});
}
}
return dist;
}
auto solve = [](){
ri(n, m);
g.resize(n + 1);
for(int i = 0; i < m; i++){
ll a,b,c; ri(a, b, c);
g[a].pb({c, b}); g[b].pb({c, a});
}
ri(s, k);
vl v{s};
for(int i = 1; i <= k; i++){
ll x; ri(x); v.pb(x);
}
int N = si(v);
vector<vector<ll>> dist(N, vl(N, iinf));
for(int i = 0; i < N; i++){
dist[i][i] = 0;
auto d = dijkstra(g, v[i]);
for(int j = 0; j < N; j++){
dist[i][j] = d[v[j]];
}
}
memset(dp, -1, sizeof(dp));
ll FULL = (1 << N) - 1;
auto tsp = [&](int cur, int state, auto&& tsp) -> ll{
if(state == FULL) return dist[cur][0];
ll& ret = dp[cur][state];
if(ret != -1) return ret;
ret = iinf;
for(int i = 1; i < N; i++){
if(state & (1 << i)) continue;
if(dist[cur][i] == iinf) continue;
ret = min(ret, tsp(i, state | (1 << i), tsp) + dist[cur][i]);
}
return ret;
};
po(tsp(0, 1 << 0, tsp));
};Time
총평
문제를 좀 풀어야겠는데 시간 내기 힘들구만....