Codeforces Round #743 (Div. 2) , Unrated
Dashboard - Codeforces Round #743 (Div. 2) - Codeforces
Dashboard - Codeforces Round #743 (Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. Countdown
Problem - A - Codeforces
codeforces.com
문제
계산기에 숫자가 표시된다. 이 때
1. 1을 뺀다
2. 2개의 자리 수를 정해 위치를 바꾼다
한번의 연산에 하나씩 하면서, 최소 연산으로 0을 만들 때 최소 연산의 수를 출력하는 문제
풀이
각 자리수를 정답에 추가시키고, 각 자리수가 끝자리가 아니라면 정답을 1씩 더 추가시켜 준다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n,ans=0;
string s;
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] != '0') {
ans += (s[i] - '0');
if (i != (n - 1))ans++;
}
}
cout << ans << '\n';
}
}
B. Swaps
Problem - B - Codeforces
codeforces.com
문제
1 ~ 2n 까지 a 배열에는 홀수만 , b 배열에는 짝수만 주어진다. 이때 각 배열에서 i를 선정하여
i와 i+1번째 숫자를 swap할 수 있다. 이때 a < b를 만들 수 있는 최소 swap의 수를 구하는 문제
풀이
D[i] = a배열에서 숫자 i이하의 모든 수중에서 최소 인덱스
ans = min( ans, d[b[i]]+ idx[b[i]] )
정답은 b[i] 이하 숫자 최소인덱스 + b[i]의 인덱스 중 최솟 값을 출력하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int a[100001], b[100001];
int aidx[200001], bidx[200001];
int d1[200001], d2[200001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
aidx[a[i]] = i;
}
for (int i = 0; i < n; i++) {
cin >> b[i];
bidx[b[i]] = i;
}
int n2 = n * 2;
d1[1] = d1[2] = aidx[1];
for (int i = 3; i <= n2;i+=2){
d1[i] = min(d1[i - 1], aidx[i]);
d1[i + 1] = d1[i];
}
int MAX = 0,start=0,ans=1000000;
for (int i = 0; i < n; i++) {
ans = min(ans, d1[b[i]]+bidx[b[i]]);
}
for (int i = 1; i <= n2; i++) {
d1[i] = 0;
}
cout << ans << '\n';
}
}
C. Book
Problem - C - Codeforces
codeforces.com
문제
n개의 챕터와 선행 챕터가 주어진다. 1부터 n까지 챕터를 쭉 공부하되, 선행 챕터를 공부 못했으면 못배우고 넘어간다.
이 때 쭉 반복해서 모두 배울 수 있다면 반복 횟수, 못배운다면 -1을 출력하는 문제
풀이
위상 정렬을 이용하여 풀되, 큐 2개를 이용하여 반복 횟수를 구한다. 이 때 못 배운 챕터가 있으면 -1 이고, 첫번째로 사용하는 큐는 min-heap을 사용해야한다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> v[200001];
int ind[200001];
priority_queue<int, vector<int>, greater<int>> pq;
queue<int> q2;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
while (!pq.empty())pq.pop();
while (!q2.empty())q2.pop();
int n,ans=0;
cin >> n;
for (int i = 1; i <= n; i++) {
ind[i] = 0;
v[i].clear();
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
ind[i] += x;
for (int j = 0; j < x; j++) {
int t;
cin >> t;
v[t].push_back(i);
}
}
for (int i = 1; i <= n; i++) {
if (ind[i] == 0) {
pq.push(i);
}
}
while (!pq.empty()) {
while (!pq.empty()) {
int x = pq.top();
pq.pop();
for (auto k : v[x]) {
ind[k]--;
if (ind[k] == 0) {
if (k > x)pq.push(k);
else q2.push(k);
}
}
}
while (!q2.empty()) {
pq.push(q2.front());
q2.pop();
}
ans++;
}
bool flag = true;
for (int i = 1; i <= n; i++) {
if (ind[i]) {
flag = false;
break;
}
}
if (flag)cout << ans << '\n';
else cout << -1 << '\n';
}
}
레이팅 변화 :

중간에 채점 이슈로 인해 언레이팅 대회가 되었습니다..
점수는 그대로이며 아쉬운데로 퍼포먼스만 캡처했습니다.
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.