[버추얼 매일 돌리기 프로젝트 #1] Codeforces Round #554 (Div. 2)

3월 오렌지 가고 싶다. 

 

내가 아는 누군가가 코포 라운드 최대한 많이 참가하면 레이팅이 늘어난다고 해서 한다.

2020. 01. 01에 Codeforces Round #554 (Div. 2)을 했다. 순위는 1096. 3솔. 퍼포 1694로 블루 퍼포를 받았다. 그에 비에 낮은 레이팅으로선 잘 본 것 같다.

 

아쉬운건 C 뇌절이었다. C 생각을 좀더 급하게 하지 않았더라면 더 빨리 풀 수 있었을텐데.

 

 

A. 

곱해서 홀수가 되는 최대 쌍 갯수를 구하라는 문제이다.

홀수 = 짝수+홀수 이므로 우리는 어떤 한 배열에서 짝수인것을 매칭시키려면 다른 배열에서의 홀수인것을 골라야 된다.

그냥 짝수 갯수 홀수 갯수를 각 두 배열에서 세준 다음 두 배열에서의 조합을 뽑아낼수 있는 갯수를 출력하면 된다.

그러한 과정은 코드를 참고.

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
string s;
ll t,n,m;
ll w[MEM], v[MEM];
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ll h1=0,j1=0,h2=0,j2=0;
    for(int i=0; i<n; i++){
        ll q;
        cin >> q;
        if(q%2) h1++;
        else j1++;
    }
    for(int i=0; i<m; i++){
        ll q;
        cin >> q;
        if(q%2) h2++;
        else j2++;
    }
    cout << min(j1,h2) + min(j2,h1);
}

B.

어떤 수가 주어졌을때 40번 이내로 2^n-1(n은 임의의 수)를 xor하고 +1을 하는 작업을 해서 똑같은 2^n-1 형식의 수를 만드는 것인데, 이때의 가능한 n의 갯수와 가능한 n의 집합의 원소를 출력하라는 말이다.

먼저 2^n-1의 수 특성상 모든 비트가 1이다. 그러니 xor 했을때 비트가 0이면 1, 1이면 0으로 바뀐다. 

그러므로 우리는 이러한 성질을 이용하면 가장 앞에 있는 0부터 제거하는 그리디로 생각할 수 있다. 

그러한 점을 감안해서 잘 구현해주면 끝.

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
string s;
ll t,n,m;
ll w[MEM], v[MEM];
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    string s;
    ll k=n;
    while(k>0){
        if(k%2) s += '1';
        else s += '0';
        k /= 2;
    }
    reverse(s.begin(), s.end());
    //cout << s << '\n';
    vector<ll> ans;
    for(int i=0; ; i++){
        ll p=-1;
        for(int j=0; j<s.size(); j++)
            if(s[j]=='0') {
                p=j;
                break;
            }
        if(p==-1){
            cout << i << '\n';
            for(int j=0; j<ans.size(); j++)
                cout << ans[j] << ' ';
            return 0;
        }
        if(i%2){
            for(int j=s.size()-1; j>=0; j--){
                if(s[j]=='1') s[j] = '0';
                else {
                    s[j] = '1';
                    break;
                }
            }
        }
        else{
            ans.push_back(s.size()-p);
            for(int j=p; j<s.size(); j++){
                if(s[j]=='0') s[j] = '1';
                else s[j] = '0';
            }
        }
        //cout << i << ' ' << p << ' ' << s << '\n';
    }
}

C.

뇌절했지만 1800을 푼거라 기쁘다. 이왜1800?

그냥 두 수가 주어지도 어떤 수 k를 동시에 더했을때 두수의 최소공배수를 최소로 하는 수 k를 구하라는게 문제였다.

a>b 인 두수 a, b가 있다고 가정하자.

gcd(a+k, b+k) = gcd(b+k, a-b)

lcm(a+k, b+k) = (a+k)(b+k)/gcd(b+k, a-b)

이때 gcd로 나올 수 있는 수는 a-b의 약수이다.

그러므로 O(n^(1/2))에 약수를 구해놓은 다음 약수들의 lcm 값이 최소인 것을 골라 k를 출력하면 된다.

최소를 구하는 아주 쉬운 방법은 우선순위 큐다. 역시 믿고 있었다구!

 

여담으로 너무 성급히 생각하는 바람에 gcd로 나올 수 있는 수가 a-b밖에 없다고 가정하고 풀어서 뇌절했다. ㅋㅋ! 

8틀해서 C에서 464점밖에 못받았다. ㄹㄱㄴ

#include <bits/stdc++.h>
#define MEM 200005
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e9+7;
const ll MOD = 1e6+7;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
string s;
ll t,n,m;
vector<ll> v;
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n >> m;
    if(n<m) swap(n,m);
    ll g = n-m;
    if(!g) {
        cout << g;
        return 0;
    }
    ll res=0, ans=INF;
    for(ll i=1; i*i<=g; i++){
        if(g%i) continue;
        v.push_back(i);
        if(i!=g/i) v.push_back(g/i);
    }
    priority_queue<pi> pq;
    for(int i=0; i<v.size(); i++){
        ll k=v[i];
        ll h=(k-(m%k))%k;
        //cout << k << ' ' << ((n+h)*(m+h))/k << ' ' << h << '\n';
        pq.push({-((n+h)*(m+h))/k, h});
    }
    cout << pq.top().y;
}

버추얼 레이팅 1357 -> 1457로 상승.

마침 새해라 오렌지 되고 싶단 마음으로 핸들을 잠깐 만들어놨다.