CodeCraft-22 and Codeforces Round #795 (Div. 2) 1589 → 1681
https://codeforces.com/contest/1691
Dashboard - CodeCraft-22 and Codeforces Round #795 (Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 공부를 위한 올바른 정해가 아닐 수 있습니다 !!!!
A. Beat The Odds
https://codeforces.com/contest/1691/problem/A
Problem - A - Codeforces
codeforces.com
문제
n길이의 배열 a가 주어진다. 어떠한 2개의 연속 합이 짝수가 되도록 지워야하는 최소 원소의 수를 출력하는 문제
풀이
모든 홀수를 지우는 경우의 수와 모든 짝수를 지우는 경우의 수중 작은 값을 출력한다
코드
#include <bits/stdc++.h>
using namespace std;
long long a[100001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
int even = 0, odd = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] % 2)odd++;
else even++;
}
cout << min(n - odd, n - even) << '\n';
}
}
B. Shoe Shuffling
https://codeforces.com/contest/1691/problem/B
Problem - B - Codeforces
codeforces.com
문제
n길이의 비내림차순 수열 a가 주어진다. a[i]는 i번째 학생이 신고 있는 신발 사이즈이며 , 모든 학생이 현재 신은 신발을 제외하고 현재보다 같거나 큰 신발로 갈아 신을 수 있다면 YES 아니라면 NO를 출력하는 문제
풀이
무조거 같은 사이즈의 신발끼리 교환해야 하므로 신발 사이즈가 1개인 신발이 하나라도 있다면 답은 NO이고 나머지는 한칸식 옆으로 인덱스를 옮겨 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[100001];
vector<int> ans;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
ans.clear();
int n;
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
if (n == 1) {
cout << "-1\n";
continue;
}
bool flag = true;
for (int i = 0; i < n; i++) {
int i2 = i + 1, cnt = 1;
while (i2 < n) {
if (a[i] == a[i2])cnt++;
else break;
i2++;
}
if (cnt == 1) {
flag = false;
break;
}
i2--;
ans.push_back(i2+1);
for (int j = i; j < i2; j++) {
ans.push_back(j + 1);
}
i = i2;
}
if (flag) {
for (int i = 0; i < n; i++)cout << ans[i] << ' ';
cout << '\n';
}
else cout << "-1\n";
}
}C. Sum of Substrings
https://codeforces.com/contest/1691/problem/C
Problem - C - Codeforces
codeforces.com
문제
n길이의 binary string과 k가 주어진다. 한번의 operation에 인접한 원소를 swap할 수 있으며 최대 k번 operation을 적용할 수 있다. i = 1 .. (n-1)까지 digit로 s[i]s[i+1]의 숫자를 모두 더한 값을 f(s)라고 했을때 최대 k번 적용후 f(s)의 최소 값을 구하는 문제
풀이
k의 여유가 된다면 우선순위가 가장 빠른 순서대로 아래를 진행해준다.
가장 오른쪽의 1을 s의 마지막 위치로
가장 왼쪽의 1을 s의 처음 위치로
이후 f(s)의 값을 계산하여 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
cin >> s;
int cnt = 0;
int l = -1,idxl, r = -1,idxr;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
l = i;
cnt++;
idxl = i;
break;
}
}
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '1') {
r = n - i - 1;
idxr = i;
if (idxl != idxr)cnt++;
break;
}
}
if (cnt == 0)cout << 0 << '\n';
else if (cnt == 1) {
if (r <= k) {
cout << 1 << '\n';
continue;
}
if (l <= k) {
cout << 10 << '\n';
continue;
}
cout << 11 << '\n';
}
else {
if (r <= k) {
swap(s[idxr], s[n - 1]);
k -= r;
}
if (l <= k) {
swap(s[idxl], s[0]);
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
int num = 0;
for (int j = i; j <= i + 1; j++) {
num *= 10;
num += (s[j] - '0');
}
ans += num;
}
cout << ans << '\n';
}
}
}D. Max GEQ Sum
https://codeforces.com/contest/1691/problem/D
Problem - D - Codeforces
codeforces.com
문제
max(ai,ai+1,…,aj−1,aj) ≥ ai+ai+1+⋯+aj−1+aj , 1≤i≤j≤n
가능한 모든 i , j 에 대하여 위와 같은 식을 만족한다면 YES 아니라면 NO를 출력하는 문제
풀이
시스텟은 통과하였지만 틀린 로직이고 , 핵당하였으므로 풀이는 추후 수정
코드
#include <bits/stdc++.h>
using namespace std;
long long a[200001];
long long pre[200001];
vector<int> v;
const long long inf = 1000000000LL * 200001LL;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
v.clear();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
if (a[i] > 0)v.push_back(i);
}
bool flag = true;
for (int i = 1; i < v.size(); i++) {
long long MIN = min(a[v[i - 1]], a[v[i]]);
long long sum = pre[v[i]-1] - pre[v[i - 1]];
//cout << MIN << ' ' << sum << '\n';
if (MIN + sum > 0) {
flag = false;
break;
}
}
long long sum = 0, MAX = inf;
for (int i = n; i > 0; i--) {
MAX = max(MAX, a[i]);
if (sum + a[i] > MAX) {
flag = false;
break;
}
sum += a[i];
if (sum <= 0) {
sum = 0;
MAX = inf;
}
else {
if (MAX == inf) MAX = a[i];
else MAX = max(MAX, a[i]);
}
}
if (flag)cout << "YES\n";
else cout << "NO\n";
}
}자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.