Codeforces Round #751 (Div. 2), 1598 -> 1551
Dashboard - Codeforces Round #751 (Div. 2) - Codeforces
Dashboard - Codeforces Round #751 (Div. 2) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. Two Subsequences
Problem - A - Codeforces
codeforces.com
문제
string s가 주어졌을 때, 모든 문자열을 활용하면서 두 개의 string a,b 로 쪼개었을 때 a를 사전순으로 제일 작게 출력하는 문제
풀이
string s에서 가장 작은 아스키 코드 값의 char를 찾아 a로 출력하고, 해당 인덱스를 제외하고 나머지를 b로 출력한다
코드
#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--){
string s;
cin >> s;
char cmin = 'z'+1;
int idx = -1;
for (int i = 0; i < s.size(); i++) {
if (cmin > s[i]) {
cmin = s[i];
idx = i;
}
}
cout << cmin<<' ';
for (int i = 0; i < s.size(); i++) {
if (idx == i)continue;
cout << s[i];
}
cout << '\n';
}
}B. Divine Array
Problem - B - Codeforces
codeforces.com
문제
배열이 주어지고 한번 transformation 할때마다 주어진 배열의 원소는 각 원소들이 가지고 있는 갯수로 바뀐다.
이때 쿼리에서 인덱스와 몇번 transformation 했을 때, 바뀌는 값을 출력하는 문제
풀이
모든 값이 같아질때 까지 transformation 을 한 후, max 값을 넘기면 max값으로 바꿔주고 답을 출력
코드
#include <bits/stdc++.h>
using namespace std;
int a[2001], cnt1[2001],b[2001];
int ans[2001][8001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while(T--){
int n;
cin >> n;
int n2 = n * 4;
for (int i = 1; i <= n; i++) {
cnt1[i] = 0;
b[i] = 0;
for (int j = 1; j <= n2; j++) {
ans[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
ans[i][0] = a[i];
}
int cnt = 1;
while (true) {
bool flag = true;
for (int i = 1; i <= n; i++)cnt1[i] = 0;
for (int i = 1; i <= n; i++) {
cnt1[a[i]]++;
}
for (int i = 1; i <= n; i++) {
b[i] = cnt1[a[i]];
ans[i][cnt] = b[i];
if (a[i] != b[i])flag = false;
}
for (int i = 1; i <= n; i++) {
a[i] = b[i];
b[i] = 0;
}
if (flag)break;
cnt++;
}
int Q;
cin >> Q;
while (Q--) {
int x, y;
cin >> x >> y;
if (y > cnt)y = cnt;
cout << ans[x][y] << '\n';
}
}
}C. Array Elimination
Problem - C - Codeforces
codeforces.com
문제
주어진 배열에서 k개를 골라 모두 and 한 값을 뺄 수 있는 연산을 원하는 만큼 할 수 있을 때, 모든 배열을 0으로 만들 수 있는 모든 k 값을 출력하는 문제
풀이
각 비트마다 몇개의 숫자가 포함되는지 계산한 후 값들의 GCD를 구하여 이의 약수들을 출력 한다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[200001];
int cnt[31];
int gcd(int a, int b) { for (; b; a %= b, swap(a, b)); return a; }
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 < 31; i++)cnt[i] = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
int idx = 0;
long long t = a[i];
while (t) {
if (t % 2)cnt[idx]++;
t /= 2;
idx++;
}
}
bool flag = true;
int ans = 0;
for (int i = 0; i < 31; i++) {
if (cnt[i]) {
ans = gcd(ans, cnt[i]);
flag = false;
}
}
int i2 = sqrt(ans);
if (flag) {
for (int i = 1; i <= n; i++)cout << i << ' ';
cout << '\n';
continue;
}
vector<int> vans;
for (int i = 1; i <= i2; i++) {
if (ans % i == 0) {
int div = ans / i;
if (i == div)vans.push_back(i);
else {
vans.push_back(i);
vans.push_back(div);
}
}
}
sort(vans.begin(), vans.end());
for (auto kk : vans)cout << kk << ' ';
cout << '\n';
}
}레이팅 변화 :
1598 -> 1551 (-47)
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.