AtCoder Beginner Contest 216 A부터 E까지 업솔빙
falconlee236
·2022. 2. 14. 23:47
AtCoder Beginner Contest 216 A부터 E까지 업솔빙
생각보다 C번에서 헤맸는데, 이 문제를 조금 더 빨리 풀었다면 더 높은 등수가 나왔을걸이라는 생각이 계속 난다. D번하고 E번은 문제를 보고 깔끔히 포기했다. E번은 솔직히 조금 냄새가 나긴 했는데, 이분탐색이라는 것은 전혀 생각 못했다. 도대체 어떤 문제를 이분 탐색으로 풀어야 하는거야? 이분탐색이라는 것을 알아도, 숫자가 조금만 달라도 값이 완전히 달라지기 때문에 이것도 어렵다. D번은 그냥 큐 시물레이션 문제였는데, 생각보다 메모리 제한이 널널해서 내가 생각한대로 그대로 풀었으면 손쉽게 풀었을 것 같다는 느낌이 들었다. 메모리제한 신경 안쓰고 일단 풀어볼걸 이라는 생각을 했다. 이번 대회에서 유난히 lambda를 자주 사용하는데, 이 대회 업솔빙 하면서 c++의 lambda함수를 좀 더 잘 알게 됐다.
이번 대회에서 배운 것은
- 이분탐색 응용 문제
- 시뮬레이션 문제 유형
- c++ lambda함수
- 두 수사이의 합계 공식 By 가우스
문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.
A - Signed Difficulty (*17)
접기/펼치기
문제 설명
$Y$가 한자리 수인 실수 $X.Y$가 주어진다.
다음 조건에 맞춰 출력하라.
* $X-$, $(0 \le Y \le 2)$
* $X$, $(3 \le Y \le 6)$
* $X+$, $(7 \le Y \le 9)$
문제 해설
c++의 substring 함수를 아는지 묻는 문제였다. 문자열의 맨 뒤 index를 구할때 c++에서는 s.size() - 1을 사용한다는 것을 알아두자. 참고로 s.size() - 1을 이용해서 얻은 값은 char이기 때문에 정수로 비교하기 위해서 '0'문자를 빼야한다는 것을 잊지말자.
정답 코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
string s; cin >> s;
int len = s.size();
string sub = s.substr(0, len - 2);
cout << sub;
if(s[len - 1] - '0' <= 2) cout << "-";
else if(s[len - 1] - '0' >= 7) cout << "+";
return 0;
}B - Same Name (*38)
접기/펼치기
문제 설명
사람 $N$명이 있다. $i$번째 사람 $(1 \le i \le N)$의 성씨와 이름은 각각 $S_i, T_i$이다.
이 사람들중에서 성씨와 이름이 서로 같은 사람 한쌍이 있는지 확인하라. 다시말하면 $1 \le i < j \le N$ 일때, $S_i = S_j, T_i = T_j$ 를 만족하는 정수 쌍 $(i, j)$가 있는지 확인하라.
문제 해설
완전탐색 문제, $N$의 제한이 1000이므로 그냥 $O(N^2)$ for문 2개 쓰면 된다.
정답 코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n;
string a[n][2];
for(int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1];
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(a[i][0] == a[j][0] && a[i][1] == a[j][1]){
cout << "Yes";
return 0;
}
}
}
cout << "No";
return 0;
}C - Many Balls (*145)
접기/펼치기
문제 설명
빈 상자를 가지고 있다.
지수는 다음 두 문자를 원하는 순서대로 몇번이고 부를 수 있다.
* $A$: 상자에 새로운 공을 넣는다.
* $B$: 상자에 있는 공의 수를 두배로 한다.
최대 $120$ 문자까지 사용해서 상자에 정확히 $N$개 공이 들어있게 만들어야 한다.
공이 $N$개만 있다면 문자의 순서는 전혀 상관이 없다.
문제 해설
처음에는 0부터 순서대로 문제를 풀려고 했는데 너무 예외 상황도 많아서 그냥 반대로 풀기로 했다. 내가 이 문제를 푸는 방법은 다음과 같다.
$N$부터 시작하며
* 이 수가 짝수이면: 2로 나누고 $B$를 저장
* 이 수가 홀수라면: 1을 빼고 $A$를 저장
이 과정을 반복하고 맨 마지막에 문자열을 뒤집으면 된다.
아니면 문자를 계속 앞에다 추가하는 방식으로 해도 된다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long n; cin >> n;
string s;
while(n > 0){
if(n & 1LL) s = 'A' + s, n--;
else s = 'B' + s, n >>= 1;
}
cout << s;
return 0;
}D - Pair of Balls (*1039)
접기/펼치기
문제 설명
$2N$개 공이 있다. 각 공은 $1$부터 $N$ 사이에 있는 숫자로 표현되는 색깔로 이루어져 있다. $N$개 색깔에 대해서 한 색깔에는 정확히 $2$개 공이 있다.
이 공들은 $M$개 지면과 수직으로 있는 실린더에 담겨있다. 처음에 $i$번째 실린더 $(1 \le i \le M)$은 $k_i$개 공이 있고, $i$번째 실린더의 맨 위 부터 $j$번째 공은 색깔 $a_{i, j}$을 가지고 있다.
우리의 목표는 다음 연산을 반복해서 모든 $M$개 실린더에 있는 공을 없애는 것이다.
* 비어있지 않은 두 실린더를 선택하고 각 실린더의 맨위에 있는 공 1개를 제거한다. 이때 이 두 공은 서로 같은 색깔이어야 한다.
이 목표가 달성될 수 있는지 결정해야 한다.
문제 해설
시뮬레이션 문제이다. 문제에서 하라는대로 그대로 하면 된다. 일단 필요한것은 $M$개 실린더를 담을 수 있는 공간이다. 이것은 문제를 보니까 먼저 들어간 공이 제일 먼저 나와야 하기 때문에 queue를 $M$개 선언하면 될 것이다.
이제는 모든 공은 $N$개 각 색깔당 2개씩 있다고 했기 때문에 맨 위에 한 색깔의 공이 2개 있다면 그 아래에 있는 모든 실린더에는 그 색깔이 없다. 따라서 맨 위에 있는 공의 색깔을 담는 배열을 만들고, $i$번째 색깔을 의미하는 배열에 원소가 2개 있다면, 즉 2개 실린더에 그 공이 존재하다면 그 공은 제거할 수 있다는 뜻이다.
맨 위에 있는 공을 제거했다면 이제 다음 제거해야할 공은 어떻게 정할까? 이 공을 정하기 위해서 다시 색깔 배열을 $1$부터 $N$까지 모두 순회해서 찾아야 할까? 이런 행위는 무조건 시간초과를 부르는 작업이다.
나는 이 작업을 수월하게 하기 위해서 큐 자료구조를 하나 더 사용했다. $M$개 실린더에 꼭 색깔이 같은 공의 쌍이 1개만 있다는 보장이 없기 때문에 색깔이 같은 공의 색깔을 큐에 모두 담는다. 그리고 한 색깔의 공이 모두 빠졌다면 맨 위에 있는 공이 바뀔 것이고, 그 공의 실린더 INDEX를 모두 기록한 다음 그때 또 그 색깔의 공이 2개 있다면 그 색깔을 다시 큐에 넣는 작업을 계속 반복한다면 훨씬 적은 시간복잡도로 이 문제를 해결할 수 있다. 즉 이 큐에는 맨 위에 같은 색깔의 공이 2개 있는 색깔을 저장하는 자료구조라고 생각 하면 된다. 이 색깔을 골랐을 때 색깔배열에는 해당 색깔의 공이 맨 위에 있는 실린더의 INDEX가 2개 저장되어 있다.
만약 큐에 있는 모든 원소를 다 뽑았는데, 비지 않은 실린더가 하나라도 있다면 그 길로 NO를 출력하면 된다. 모든 실린더가 다 비어있다면 YES를 출력, all_of함수를 이용했다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
queue<int> cli[m];
vector<int> cnt[n];
for(int i = 0; i < m; i++){
int k; cin >> k;
while(k--){
int num; cin >> num;
cli[i].push(num - 1);
}
cnt[cli[i].front()].push_back(i);
}
queue<int> q;
for(int i = 0; i < n; i++){
if(cnt[i].size() == 2) q.push(i);
}
while(q.size()){
int top = q.front(); q.pop();
for(auto x : cnt[top]){
cli[x].pop();
if(cli[x].empty()) continue;
int idx = cli[x].front();
cnt[idx].push_back(x);
if(cnt[idx].size() == 2) q.push(idx);
}
}
if(all_of(cli, cli + m, [](auto& x){return x.empty();})) cout << "Yes";
else cout << "No";
return 0;
}E - Amusement Park (*1084)
접기/펼치기
문제 설명
지수는 놀이공원에 왔다.
공원은 $N$개 놀이기구가 있고, $i$번째 놀이기구의 재미는 처음에 $a_i$이다.
지수가 $i$번째 놀이기구를 탈때 다음 순서대로 일이 발생한다.
* 지수의 만족도가 헌재 $i$번째 놀이기구의 재미만큼 상승한다.
* 그리고 $i$번째 놀이기구의 재미는 $1$ 감소한다.
지수의 만족도는 처음에 $0$이다. 지수는 놀이기구를 순서에 상관없이 최대 $K$번 탈 수 있다.
놀이기구를 최대로 탔을 때 지수가 얻을 수 있는 최대 만족도는 얼마일까?
문제 해설
이분 탐색 문제였다. 핵심은 놀이기구를 최대 $K$번 탈 수 있다는 것에 있다. 놀이기구들 중 최대 재미값을 $A$라고 하면 놀이기구의 재미를 $M$까지 줄였다면 총 $A - M$번 놀이기구를 탄 것이 되고, $M + 1$ 부터 $A$까지 재미의 합이 그 만족도가 된다. 이 관찰이 이 문제를 푸는 전부이다.
이제 우리가 할 것은 이 $M$값을 찾는 것이다. 각 놀이기구의 재미 - $M$값이 1보다 작다면 그 놀이기구는 탈 필요가 없기 때문에 0을, 놀이기구의 재미 - $M$값이 0보다 크다면 그 차이만큼 놀이기구를 탈 수 있다는 뜻이다. 모든 놀이기구에 각 놀이기구의 재미 - $M$값의 합은 결국 전체 놀이기구를 탈 수 있는 횟수가 될 것이고 이 값이 최대 $K$를 만들 수 있게 하는 $M$값을 이분탐색으로 찾으면 된다. 전체 놀이기구를 탈 수 있는 횟수는 f 익명 함수로 만들었다. 이때 $a$ 배열 값을 사용해야 하기 때문에 [&a]로 a배열만 capture했다. 자세한 내용은 구글에서.
최솟값을 -1로 둔 이유는 $M$값이 $0$이 될수도 있기 때문이다. 잊지말자. $M$값이 총 놀이기구를 탄 횟수가 아닌 각 놀이기구 재미 - $M$값의 총 합이 총 놀이기구를 탄 횟수라는 것을. 이분탐색을 할때 원하는 값을 찾고 싶다면 오른쪽 값을 사용하면 된다. 왜냐하면 조건을 만족할 때 마다 오른쪽의 값을 MID값으로 해서 탐색 범위를 절반으로 줄이기 때문이다.
이렇게 찾은 $M$값을 사용해서 이제는 총 만족도를 구해야 한다. 두 수 $A$와 $B$가 있고 $(A \le B)$ 일때 두 정수 사이의 모든 합을 구하는 공식은 다음과 같다. $(A + B) * (B - A + 1) / 2$이다. $A + B$가 $(B - A + 1)$개 있고, 전체 더한 값을 2로 나눈다는 뜻이다.
간단하게 증명하면 $3$과 $5$ 사이에 잇는 모든 수를 더한 값을 구하고 싶다.
$S = 3 + 4 + 5$라고 하자. 그러면 $2S = 3 + 4 + 5 + 5 + 4 + 3$이라고 할 수 있고, $3 + 5$가 3개 있다고 할 수 있다. 그러면 $2S = (3 + 5) * (5 - 3 + 1)$이고 $S = (3 + 5) * (5 - 3 + 1) / 2$이다.
앞에서 구한 $M$에 대해서 각 놀이기구의 재미 - $M$ 값이 $0$보다 작거나 같다면 그 놀이기구는 못탄다는 것이므로 계산에 반영하지 않는다. 저 값이 $1$보다 클때만 만족도를 위에 있는 공식으로 계산해서 더한다. 그리고 그만큼 놀이기구를 탄 것이므로 $k$에서 차이값을 뺀다. 이때 주의해야 할 점은 구한 $M$값을 이용해서 재미 - $M$을 해서 나온 값은 각 놀이기구의 재미를 포함해서 탄 횟수를 센다는 점이다. 만약 $M = 4$이고 한 놀이기구의 재미가 $8$이라고 하자. 그러면 총 4번 놀이기구를 탄건데 $8$부터 4번을 탄거니 $8 + 7 + 6 + 5$를 해야하므로 $4$ 부터 $8$까지 합이 아닌, $4 + 1$부터 $8$까지 합을 구해야 한다.
그리고 마지막으로 $K$가 남아있을 수 있다. 그렇다면 남아있는 $M$값을 가진 놀이기구를 $K$번 타면 최적의 해가 되기 때문에 $M * K$를 마지막 답에 추가한다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> k;
ll a[n];
for(auto& x : a) cin >> x;
auto f = [&a](ll num){
ll res = 0;
for(auto x : a) res += max(0LL, x - num);
return res;
};
ll no = -1, ok = 2e9;
while(no + 1 < ok){
ll mid = (no + ok) / 2;
if(f(mid) <= k) ok = mid;
else no = mid;
}
auto ari = [](ll a, ll b){
return (a + b) * (b - a + 1) >> 1;
};
ll ans = 0;
for(auto x : a){
ll d = x - ok;
if(d <= 0) continue;
ans += ari(ok + 1, x);
k -= d;
}
ans += k * ok;
cout << ans;
return 0;
}'알고리즘 > atcoder' 카테고리의 다른 글
| AtCoder Beginner Contest 218 A부터 E까지 업솔빙 (0) | 2022.03.15 |
|---|---|
| AtCoder Beginner Contest 217 A부터 E까지 업솔빙 (0) | 2022.03.08 |
| AtCoder Beginner Contest 215 A부터 D까지 업솔빙 (0) | 2022.02.10 |
| AtCoder Beginner Contest 214 A부터 D까지 업솔빙 (0) | 2022.01.29 |
| AtCoder Beginner Contest 213 A부터 E까지 업솔빙 (0) | 2022.01.22 |
