오-월은 푸-르구나-
우리들은 자란-다
오늘은 어린이날
우-리들 세상
https://codeforces.com/contest/1675
https://codeforces.com/contest/1675
codeforces.com
원래는 이왕 그린이 된 거 다음 주에 있는 Div.4를 참가해보려고 했는데 오늘 컨디션이 너무 좋았고 Div.3인 김에 오랜만에 참가했다.
최근에 B에서 막힌 적도 많고 가장 최근 Div.3에 안 좋은 기억이 있어서 긴장했는데 다행히 오른다!
A.
Div.3 A를 틀리는 사람이 있다...?
다급한 마음에 처음에 a랑 x, b랑 y 값을 반대로 비교했고 그 외에도 전반적으로 잘못 짰다.
ㅠㅠ
침착하자.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int a, b, c, x, y;
cin >> a >> b >> c >> x >> y;
x = max(0, x - a);
y = max(0, y - b);
if (x + y <= c) {
cout << "YES" << kEndl;
}
else {
cout << "NO" << kEndl;
}
}
}
B.
strictly increasing이 포인트다.
뒤에서부터 값을 확인하면서 바로 다음 값보다 작을 때까지 2로 나누면 된다.
만약 다음 값이 0이라면 0보다 작을 수는 없으니 이는 불가능한 경우다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int ans = 0;
for (int i = n - 2; i >= 0; --i) {
if (arr[i] < arr[i + 1]) {
continue;
}
if (arr[i + 1] == 0) {
ans = -1;
break;
}
while (arr[i] >= arr[i + 1]) {
arr[i] /= 2;
++ans;
}
}
cout << ans << kEndl;
}
}
C.
예전에 이런 종류의 사고력 문제 같은 걸 푼 기억 때문에 도둑이 무슨 심리로 어떻게 대답했을까가 신경 쓰여서 처음에 좀 헷갈렸다...
그럴 필요가 없다. 도둑은 아무렇게나 대답한다.
그냥 어떤 포인트를 잡고, 앞뒤의 0과 1의 개수를 확인해서 그 사람이 도둑이 될 수 있는지만 확인하면 된다.
만약 어떤 사람이 도둑이라면 그전에는 그림이 있고, 그 후에는 없을 것이다.
그러므로 그 전에 1이 없고, 그 후에 0이 없는 인덱스 개수가 답이다.
prefix sum을 이용하면 된다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
string s; cin >> s;
if (s.length() == 1) {
cout << 1 << kEndl;
continue;
}
int n = s.length();
vector<vector<int>> count(2, vector<int>(n));
for (int i = 0; i < n; ++i) {
if (s[i] != '?') {
++count[s[i] - '0'][i];
}
}
for (int i = 1; i < n; ++i) {
count[0][i] += count[0][i - 1];
}
for (int i = n - 2; i >= 0; --i) {
count[1][i] += count[1][i + 1];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if ((i == 0 || count[0][i - 1] == 0) && (i == n - 1 || count[1][i + 1] == 0)) {
++ans;
}
}
cout << ans << kEndl;
}
}
D.
우선 모든 path가 leaf node까지 도달할 때가 최선이므로 path 개수는 leaf node 개수다.
그리고 tree의 level이 낮은 노드부터 path를 시작하는 게 최선이다.
그래서 bfs로 각 노드의 level을 구하고, 각각에 대해 {level, node 번호} pair를 만들어서 min heap에 넣었다.
그리고 하나씩 pop하면서 이전에 방문하지 않았다면 그것을 시작으로 하는 path를 만드는 것을 반복한다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<vector<int>> tree(n + 1);
int root = -1;
for (int i = 1; i <= n; ++i) {
int parent; cin >> parent;
if (parent == i) {
root = i;
}
else {
tree[parent].push_back(i);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (tree[i].size() == 0) {
++ans;
}
}
cout << ans << kEndl;
queue<pair<int, int>> que;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
que.push({ 1, root });
pq.push({ 1, root });
while (!que.empty()) {
int level = que.front().first;
int cur = que.front().second;
que.pop();
for (const auto child : tree[cur]) {
que.push({ level + 1, child });
pq.push({ level + 1, child });
}
}
vector<bool> visited(n + 1, false);
vector<int> starting_index(n + 1);
while (!pq.empty()) {
int cur = pq.top().second;
pq.pop();
if (visited[cur]) {
continue;
}
vector<int> path;
while (1) {
visited[cur] = true;
path.push_back(cur);
if (starting_index[cur] == tree[cur].size()) {
break;
}
cur = tree[cur][starting_index[cur]++];
}
cout << path.size() << kEndl;
for (const auto& node : path) {
cout << node << ' ';
}
cout << kEndl;
}
cout << kEndl;
}
}
E.
처음에는 앞에서부터 1씩 감소시키는 게 무조건 이득인 줄 알았는데, 맨 마지막 예제를 보고 그렇지 않다는 걸 깨달았다...
문제 풀 때 내가 생각한 풀이가 맞는지 예제로 모두 체크해봐야 한다는 걸 아는데, 매번 마음이 조급해서 그걸 놓친다...
좀 ! 더 ! 천 ! 천 ! 히 ! 침 ! 착 ! 해 !
맨 마지막 예제인
4 19
ekyv
의 경우 k에 대해서 operation을 10번 수행하면 aayv를 얻을 수 있다.
그 후에 남은 operation을 모두 세 번째 값에 수행하면 된다.
이렇게 맨 처음에 어느 값에 operation을 수행할지를 정하고, 남은 operation은 앞에서부터 차례로 수행하면 되는데,
처음에 operation을 수행하는 값은, 그것에 수행했을 때 나타나는 결과가 가장 첫 번째 값에 수행했을 때보다 좋아야 한다.
그러려면
1. 값이 가장 첫 번째 값보다 크거나 같아야 한다. 그래야 그 operation이 진행됨에 따라 첫 번째 값도 바뀔 수 있다.
2. 그렇지만 가장 첫 번째 값에만 operation을 시행한 것만큼 가장 첫 번째 값이 좋게 바뀌어야 한다. 예를 들어 두 번째 예제인
4 5
fgde
의 경우, 처음부터 g에 operation을 수행하면 첫 번째와 두 번째 값을 동시에 바꾼다는 장점은 있지만, 그 결과 나타나는 bbbb는 첫 번째부터 시행했을 때 나타나는 agaa보다 결과가 좋지 않다.
맨 처음에, 첫 번째 값이 아닌 걸 바꿨을 때 이득이 나타나는 확실한 경우는, 그 값을 'a'까지 만들 수 있는 경우다.
세 번째 예제인
4 19
ekyv
처럼 말이다.
그러므로 처음부터 쭉 돌면서 그 알파벳이 'a'가 되는 데 필요한 operation이 k 이하인지 확인하고, 만약 그렇다면 그런 것 중에서 최댓값을 저장해두고, 만약 그렇지 않다면 앞에서부터 차례로 하나씩 줄여나가는 게 가장 이상적이기 때문에 더 이상 확인하지 않고 break 한다.
그렇게 맨 처음에 operation을 수행하는 지점을 구하고, 수행하고, 나머지는 앞에서부터 차례대로 수행하면 된다.
(많이 횡설수설한데 일단은 여기까지만 수정하고 그냥 올린다. 나중에 수정하고 올리려고 하면 잊어버리게 돼서)
int GetRoot(vector<int>& root, int i) {
if (root[i] == i) {
return i;
}
return root[i] = GetRoot(root, root[i]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n, k; cin >> n >> k;
string s; cin >> s;
vector<int> first_index_of_the_alphabet(26, -1);
vector<int> root(n, -1);
for (int i = 0; i < n; ++i) {
if (first_index_of_the_alphabet[s[i] - 'a'] == -1) {
first_index_of_the_alphabet[s[i] - 'a'] = i;
root[i] = i;
}
else {
root[i] = first_index_of_the_alphabet[s[i] - 'a'];
}
}
int possible_max = -1;
for (int i = 0; i < n; ++i) {
if (s[i] - 'a' <= k) {
possible_max = max(possible_max, s[i] - 'a');
}
else {
break;
}
}
if (possible_max != -1) {
for (int i = 0; i < n; ++i) {
if (s[i] - 'a' <= possible_max) {
s[i] = 'a';
root[i] = 0;
}
}
k -= possible_max;
}
for (int i = 0; i < n && k > 0; ++i) {
if (s[i] == 'a') {
continue;
}
s[i] = s[GetRoot(root, i)];
while (s[i] != 'a' && k > 0) {
first_index_of_the_alphabet[s[i] - 'a'] = -1;
--s[i];
--k;
root[i] = i;
if (first_index_of_the_alphabet[s[i] - 'a'] != -1) {
root[first_index_of_the_alphabet[s[i] - 'a']] = i;
}
first_index_of_the_alphabet[s[i] - 'a'] = i;
}
}
for (int i = 0; i < n; ++i) {
s[i] = s[GetRoot(root, i)];
}
cout << s << kEndl;
}
}
F.
아...
라이브 때 아쉽게 못 풀었다고 생각해서 계속 붙잡아봤는데
풀이가 잘못됐다.. 잘못됐다기보다는 많이 복잡하다.
내 코드를 어떻게든 살려보려고 했지만 gumgood님 코드 보고 감동받아버려서 더 이상 손대지 않기로 했다.