코드포스 Codeforces Round #751 (Div. 2) 풀이

1602A - Two Subsequences

문자열 중에서 아스키코드상 가장 빠른 캐릭터와 나머지 문자열로 나누면 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        char min_char='z';
        int min_idx=0;
        for(int i=0; i<s.size(); i++) {
            if(min_char>s[i]) {
                min_char = s[i];
                min_idx = i;
            }
        }
        cout << min_char << ' ';
        for(int i=0; i<s.size(); i++) {
            if(i==min_idx) continue;
            cout << s[i];
        }
        cout << '\n';
    }
}

---

1602B - Divine Array

최대 n번 수행하면 배열은 고정이라는 것을 쉽게 알아낼 수 있다.

 

따라서 n개의 배열을 저장한 다음 쿼리 (x, k)를 (x, min(k, n))로 바꿔준 다음 출력하면 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
 
int an[2020][2010];
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        int n, q;
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> an[0][i];
        }
        for(int k=1; k<=n; k++) {
            int cnt[2020]{0};
            for(int i=1; i<=n; i++) {
                cnt[an[k-1][i]]++;
            }
            for(int i=1; i<=n; i++) {
                an[k][i] = cnt[an[k-1][i]];
            }
        }
        cin >> q;
        for(int i=0; i<q; i++) {
            int a, k;
            cin >> a >> k;
            k = min(k, n);
            cout << an[k][a] << '\n';
        }
    }
}

---

1601A - Array Elimination

배열에서 k(1<=k<=n) 개의 원소를 선택한 후 그 원소들을 전부 AND 연산한 값을 각 각 빼준다는 의미를 생각해보자.

 

비트단위로 생각해 봤을 때 k개의 원소가 전부 가지고 있는 비트를 빼 준다고 생각하면 된다.

 

예를 들어 두 번째 자리에 있는 비트가 1인 원소가 8개라면 그 두 번째 자리에 있는 비트를 제거해 주려면 이 8개 중에서 묶어서 제거해야 한다는 의미이다.

 

원소 8개가 전부 두번째 자리에 있는 비트를 제거해 주어야 하므로 묶을 수 있는 경우의 수는 1, 2, 4, 8이다.

 

이것은 8의 약수라는 것을 알 수 있다.

 

일단 원소가 가질 수 있는 최댓값은 2의 30승이다. 따라서 29번째 비트까지만 확인하면 된다.

 

1번째 비트를 가지고 있는 원소 수, 2번째 비트를 가지고 있는 원소 수, 3번째 비트를 가지고 있는 원소 수.

 

이렇게 29번째까지 원소 수를 구한다음 전체의 최대공약수를 구하고 그 최대공약수의 약수들이 정답이다.

 

정말 약수를 선택하면 전부 제거할 수 있는 이유는 다음과 같다.

 

예를 들어 2가 선택되었다고 하자.

 

1번째 비트부터 2개씩 묶어서 제거를 해야 하는데, 1번째 비트를 제거하다가 우연히 두 번째 비트도 제거하게 되는 경우가 있을 수 있다.

 

하지만 2번째 비트가 우연히 제거되는 경우는 선택한 두 개의 원소가 전부 두번째 비트를 가지고 있을 때에만 제거가 되므로 항상 나누어 떨어지게 된다.

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define F first
#define S second
 
const int N=200000;
int n, an[N+10];
int main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
 
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i=1; i<=n; i++) {
            cin >> an[i];
        }
        int ans=0;
        for(int k=0; k<30; k++) {
            int cnt=0;
            for(int i=1; i<=n; i++) {
                if(an[i]&(1<<k)) cnt++;
            }
            ans = __gcd(ans, cnt);
        }
        if(!ans) {
            for(int i=1; i<=n; i++) {
                cout << i << ' ';
            }
            cout << '\n';
            continue;
        }
        for(int i=1; i<=ans; i++) {
            if(ans%i==0) cout << i << ' ';
        }
        cout << '\n';
    }
}

---

1601B - Frog Traveler