개요
E번이 거의 쉬운 C급으로 쉬운 이상한 라운드이다.
풀다가 대쉬보드에서 맞은 사람 수를 확인하지 않았다면 상당히 낭패를 볼 뻔 했다.
A번
A번 문제: 구현
$[s, e]$구간이 쿼리로 주어지는데, 여기서 $d$의 배수인 것 중 $[s, e]$에 포함되지 않는 최소값을 찾는 문제이다.
풀이 보기
두 가지 경우로 나누면 간단하다.
$d < s$인 경우 그냥 $d$ 자체가 답이다.
아닌 경우 $e < i \cdot d$ 중 가장 $i \cdot d$를 찾으면 된다.
소스코드 보기
#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...); }
// ....................................................... //
i64 s, e, x;
void input() {
cin >> s >> e >> x;
}
int solve() {
if(x < s) {
cout << x << ENDL;
return 0;
}
i64 d = e/x;
if(x*d <= e) {
cout << x*(d+1) << ENDL;
} else {
cout << x*d << ENDL;
}
return 0;
}
// ................. main .................. //
void execute() {
int TT; cin >> TT;
while(TT--)
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번 문제: 구현 그리디
아코디언은 [:||||:] 형태이다.
즉, [:과 :] 사이에 |이 0개 이상 들어가있는 구조이다.
문자열이 하나 주어지는데, 여기서 원하는 만큼 문자를 지울 때 만들 수 있는 아코디언의 최대 길이를 구하면 된다.
풀이 보기
B번 문제 치고 조금 생각을 해야 하고 구현도 고려해야 할 점이 많은 문제이다.
하지만 천천히 생각해보면, [, ]이 여러개 등장한다고 했을 때 가장 외곽의 [ ]를 남겨두는게 무조건 이득이라는 것을 알 수 있다.
::의 경우에도 위에서 구한 [ ]내에서 가장 외곽에 있는 것을 남겨두는게 무조건 이득이다.
이렇게 되면 구한 ::안에 있는 |의 개수를 세서 가장 긴 아코디언을 만들면 된다.
구현할 때 조심해야 할 점은 아코디언을 만들 수 없는 경우를 따로 처리해야 한다는 것이다.
소스코드 보기
#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 = 5e5+10;
string st;
void input() {
cin >> st;
}
int solve() {
int s = -1, e = -1;
FOR(i, 0, st.size()) {
if(s == -1 && st[i] == '[') s = i;
}
RFOR(i, st.size()-1, 0) {
if(e == -1 && st[i] == ']') e = i;
}
if(s == -1 || e == -1 || s >= e) {
cout << -1 << ENDL;
return 0;
}
int cnt = 0;
int ss = -1, ee = -1;
FOR(i, s, e+1) {
if(ss == -1 && st[i] == ':') ss = i;
}
RFOR(i, e, s) {
if(ee == -1 && st[i] == ':') ee = i;
}
if(ss == ee) {
cout << -1 << ENDL;
return 0;
}
int ans = 4;
FOR(i, ss, ee+1) {
if(st[i] == '|') ++ans;
}
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;
}
// ......................................... //
C번
C번 문제: 구현 그리디
$n$개의 $[s_i, e_i]$ 세그먼트가 주어지고, 우리는 이것들을 두 개의 비어있지 않은 그룹으로 분류해야 한다.
단, 서로 다른 그룹에 속한 두 세그먼트의 교차점이 없어야 한다.
풀이 보기
어떤 세그먼트 $a$와 겹쳐지는 세그먼트들의 집합을 $A$라고 할 때, $A$는 무조건 같은 그룹에 속해야 한다.
또한 $A$와 겹쳐지는 세그먼트 또한 $a$와 같은 그룹에 속해야 하고, 이것은 겹쳐지는 세그먼트가 없을 때까지 반복된다.
그 외의 세그먼트들은 같은 그룹에 속하든, 다른 그룹에 속하든 문제가 되지 않는다.
이것을 가장 쉽게 구현할 수 있는 방법은 구간을 $s_i$순으로 정렬 후 순서대로 순회하며 앞의 구간과 겹쳐지면 무조건 같은 그룹에, 겹쳐지지 않으면 다른 그룹에 넣는 것이다.
또한 두 그룹은 비어있지 않은 상태여야 하기 때문에 이것에 대한 처리도 해야하는 것에 주의해야 한다.
소스코드 보기
#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, RANGE = 2e5+10;
int n, ord[MAXN], ans[MAXN];
ii seg[MAXN];
vi g[2];
void input() {
cin >> n;
FOR(i, 0, n) cin >> seg[i].first >> seg[i].se;
}
int solve() {
FOR(i, 0, n) ord[i] = i;
sort(ord, ord + n, [](int u, int v) { return seg[u] < seg[v]; });
int me = -1;
FOR(i, 0, 2) g[i].clear();
int cur = 0;
FOR(j, 0, n) {
int i = ord[j];
if(me < seg[i].fi) {
cur ^= 1;
}
me = max(seg[i].se, me);
g[cur].pb(ord[j]);
ans[ord[j]] = cur;
}
if(g[0].size() && g[1].size()) {
FOR(i, 0, n) cout << ans[i]+1 << ' '; cout << ENDL;
} else {
cout << -1 << ENDL;
}
return 0;
}
// ................. main .................. //
void execute() {
int TT; cin >> TT;
while(TT--)
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;
}
// ......................................... //
후기
이번에도 문제를 잘못 읽어 무려 2번이나 삽질하고 시간도 많이 날려먹었다.
같은 그룹에 겹쳐지는 세그먼트가 들어가면 안 되는 건줄 알고 fenwick도 사용하며 열심히 구현했는데 너무 허무했다.
특히 예제가 잘못 읽은 문제나 원래 문제나 똑같은 출력이 나오기 때문에 잘못을 알기까지 꽤 많은 시간이 걸렸다.
매 코포 컨테스트마다 이런 실수가 나오는데 앞으로는 좀 더 문제를 자세히 읽어야겠다.
D번
D번 문제: Math GCD 트리 DP 소인수
어떻게 된게 D번이 E번보다 어렵다.
$n$개의 정점으로 이루어진 트리가 주어지고, 각 정점마다 $[1..2 \cdot 10^5]$의 가중치가 부여되어 있다.
$g(u, v)$는 $u$정점에서 $v$정점까지의 단순 경로에 있는 정점들의 gcd값을 의미한다.
$dist(u, v)$는 $u$정점에서 $v$정점까지의 단순 경로에 있는 정점들의 수를 의미한다.
이 때, $g(u, v) > 1$ 인 경로들 중 $dist(u, v)$의 최대값을 구해야 한다.
풀이 보기
여러 수의 gcd가 $2$이상이라는 소리는 그들의 공통된 소인수가 하나라도 존재한다는 것이다.
즉, 공통된 소인수가 단 하나라도 있는 경로 중 최장 경로의 길이를 구해야 한다..
일단 공통 소인수라는 조건 없이 최장 경로를 구하는 것은 간단한 Tree DP로 해결이 가능하다.
$dp[u] = max(path({sub}_u, u))$
DP값을 채울 때는 Bottom-Up 방식으로 $dp[u] = 1 + max(dp[{child}_u])$로 채워나가면 된다.
또한 실제 최장 경로를 구할 때는 모든 정점 $u$에서 $dp[{child}_u]$값 중 가장 큰 $2$개를 골라 더한 것들 중 최대값을 찾으면 된다.
(사실 DP까지도 필요 없지만, 다음 문제 해결을 위해 이렇게 적었다.)
하지만, 이 문제에서는 그런 경로 중 공통된 소인수가 단 하나라도 있어야하므로, DP를 살짝 재정의 해야할 것 같다.
$dp[u][x]$ = $path({sub}_u, u)$ 중 $x$를 공통 소인수로 하는 최대 길이
이렇게 하면 아까와 마찬가지로 Bottom-Up 방식으로 자식 정점들에 dp값을 미리 채워두고, 현재 $u$에서 $weight[u]$의 소인수 $x$들에 대해 $dp[u][x] = max(1 + dp[{child}_u][x])$로 dp값을 점점 채워나가면 된다.
실제 최장 경로를 구할 때에도 이전과 마찬가지로 구하면 된다.
그런데 이렇게 하면 각 정점마다 해당 소인수의 개수만큼 저장할 공간이 늘어나니까 MLE가 발생하지는 않을까?
$2 \cdot 10^5$이내의 수는 $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 = 510,510$이기 때문에 소인수가 최대 6개 밖에 없기 때문에 문제가 되지 않는다.
또한 $2 \cdot 10^5$개의 $2 \cdot 10^5$이내의 자연수를 빠르게 소인수분해를 할 수 있는 수단이 필요한데, 이것은 이전에 소개했던 오일러의 체를 활용하면 쉽게 구현할 수 있다.
마지막으로 $dp[u][x]$를 정직하게 배열로 구현해버리면 당연히 MLE가 발생하기 때문에, map으로 구현을 해줘야 한다.
소스코드 보기
#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 = 2e5+10, RANGE = 2e5+10;
int n, ar[MAXN], pn, spf[RANGE], pr[RANGE], par[MAXN], ans;
map<int, int> dp[MAXN];
vi g[MAXN], pf[RANGE];
void input() {
cin >> n;
FOR(i, 0, n) cin >> ar[i];
FOR(i, 0, n-1) {
int u, v; cin >> u >> v; --u, --v;
g[u].pb(v);
g[v].pb(u);
}
}
void eulerSieve() {
FOR(x, 2, RANGE) {
if(!spf[x]) spf[x] = pr[pn++] = x;
for(int j = 0; x*pr[j] < RANGE; ++j) {
spf[x*pr[j]] = pr[j];
if(x % pr[j] == 0) break;
}
}
FOR(i, 2, RANGE) {
int x = i;
while(spf[x]) {
int cur = spf[x];
pf[i].pb(cur);
while(x % cur == 0) x /= cur;
}
}
}
void f(int u) {
for(int v : g[u]) if(par[u] != v) par[v] = u, f(v);
for(int x : pf[ar[u]]) {
int fir = 0, sec = 0;
for(int v : g[u]) {
if(par[v] == u) {
sec = max(sec, dp[v][x]);
if(fir < sec) swap(fir, sec);;
}
}
dp[u][x] = 1+fir;
ans = max(ans, 1 + fir + sec);
}
}
int solve() {
eulerSieve();
memset(par, -1, sizeof(par));
par[0] = MAXN;
f(0);
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;
}
// ......................................... //
후기
C번에서 죽을 쒀서 쉬웠던 E번 솔브 속도가 느려졌다.
따라서 이대로 라운드가 끝나버리면 700등이 돼 버리는데, 만약 D번을 늦게라도 풀면 200~400등까지는 노려볼만 했다.
Tree DP문제라는 것을 감을 잡고 소인수를 이용하면 상태공간을 많이 줄일 수 있다는 것을 알고 열심히 구현했지만, 중간에 DP 업데이트를 실수해서 시간 내에 AC를 받지 못해 아쉬웠다.
계속 코드를 보면서 “맞는데 왜 틀렸지?”라고 생각했는데, 코포를 끝내고 샤워를 하던 도중에 DP값 업데이트와 ans값 업데이트는 따로 해줬어야 한다는 것을 알고 너무 아쉬웠다.
즉, 내가 처음에 짰던 코드는 아래와 같은데
...
ans = max(ans, dp[u][x] = 1 + fir + sec);
이렇게 해버리면 $dp[u][x]$는 “$u$를 지나고, 공통 소인수가 $x$인 경로의 최장길이”가 되어버린다.
따라서 아래와 같이 $u$에서는 아래 1개의 경로 값만을 받아와야만 했다.
...
dp[u][x] = 1+fir;
ans = max(ans, 1+fir+sec);
E번
E번 문제: 구현 그리디
쉬울 때의 C번과 비슷한 수준의 문제여서 당황스러웠던 문제이다.
지폐가 여러 장 주어지고, 모든 지폐가 지갑에 들어갈 수 있는지 구해야한다.
지폐와 지갑은 모두 직사각형 모양으로 가로, 세로 길이가 주어진다.
지폐는 지갑에 회전시켜서 넣을 수 있고, 겹쳐지는 부분이 있어도 상관 없다.
$5 \cdot 10^5$개의 쿼리가 주어지는데, 쿼리는 두 종류이다.
- $+\ x\ y$ : $x \times y$크기의 지폐를 추가한다.
- $?\ h\ w$ : $w \times h$크기의 지갑에 현재까지의 지폐가 모두 들어갈 수 있는지 출력한다.
풀이 보기
지폐를 회전시키지 않는다고 생각하면 단순히 현재까지의 지폐 중 $max(x_{i..n})$, $max(y_{i..n})$이 지갑에 들어가는지를 알아보면 된다.
하지만 회전시켜야 하는 경우를 고려해야 하는데, 이것은 지폐던 지갑이던 놓는 방향을 무조건 $w \leq h$인 방향으로 놓도록 강제하면 위와 같은 방법으로 해결 할 수 있다.
소스코드 보기
#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...); }
// ....................................................... //
int QQ;
void input() {
cin >> QQ;
}
int solve() {
int mx = 0, my = 0;
while(QQ--) {
char typ; cin >> typ;
if(typ == '+') {
int x, y; cin >> x >> y;
if(x > y) swap(x, y);
mx = max(x, mx), my = max(y, my);
} else {
int x, y; cin >> x >> y;
if(x > y) swap(x, y);
if(x >= mx && y >= my) cout << "YES" << ENDL;
else cout << "NO" << 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번에서 삽질하느라 이 문제를 읽는 시간이 느려졌지만, 문제가 너무 쉬워 6분만에 풀었다.
코드를 짜면서도 “정말 이게 답인가? 뭔가 함정이 있는게 아닌가?” 싶을 정도였다.
개인적으로 이렇게 난이도가 뒤죽박죽인 문제는 안 나왔으면 좋겠다.
F번
F번 문제: DP Convex Hull Trick
라운드가 끝나고 손도 대지 않았던 F번을 봤는데, “최대값을 최소화” 하라는 단서를 보고 Binary Search인줄 알았다.
그래서 탱크 크기가 $x$일 때 모든 트럭이 목적지에 도착할 수 있나? 라는 판단 함수만 만들어내면 답이 나오는데, 그 판단을 내가 생각한 것은 $O(n \cdot m)$에 내려버리기 때문에 TLE가 날 것 같았다.
더 좋은 방법이 생각나지 않아 아예 처음부터 다시 시작하여 탱크의 크기는 우리가 결정하지만, 각 트럭의 운행 구간 $[s, e]$와 연비 $c$, 충전 횟수 $r$은 탱크의 크기와 독립적으로 항상 고정 된다는 정보를 이용하기로 했다.
또한 트럭들은 항상 한 쪽 방향(index가 증가하는 방향)으로만 운행을 하고, 겹치는 운행구간이 많다는 점도 이용해볼만 했다.
그러나 여기서 발목을 잡는게 연비 $c$가 트럭마다 다르다는 것인데, 나는 애초에 탱크의 용량 $V$에 집중하지 않기로 했다.
그 대신, 트럭이 $[s, e]$를 이동 할 때 최대 $r$번 끊어서 이동할 수 있다는 점을 이용하고 싶었는데, 이것으로 dp 식을 만들 수 있을 것 같았다.
$dp[s][e][x] = [s..e]$구간을 총 $x$번 쪼개어 운행한다고 했을 때, 길이가 최대인 구간이 최소인 값
이것을 구해놓으면 각 트럭마다 $c_i \cdot dp[s_i][e_i][r_i+1]$이 필요한 최소 탱크 용량이므로 $V$는 이것들의 $max$값을 취하면 쉽게 구할 수 있을 것이다.
그러나 문제되는 점이 dp를 실제로 계산할 때인데,
$dp[s][e][x] = min(max(dp[s][j][x-1], dist[i..j]))\ \ \ \ for\ j = [s..e)$
이와 같이 점화식이 나온다.
그러나 점화식 자체에서 $O(n)$이 걸리므로, 총 시간복잡도는 $O(n^4)$가 돼 버린다.
한창 백준에서 USACO문제들을 풀 때 저런 점화식을 유도했는데 시간복잡도가 너무 큰 경우가 있었는데, 그 때 시간복잡도를 줄이는 트릭이 Convex Hull Trick이었다.
그러나 나는 아직 기하를 공부하지 않았고 Convex Hull이라는 단어만 나와도 치가 떨리는 수준이기 때문에 제대로 공부를 하지 않고 넘어갔었는데, 이번 문제도 혹시 그런가하고 살짝 튜토리얼에서 Convex를 검색해봤다.
역시나 Convex Hull Trick을 사용한 문제였고, 조만간 그것에 대해서 제대로 공부해야겠다는 생각이 들었다..
튜토리얼을 보니 이것 외에도 다른 방법이 있는 것 같았는데 설명이 제대로 나와있지 않아 그 방법에 대해서는 모르겠다. (아마 Binary Search를 사용한 방법인 것 같다.)
후기
처음 A, B번을 풀었을 때 스코어보드를 잠깐 봤는데 B번 구현이 약간 까다로운 탓인지 잠시나마 100등 안에 들었었다.
하지만 C번에서 삽질을 하며 시간을 날리고 D번을 결국 풀지 못한 결과 700등이 되고 말았다.
두 가지가 없이 순탄하게 풀었다면 100~200등은 노려볼만 했는데 아쉬웠다.
나중에 보니 F번도 도전해볼만 했는데..
물론 Convex Hull Trick은 원리도 이해하지 못하고 대충 다른 블로그에서 베껴왔겠지만 말이다.
