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

프로젝트 2일차

 

2020. 01. 02에 Codeforces Round #539 (Div. 2)를 돌렸다. 순위 1027. 3솔. 퍼포 1628로 브루 퍼포를 받았다. 

블루 퍼포는 잘 나오긴 하나 아직 뇌절하는 건 똑같은 것 같고, Xor을 잘 몰랐던 나는 C를 푸는데 너무나도 힘들었다.

 

아무튼 Xor 문제를 그래도 풀어서 기쁘다. 단 C에서 뇌절을 자주하는 느낌이다. 저걸 잡는 것이 우선인듯 하다.

 

 

A. codeforces.com/contest/1113/problem/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;
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-1<=m){
        cout << n-1;
        return 0;
    }
    ll g=n-m-1;
    cout << m+(g+1)*(g+2)/2-1;
}

B. codeforces.com/contest/1113/problem/B

두개의 원소를 골라서 어떤 임의의 정수를 골라 각각 나누고 곱해서 합이 최소이게 만드는 문제인데

차이가 최대로 작아질 수 있는건 배열의 최소 원소를 무조건 고르고

나머지 원소들을 시도해보면서 최소를 찾으면 된다.

 

이상한 가정을 해서 뇌절했다. 이런 경우를 만들지 말고 시간복잡도에 맞으면 그걸로 만족해야겠다.

#include <bits/stdc++.h>
#define MEM 400005
#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;
}
ll t,n,m;
ll a[MEM];
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    ll k=*min_element(a,a+n);
    ll s=accumulate(a,a+n,0);
    ll ans=INF;
    //cout << k << ' ' << s << '\n';
    for(int i=0; i<n; i++){
        for(int j=1; j<=a[i]; j++)
            if(a[i]%j==0) {
                ll p = s-k-a[i];
                ll o=a[i];
                p += k*j+o/j;
                ans = min(ans, p);
            }
    }
    cout << ans;
}

C. codeforces.com/contest/1113/problem/C

문제 설명은 길어서 생략

xor의 성질을 이용하면 쉽게 풀린다. 

그냥 a^a=0이라는 것을 이용하면 쉽게 풀리는 아주 쉬운 문제이다. 

l-r+1 규칙은 dp를 이용해서 풀어준다.

#include <bits/stdc++.h>
#define MEM 300005
#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;
}
ll t,n,m;
ll a[MEM], b[MEM];
ll dp[(1<<20)+1][2];
main()
{
    sanic; cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i];
        if(i>0) b[i] = b[i-1];
        b[i] ^= a[i];
    }
    dp[0][1] = 1;
    ll ans=0;
    for(int i=0; i<n; i++){
        ans += dp[b[i]][i%2];
        dp[b[i]][i%2]++;
    }
    cout << ans;
}

 

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

저번처럼 8틀 안해서 다행이다.;;