개요
전반적으로 난이도가 괜찮았다.
실수 몇 번만 아니었으면 더 좋았을 것 같다.
A번
A번 문제: 구현
현재 무게가 $w$인 눈덩이가 $h$ 높이의 비탈길에서 굴러떨어진다.
또한 비탈길 중간 $d_i$높이에서 $u_i$무게를 가진 돌 $2$개가 존재한다.
눈덩이는 매 높이마다 $1$의 높이만큼 떨어지는데, 그 때마다 떨어지기 이전 높이 $h$만큼 무게가 늘어난다.
그러다가 중간에 돌을 만나면, $d_i$만큼 눈덩이의 무게가 줄며, 만약 그 결과가 음수이면 눈덩이의 무게는 0에서부터 다시 불어나야 한다.
이 때 눈덩이의 최종 무게는?
풀이 보기
단순 구현문제이다.
위에서 서술한 그대로 구현하면 된다.
소스코드 보기
#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 w, h, h1, h2, d1, d2;
void input() {
cin >> w >> h >> d1 >> h1 >> d2 >> h2;
}
int solve() {
while(h) {
w += h;
if(h == h1) w = max(0, w-d1);
if(h == h2) w = max(0, w-d2);
--h;
}
cout << w << 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번 문제: 구현 그리디 Math
$n$개의 정사각형을 그리려고 한다.
이 때, 현재 그리려는 선분과 평행하면서 같은 $x$좌표 범위 혹은 같은 $y$좌표 범위에 있는 선분이 이미 그려져있다면 코스트 없이 선분을 그릴 수 있다.
또한 코스트가 필요할 경우는 직사각형의 한 변과 같은 길이의 선분을 그릴 때 $1$만큼 필요하다.
이 때 $n$개의 정사각형을 그리기 위해 필요한 최소 코스트는?
예를 들어 $2$개의 정사각형을 그릴 때는 아래와 같이 빨간색 선분 3개에 대해서만 코스트를 지불하면 된다.
풀이 보기
그리디하게 생각하면 $w \cdot h$ 범위 내에 정사각형을 채우는 경우는 $w+h$코스트만을 지불하면 된다.
즉, 가장 겉 선분의 코스트만을 지불하면 되는 것이다.
그렇다면 $n$개의 사각형을 $w \cdot h$범위 내에 채우는 가장 효율적인 방법은 무엇일까?
우리는 두 수를 곱할 때 수의 합이 같을 경우 최대한 비슷한 수를 곱하는 것이 가장 큰 값이 된다는 것을 알고 있다.
이것을 그대로 적용하면 $w=h$이거나 $w=h+1$인 경우에 같은 $w+h$를 갖는 경우 중 두 수의 곱이 가장 커지게 된다는 것을 알 수 있다.
따라서 $n \leq w \cdot h$인 $w$, $h$ 중 가장 작은 $w+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...); }
// ....................................................... //
i64 x;
void input() {
cin >> x;
}
int solve() {
i64 w = 1, h = 1;
while(w*h < x) {
++h;
if(w < h) swap(w, h);
}
cout << w+h << 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;
}
// ......................................... //
후기
처음에는 $n$의 두 약수 $a$, $b$ 중 $a + b$가 가장 작은 경우를 찾으면 되는줄 알고 한 번 틀렸다.
B번이라고 너무 생각없이 풀었는데, 이런 사소한 실수도 조심해야겠다.
C번
C번 문제: 구현 그리디
문자열이 하나 주어지고, 해당 문자열에는 특수 문자 두 가지가 들어가있다.
각 특수문자의 앞에는 무조건 일반 문자가 존재한다.
$?$ : 앞의 문자를 지우거나 남겨둘 수 있다.
$*$ : 앞의 문자를 지우거나 $0$번 이상 반복시킬 수 있다.
특수 문자 연산을 적절히 하여 길이가 $k$인 문자열로 만들 수 있을까?
만들 수 있는 경우 해당 문자열을 출력해야 한다.
풀이 보기
단순하게 생각하자.
결과 문자열이 어떻든 상관 없이 길이만 맞추면 된다.
일반문자의 수를 $n$, $?$의 수를 $a$, $*$의 수를 $b$이라고 할 때, 우리가 만들 수 있는 문자열의 길이의 범위는 어떻게 될까?
따라서 만들 문자열 $k$가 위의 범위에 들어가는 경우 결과를 출력하도록 구현만 하면 된다.
급하게 짜느라 구현이 좀 더러워졌는데, 조금만 고치면 더 깔끔하게 구현도 가능 할 것 같다.
소스코드 보기
#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...); }
// ....................................................... //
string s;
int n, k;
void input() {
cin >> s >> k;
n = s.size();
}
int solve() {
int ca = 0, sn = 0;
FOR(i, 0, n) {
if(s[i] == '?') ++ca;
if(s[i] == '*') ++sn;
}
n -= (ca+sn);
if(!(n-ca-sn <= k && (k <= n || sn))) { cout << "Impossible" << ENDL; return 0; }
int inc = 0, rem = 0;
if(k > n) inc = k-n;
if(k < n) rem = n-k;
debug(inc, rem);
string ans;
FOR(i, 0, s.size()) {
if(s[i] != '*' && s[i] != '?') ans.pb(s[i]);
else if(inc && s[i] == '*') { FOR(j, 0, inc) ans.pb(s[i-1]); inc = 0; }
else if(rem && (s[i] == '?' || s[i] == '*')) { ans.pop_back(); rem--; }
}
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번 문제: 트리 그리디
$n$개의 정점을 가진 트리가 있고, 각 정점에는 가중치 $a_i$가 부여 되어있다.
$s_u = sum(a_{u \in path(root, u)})$라고 정의된다.
트리에서 홀수 깊이($root$의 깊이 = 1) 정점의 $s_i$만을 알 수 있을 때 이런 경우가 가능한지, 가능한 경우 중 $a_i$의 합이 가장 작은 경우를 찾아야 한다.
풀이 보기
직관적으로 생각했을 때 최대한 트리의 상위 노드의 $a_i$를 크게 부여하는 것이 무조건 이득이라는 것을 알 수 있다.
따라서 $root$에서부터 Top-Down방식으로 $a_i$를 부여해나가면 된다.
이 때, 하위 노드에서 현재까지 $s_{par[u]}$가 어느만큼 채워졌는지에 대한 정보를 인자로 넘겨주면 편하다.
또한 현재 노드가 짝수 깊이의 노드여서 $s_u$가 특정되지 않았다면 $min(s_{v \in child[u]})$값을 채우도록 하면 된다.
불가능한지 여부는 상위 노드의 $s_u$가 하위 노드보다 작은 경우가 있는지에 대한 판단만 하면 된다.
소스코드 보기
#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;
const i64 INF = 0x3fffffffffffffff;
i64 n, ans, ar[MAXN], par[MAXN], ok;
vi g[MAXN];
void input() {
cin >> n;
FOR(i, 1, n) cin >> par[i], g[--par[i]].pb(i);
FOR(i, 0, n) cin >> ar[i];
}
void f(int u, i64 p) {
if(ar[u] != -1) {
if(ar[u] < p) {
ok = -1;
return;
} else {
ans += (ar[u]-p);
p = ar[u];
}
} else if(g[u].size()) {
i64 sel = INF;
for(int v : g[u]) sel = min(sel, ar[v]);
if(p > sel) {
ok = -1;
return;
}
ans += (sel-p);
p = sel;
}
for(int v : g[u]) f(v, p);
}
int solve() {
f(0, 0);
if(ok == -1) cout << -1 << ENDL;
else 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;
}
// ......................................... //
후기
정신줄을 놓고 코딩했는지, 별로 생각을 안 하다가 바로 코딩을 해서 그런지는 모르겠지만 첫 번째 구현 때 식수로 $s_u$가 특정되지 않았을 경우에 대한 처리를 하지 않아서 한 번 틀렸다.
또한 내가 문제를 풀 때는 짝수 노드들에만 $s_u$가 특정되지 않았다는 것을 미처 보지 못했는데, 이 정보를 활용하면 아주 깔끔하게 구현 할 수 있을 것이다.
E번
E번 문제: constructive algorithm 그리디 Math
$n \times m$의 $A, G, C, T$로 이루어진 맵이 주어진다.
이 맵의 각 셀의 원소를 적절히 바꾸어 모든 $2 \times 2$의 부분 맵에 대하여 각 셀이 서로 다른 원소를 가지도록 만들 때, 최소 변경 수를 구하면 된다.
나는 이 문제가 DP인줄알고 열심히 점화식을 세웠지만, 결국 풀지는 못했다.
튜토리얼을 보니 한 줄(row, col)에 최대 2개의 문자만이 들어가도록 맵을 바꾸는게 무조건 이득이라고 한다.
즉, 다음과 같은 형태인 경우 중 하나가 무조건 최적이라는 뜻이다.
AGAGAGAG
CTCTCTCT
...
왜 이렇게 되는지는 튜토리얼 페이지가 없다고 설명을 안 해줬다..;
개인적으로는 DP로도 해결 할 수 있을 것 같은데, 조금 더 생각을 해봐야겠다.
후기
B, D를 실수한 것 빼고는 딱히 감흥이 없는 라운드였다.
D번도 너무 전형적인 트리 문제라 식상했던 것 같다.
E번을 DP로 풀지 못한게 약간 아쉽다.
