개요
이번 코포는 시작하기 전 부터 서버가 불안불안 하더니만 결국 채점 큐에 들어간 문제가 40분 가까이 채점되지 않아 Unrated가 돼 버리고 말았다..;
문제 자체들은 쉬운 편이었고, F번 또한 오래 생각해보면 풀릴 것 같았지만, Unrated 라는 소식에 도전은 안 해봤다.
A번
A번 문제: 구현
언제나 그렇듯 A, B번 문제는 풀만하다.
단순한 구현 문제로, .과 X로 이루어진 맵이 주어지는데, 여기서 다음과 같은 형태가 몇 번이나 나오는지 구하는 문제이다.
X.X
.X.
X.X
풀이 보기
흔하게 나오는 맵에서의 상하좌우 4방향 방문과 같이 dy, dx를 정의해놓고 구현을 하면 편하다.
단, 이 문제의 경우에는 모양이 다르기 때문에 dy = { -1, -1, 1, 1 }, dx = { -1, 1, -1, 1 }로 정의하면 된다.
그러고 난 후 X가 등장하는 곳마다 4방향 모두가 X이면 카운트를 해가면 된다.
시간복잡도: $O(n^2)$
소스코드 보기
include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 500;
const int dy[4] = { -1, -1, 1, 1 }, dx[4] = { -1, 1, -1, 1 };
int n;
string g[MAXN];
void input() {
cin >> n;
FOR(i, 0, n) cin >> g[i];
}
int solve() {
int cc = 0;
FOR(i, 0, n) {
FOR(j, 0, n) {
if(g[i][j] == 'X') {
bool ok = true;
FOR(dir, 0, 4) {
int y = i + dy[dir], x = j + dx[dir];
if(!(0 <= y && y < n && 0 <= x && x < n && g[y][x] == 'X')) { ok = false; break; }
}
if(ok) ++cc;
}
}
}
cout << cc << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
B번
B번 문제: 구현 map
문제가 장황하게 길어 해석하는게 문제인 문제이다.
게다가 자세하게 읽지 않으면 지나칠 수 있는 문장도 있으니 주의해야 한다.
레스토랑이 있는데, 거기에는 $n$종류의 음식이 있고 $m$명의 손님이 음식을 먹으려고 일렬로 대기중이다.
음식은 각각 $a_{1..n}$개 만큼 있고, $c_{1..n}$원의 가격에 판매하고 있다.
손님들은 온 순서대로 차례로 음식을 먹는데, 다음 과정에 따라 음식을 가져가게 된다.
현재 손님 $i$는 처음으로 먹을 음식 $t_i$와 먹을 음식들의 개수 $d_i$ 정보를 가지고 있다.
이 손님이 현재 먹을 음식이 $j$라고 할 때 다음의 과정에 따라 총 $d_i$개의 음식을 먹으려고 한다.
- 음식 $j$가 남아있는 경우 해당 음식을 먹는다.
- 음식 $j$가 남아있지 않은 경우, 남아있는 음식들 중 가장 싼 음식을 고르고, 가격이 같은 것이 있을 경우 index가 가장 작은 것을 고른다.
- 손님이 $d_i$개의 음식을 다 먹지 못했는데 모든 음식이 다 떨어졌을 경우, 손님은 화가 나기 때문에 해당 손님에게서는 돈을 아예 받을 수 없다 (0원)
위 과정을 반복할 때 각 손님에게서 얼마의 돈을 받을 수 있을지 계산하는 문제이다.
풀이 보기
고려해야 할 것이 조금 있는 구현문제이다.
음식 $j$를 다 먹은 뒤 2번 조건에 맞는 다음 음식을 빠르게 구하는 것이 문제인데, 이것은 map<ii, int>를 사용하면 key값에 따라 정렬된 결과가 유지되기 때문에 쉽게 해결할 수 있다.
여기서 map에는 mp[{cost, index}] = remain과 같은 정보를 저장하면 된다.
또 한가지 주의해야 할 점은 3번 조건에서 해당 손님이 음식을 먹기는 먹었지만 원하는 만큼 못 먹어 돈을 못 받는 경우에 대한 예외처리를 해야한다는 것이다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1e5;
int n, q, r[MAXN], c[MAXN];
map<ii, int> mp;
void input() {
cin >> n >> q;
FOR(i, 0, n) cin >> r[i];
FOR(i, 0, n) cin >> c[i], mp[{c[i], i}] = r[i];
}
int useitem(int idx, int val) {
int us = min(val, r[idx]);
r[idx] -= us;
if(r[idx] == 0) mp.erase({ c[idx], idx });
else mp[{c[idx], idx}] -= us;
return us;
}
int solve() {
while(q--) {
int cur, rem;
cin >> cur >> rem;
--cur;
i64 tot = 0;
while(rem) {
int us = useitem(cur, rem);
rem = rem - us;
tot += 1ll * us * c[cur];
if(mp.size()) {
cur = mp.begin()->first.second;
} else if(rem != 0) {
tot = 0;
break;
}
}
cout << tot << ENDL;
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
C번
C번 문제: 그리디 math
짝수 개의 원소를 가진 배열이 주어지는데, 이 배열에서 원소들을 2개 이상의 원소를 가진 그룹들로 그루핑해서 각 그룹 원소의 합의 제곱의 합이 가장 작아지는 경우를 찾는 문제이다.
즉, $m$개의 그룹으로 그루핑을 했다고 가정하고, 그룹 $j$의 원소 합을 $s_j$라고 할 때 다음을 최소화 하면 된다.
풀이 보기
우선 다음을 생각해보자.
$a$, $b$, $c$ 세 개의 양의 정수가 있는데 $a^2 + b^2 + c^2$이 더 작을까 아니면 $(a+b)^2 + c^2$이 더 작을까?
당연하게도 식을 전개해보면 전자가 작을 수 밖에 없다는 것을 알 수 있다.
이것을 통해 우리는 최대한 그룹의 크기를 작게 해서 그루핑 하는게 무조건 이득이라는 것을 알 수 있다.
이 문제에서는 각 그룹의 원소의 수가 최소 2개는 되어야 하고, 배열의 원소는 짝수개이니까 무조건 2개씩 그루핑을 하면 된다.
그렇다면 어떤 수끼리 짝을 지어줘야 할까?
$(a + b)^2 = a^2 + b^2 + 2ab$ 이므로, $a^2 + b^2$부분은 어떻게 짝을 짓던 결국 최종 합은 똑같은 값이 나올 것이고 문제는 $ab$의 값을 최소화 하는 것이다.
간단하게 생각해보면 배열에서 남은 수들 중 가장 작은 수와 가장 큰 수를 매칭해나가는 것을 반복하면 그것이 최소값이라는 것을 알 수 있다.
정확한 증명은 $a < b < c < d$ 네 수가 있는데 $a \cdot d + b \cdot c > a \cdot b + c \cdot d$ 혹은 $a \cdot d + b \cdot c > a \cdot c + b \cdot d$ 인 경우가 있을까에 대해 생각해보면 된다.
소스코드 보기
생각 없이 multiset을 써버렸는데, 사실 그냥 sort해서 푸는게 편하다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 3e5;
int n, ar[MAXN];
multiset<int> ms;
void input() {
cin >> n;
FOR(i, 0, n) cin >> ar[i];
}
int solve() {
FOR(i, 0, n) ms.insert(ar[i]);
i64 ans = 0;
FOR(i, 0, n/2) {
int ss = (*ms.begin()) + (*(--ms.end()));
debug(ss);
ms.erase(ms.begin());
ms.erase(--ms.end());
ans += 1ll * ss * ss;
}
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
D번
D번 문제: 그래프 MST
정점이 $10^5$개 정도 되는 연결 무향 그래프가 주어지고, 각 정점은 $1..n$의 index를 가지고 있다.
이 때, 1번 정점에서 출발하여 그래프의 모든 정점들을 방문할 때, 새로 방문한 정점들의 수열이 사전순으로 가장 앞서는 경우를 찾는 문제이다.
즉, 방문했던 정점을 또 방문할 수 있고, 새로운 정점을 만날 때만 수열에 기록할 때 사전순으로 가장 작은 수열을 찾는 것이다.
풀이 보기
Prim MST문제라는 것을 빨리 알아차리는게 중요한데, 방문의 형태가 “지금까지 방문한 정점들 (연결된 트리)”에 연결된 정점들 중 index가 가장 작은 것을 찾아 해당 정점을 트리에 넣는 식이라는 것을 보면 MST 문제라는 것을 쉽게 알 수 있다.
prim과 비슷한 형태로 구현하면 된다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 1e5+10;
int n, m, vis[MAXN];
vi g[MAXN];
set<int> rem;
void input() {
cin >> n >> m;
while(m--) {
int u, v; cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
}
int solve() {
rem.insert(1);
while(rem.size()) {
int u = *rem.begin();
rem.erase(u);
vis[u] = 1;
cout << u << ' ';
for(int v : g[u]) {
if(!vis[v]) rem.insert(v);
}
}
cout << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
후기
처음에는 별 생각 없이 일반적으로 dfs하며 현재 정점에 연결된 새로운 정점 중 index가 가장 작은 것으로 가보는 방식으로 구현했는데, 나중에 보니 3-1-2-4의 경우 예외가 있다는걸 알았다.
사실 제출 할 때부터 뭔가 예외가 있을 것 같은 불안감이 있었지만 무시하고 제출했었는데, 이 덕분에 틀린 패널티 + 채점 될 때까지의 시간 40분 패널티를 받아버려 등수가 많이 내려갔다..
틀린걸 알고 AC를 받을 때까지 시간은 별로 안 걸렸지만 여러모로 아쉬운 문제였다.
E번
E번 문제: DP multiset
$[1..n]$의 각 좌표가 정수화 된 시간 속에서 주어진 루틴에 따라 $k$개의 동전을 주워가는데, 최대 $m$번의 방해를 할 수 있을 때 최적으로 방해할 경우 얻을 수 있는 최소 동전 가치를 구하는 문제이다.
각 동전 $i$는 주울 수 있는 시간의 구간 $[s_i..e_i]$이 존재하고, 이 동전을 주울 경우 $d_i$까지는 아무런 행동도 하지 못하며, $c_i$의 가치를 가지고 있다.
동전을 주울 때는 현재 주울 수 있는 동전 중 다음과 같은 우선순위에 따라 줍게 된다.
- 동전의 가치 c_i가 큰 순으로 줍는다.
- c_i가 같을 경우 d_i가 큰 순으로 줍는다.
- 나머지 경우는 랜던하게 줍는다.
이 때 방해라는 개념은 현재 시간 $t$에 방해를 할 경우 $t$에는 아무런 행동도 하지 못하며 $[t+1..]$에서부터 행동을 할 수 있다.
또한 $e_i \leq d_i$라는 조건이 항상 성립한다.
풀이 보기
먼저 인지해야 할 점은, 시간의 범위가 $[1..10^5]$이고, 방해 횟수도 $[1..200]$으로 상당히 작다는 것이다.
이것만 봐서는 DP의 냄새가 나는데, 좀 더 생각해봐야 한다.
만약 DP로 해결할 경우 상태공간은 어떻게 되는걸까?
현재 시간 $t$와 현재까지 방해한 횟수 $m$에 대한 정보는 당연히 필요할 것이다.
하지만, 이전 시간에 방해를 어떻게 했느냐에 따라서 현재 주울 수 있는 동전들이 달라질텐데 이 정보를 모두 상태공간에 넣어버리면 $2^{200}$이 되어버리는데 과연 이 정보가 필요할까?
조금만 생각해보면 아니라는 것을 알 수 있다.
각 시간 $t$에서 주울 수 있는 동전들은 현재 방해 횟수 $m$이나 이전 방해 정보에 영향을 받지 않는다!
$s_i \leq t \leq e_i$인 동전들은 무조건 $t$ 시간에 주울 수 있다.
이것이 가능한 이유는, 만약 동전 $i$를 줍는 행동을 할 경우 다음 행동 할 수 있는 시간은 $d_i+1$부터일 것이며, $e_i \leq d_i$라는 조건 덕분에 $e_j$가 $d_i$보다 작은 동전들 $j$는 어차피 $[d_i+1..]$부터는 줍지 못할 것이다.
또한 주울 수 있는 동전이 있는데 줍지 않는 경우는 방해를 받았을 때 뿐인데, 그 경우는 단순히 $t$가 $t+1$이 될 뿐이므로 주울 수 있는 동전에 대한 정보는 변하지 않는다.
이것을 이용해 DP식을 세우면 현재 시간을 $t$, 현재 사용한 방해 횟수를 $m$이라 할 때
현재 주울 수 있는 동전이 없을 때
방해를 할 때
방해하지 않고 동전을 주울 때 ($i$ = 현재 주울 동전)
현재 $t$에서 주울 수 있는 동전은 multiset을 통해 구현하면 편하다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const i64 INF = 0x3fffffffffffffff;
const int MAXN = 1e5+10, MAXM = 2e2+10;
int n, m, k;
i64 dp[MAXN][MAXM]; // dp[시간][방해수]
vii str[MAXN], fin[MAXN]; // edg[s] = e, cost, d;
multiset<ii> ms;
void input() {
cin >> n >> m >> k;
FOR(i, 0, k) {
int s, e, d, c; cin >> s >> e >> d >> c; ++d;
str[s].pb({ -c, -d });
fin[e+1].pb({ -c, -d });
}
}
int solve() {
FOR(i, 0, MAXN) FOR(j, 0, m+1) dp[i][j] = INF;
dp[0][0] = 0;
FOR(t, 0, n+1) {
for(ii e : str[t]) ms.insert(e);
for(ii e : fin[t]) ms.erase(ms.find(e));
FOR(us, 0, m+1) {
if(ms.size()) {
// 방해 없이 가보기
ii sel = *ms.begin();
dp[-sel.se][us] = min(dp[-sel.se][us], dp[t][us] + ((i64)-sel.fi));
// 방해 하고 가보기
if(us < m) dp[t+1][us+1] = min(dp[t+1][us+1], dp[t][us]);
} else dp[t+1][us] = min(dp[t+1][us], dp[t][us]);// 아예 먹을게 없어 방해 생각x
}
}
i64 ans = INF;
FOR(i, 0, m+1) {
ans = min(ans, dp[n+1][i]);
}
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
후기
분명 DP식도 잘 세웠고, 범위에 대한 실수도 없었는데 WA가 뜨길래 상당히 당황스러웠다.
아무리 봐도 맞왜틀이어서 혹시나 multiset의 erase에 문제가 있나 찾아봤더니 erase(x);가 원소 하나만을 지우는 것이 아닌 해당되는 모든 원소를 지우는 것이었다.
erase(multi_set.find(x));로 바꾸었더니 AC가 뜨긴 떴는데 앞으로 multiset을 쓸 때는 조심해야 할 것 같다.
나와 같은 실수를 한 사람들이 꽤 있었다.
후기
D에서 한 번 삽질으로 40분 패널티 받은게 너무 억울했다.
E번이야 내가 multiset에 대해서 잘 몰라서 시간을 많이 낭비했지만, D번은 순수히 채점 큐가 제대로 돌아가지 않아서 시간을 날린 것이니…
하지만 무엇보다 억울한 것은 이번에는 꽤나 문제를 잘 풀었는데 Unrated가 된 것이다.
코포 결과
