(2021년 1월 14일에 작성한 글입니다.)
Standings - Codeforces Round #552 (Div. 3) - Codeforces
codeforces.com
200108에 #695를 하고 충격을 받은 채로 있다가
한 시간 뒤인 2:30부터 4:30까지 했다.
A.
수들이 순서가 뒤죽박죽인 채로 들어온다는 부분을 처음에 놓쳐서 좀 헤맸다.
정렬 한 다음에 가장 큰 값에서 나머지 세 값들을 하나씩 빼서 출력하면 된다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll arr[4];
int i;
for (i = 0; i < 4; i++) {
cin >> arr[i];
}
sort(arr, arr + 4);
cout << arr[3] - arr[0] << ' ';
cout << arr[3] - arr[1] << ' ';
cout << arr[3] - arr[2] << ' ';
return 0;
}
B.
배열에서의 최댓값(max_)과 최솟값(min_)을 구하고
만약 max_ % 2 == min_ % 2 라면
배열의 모든 수를 (max_ + min_) / 2로 바꿀 수 있는지,
즉 배열의 모든 수가 max_, min_, (max_+min_)/2인지 확인한다.
만약 그렇다면 답은 max_ - (max_ + min_) / 2가 된다.
만약 max_ % 2 != min_ % 2라면
배열의 모든 수가 max_나 min_인지 확인해야 한다.
처음에 D의 최솟값을 찾아야 되는건지 모르고
2
2 8
예제에서 6을 출력했다. 이것도 답인 줄 알고 제출했는데 WA였다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
int N;
int i;
cin >> N;
vector<int> arr(N + 5);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
int max_ = *max_element(arr.begin(), arr.begin() + N);
int min_ = *min_element(arr.begin(), arr.begin() + N);
bool ans = true;
for (i = 0; i < N; i++) {
if (!(arr[i] == max_ || arr[i] == min_)) {
ans = false;
break;
}
}
if (ans) {
if ((max_ - min_) % 2 == 0) {
cout << (max_ - min_) / 2;
}
else {
cout << max_ - min_ << ENDL;
}
return 0;
}
ans = true;
int mid = (max_ + min_) / 2;
if (mid * 2 != max_ + min_) {
ans = false;
}
for (i = 0; i < N; i++) {
if (!(arr[i] == max_ || arr[i] == min_ || arr[i] == mid)) {
ans = false;
break;
}
}
if (ans) {
cout << max_ - mid << ENDL;
}
else {
cout << -1 << ENDL;
}
return 0;
}
C.
우선 몇 주를 먹을 수 있는지를 구했는데,
일주일에 fish는 2번, rabbit은 2번, chicken은 3번 먹으므로
min({fish/2, rabbit/2, chicken/3})주 동안 먹을 수 있다.
이제 최대 며칠 가능한지 구해야 하는데
수가 별로 크지 않기 때문에 그냥 구현했다.
배열에 각 요일별로 먹는 음식이 뭔지 저장해놓고
월~일요일에 시작하는 각각의 경우에 대해 최대한 오래 버틸 수 있는 게 며칠인지 구했다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector<ll> val(3);
ll ans = 0;
int i, j;
cin >> val[0] >> val[1] >> val[2];
ans = min({ val[0] / 3, val[1] / 2, val[2] / 2 });
val[0] -= ans * 3;
val[1] -= ans * 2;
val[2] -= ans * 2;
ans *= 7;
char food[20] = { 'a', 'b', 'c', 'a', 'c', 'b', 'a', 'a', 'b', 'c', 'a', 'c', 'b', 'a' };
ll plus = 0;
for (i = 0; i < 7; i++) {
ll temp = 0;
vector<ll> val_temp = val;
for (j = 0; j < 7; j++) {
int idx = food[i + j] - 'a';
if (val_temp[idx] > 0) {
temp++;
val_temp[idx]--;
}
else {
break;
}
}
plus = max(plus, temp);
}
cout << ans + plus;
return 0;
}
D.
battery를 사용하면서 sunlight를 받을 때 accumulator가 충전되기 때문에
우선 accumulator를 사용해야 한다.
sunlight를 받을 때 accumulator가 이미 최대치로 충전되어 있다면 +1을 받지 못해 손해이기 때문.
이렇게 풀었는데 처음에 틀렸다
놓친 부분이,
만약 sunlight를 받는 구간을 지나가고, accumulator가 완충된 상태라면
accumulator를 사용해야 한다.
이런 상황에서는 battery나 accumulator 둘 중 뭘 사용해도 -1이 되는데,
accumulator가 완충된 상태이기 때문에 +1을 받지도 못한다.
따라서 이때 accumulator를 사용해서 -1 시켜놓으면
그 다음에 또 sunlight 구간을 지나갈 때 battery를 사용하면서 accumulator를 +1 시킬 수 있다.
결과적으로 battery만 사용하면 총합이 2 감소할 것이 1만 감소하기 때문에
이렇게 하는 게 최적이다
수정해서 냈더니 맞았다.
신기가 방기다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, maxA, maxB;
int A, B;
int i;
cin >> N >> maxA >> maxB;
A = maxA; B = maxB;
vector<char> arr(N + 5);
for (i = 0; i < N; i++) {
cin >> arr[i];
arr[i] -= '0';
}
for (i = 0; i < N; i++) {
if (arr[i]) {
if (B == maxB) {
B--;
continue;
}
if (A) {
A--;
B = min(B + 1, maxB);
continue;
}
}
if (B) { //되도록 accumulator부터 사용
B--;
}
else if (A) {
A--;
}
else {
break;
}
}
cout << i << ENDL;
return 0;
}
E.
초반에 문제를 잘못 이해해서 헤맸다.
각각에 대해 오른쪽과 왼쪽에 있는 사람이 누군지를 저장해놓고
중간에 사람들이 사라질때마다 좌우 인덱스를 업데이트 해주면 된다.
djs가 구간 업데이트 시키는 레이지 쓰면 풀리겠다고 했는데
그런 문제는 아니었다... 역시
근데 처음에는 이걸 linked list 써서 풀어야 되는 줄 알았다
linked list stl 어떻게 쓰는지 몰라서 안 함...
굳이 linked list를 쓸 필요도 없었고...
그리고 다른 분 풀이 보니까
그냥 set을 쓰면 된다.
set은 값들을 오름차순으로 정렬해주니까...
바로 앞뒤 인덱스에 접근 가능하다
신기가 방기다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, K;
int i;
cin >> N >> K;
priority_queue<pair<int, int>> pq;
vector<int> next(N+5), before(N+5);
for (i = 1; i <= N; i++) {
next[i] = i + 1;
before[i] = i - 1;
}
for (i = 1; i <= N; i++) {
int temp;
cin >> temp;
pq.push({ temp, i });
}
vector<int> ans(N + 5, 0);
int coach = 1;
while (!pq.empty()) {
int skill = pq.top().first;
int idx = pq.top().second;
pq.pop();
if (ans[idx] != 0) {
continue;
}
ans[idx] = coach;
int l, r;
int cnt;
for (i = before[idx], cnt = 0; i >= 0 && cnt < K; i = before[i], cnt++) {
if (ans[i]) {
break;
}
ans[i] = coach;
}
l = i + 1;
for (i = next[idx], cnt = 0; i <= N && cnt < K; i = next[i], cnt++) {
if (ans[i]) {
break;
}
ans[i] = coach;
}
r = i - 1;
next[before[l]] = r + 1;
before[next[r]] = l - 1;
if (coach == 1) {
coach = 2;
}
else {
coach = 1;
}
}
for (i = 1; i <= N; i++) {
cout << ans[i];
}
return 0;
}