[Codeforces] Codeforces Round #468 (Div. 2, based on Technocup 2018 Final Round) 이야기

A. Friends Meeting :: http://codeforces.com/contest/931/problem/A

a는 ++가 되도록, b는 --가 되도록하되 이때 da, db를 둬서 1,2,3,4,... 식으로 값이 더해지도록만 만들어 주면 된다.

결국 aa + bb가 정답이 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <memory.h>
#include <queue>
#include <string>
#include <set>
#include <vector>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
 
int main()
{
    int a, b;
    cin >> a >> b;
    if (a > b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
 
    int aa = 0, bb = 0, da = 1, db = 1;
    while (1)
    {
        if (a == b)
            break;
 
        a++;
        aa += da;
        da++;
 
        if (a == b)
            break;
 
        b--;
        bb += db;
        db++;
    }
 
    cout << aa + bb;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B. World Cup :: http://codeforces.com/contest/931/problem/B

n명의 사람이 있고 토너먼트 대진표 방식으로 진행이 된다 할때 a, b번의 위치의 사람이 몇번째에 만날지 묻는 이야기이다.

대진표 문제같은 경우 a / 2 != b / 2를 통해 어디서 만날 지 파악할 수 있게 된다. 

 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <memory.h>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
int main() 
{
    int n, a, b;
    scanf("%d %d %d", &n, &a, &b);
 
    int last = (int)ceil(log2(n));
    a--, b--;
 
    int ans = 0;
 
    while (a / 2 != b / 2)   
        ans++, a /= 2, b /= 2;
 
    if (ans + 1 == last)   
        cout << "Final!";
    else 
        cout << ans + 1;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Laboratory Work :: http://codeforces.com/contest/931/problem/C

mid + 1, mid , mid -1 세값이 존재할때

이때 등장횟수를 각각 a  , b , c라고하자.

그럼 전체 합을 S라 하고 전체 등장횟수는 n이니 a + b + c = n이 된다.

그럼 S = a*(mid + 1) + b*mid + c*(mid-1)이 되고

이 식을 전개하면 S = a*mid + a + b*mid + c*mid - c가 되고

이걸 다시 묶으면 

S = mid*(a+b+c) + a - c

S = mid*n + a - c

이때 S, mid, n은 우리가 모두 알고있으니

S - mid * n = a - c

S - mid * n을 x로 두면 x = a - c

따라서 a = x + c로 나타내면 a를 for문을 통해 찾을 수 있게되고

c도 마찬가지로 찾아 낼 수 있게 된다.

결국 a랑 c찾으면 n - a - c  = b이니 b를 찾을 수 있게 된다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <memory.h>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
ll arr[100002];
vector<ll> vc;
 
map<ll, ll> mp;
 
int main() 
{
    ll n;
    scanf("%lld", &n);
 
    ll minval = 1e18, maxval = -1e18;
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &arr[i]);
        minval = min(minval, arr[i]);
        maxval = max(maxval, arr[i]);
 
        mp[arr[i]]++;
 
        sum += arr[i];
    }
    
    if (maxval - minval <= 1)
    {
        printf("%lld\n", n);
        for (int i = 0; i < n; i++)
            printf("%lld ", arr[i]);
        return 0;
    }
 
    ll mid = (maxval + minval) / 2;
 
    sum -= n*mid;
 
    ll midN = 1e18;
 
    for (ll c = 0; c <= n; c++)
    {
        ll a = c - sum;
        ll b = n - a - c;
 
        if (a > n || b > n || a < 0 || b < 0)
            continue;
 
        midN = min(midN, min(mp[maxval], c) + min(mp[mid], b) + min(mp[minval], a));
    }
 
    printf("%lld\n", midN);
    for (ll c = 0; c <= n; c++)
    {
        ll a = c - sum;
        ll b = n - a - c;
 
        if (a > n || b > n || a < 0 || b < 0)
            continue;
 
        if (min(mp[maxval], c) + min(mp[mid], b) + min(mp[minval], a) == midN) {
            for (int i = 0; i < a; i++)
                printf("%lld ", minval);
            for (int i = 0; i < b; i++)
                printf("%lld ", mid);
            for (int i = 0; i < c; i++)
                printf("%lld ", maxval);
            return 0;
        }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

D. Peculiar apple-tree :: http://codeforces.com/contest/931/problem/D

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <memory.h>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include <cmath>
 
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
 
int p[100002], depth[100002], cnt[100002];
vector<int> vc[100002];
 
void func(int cur)
{
    for (int i = 0; i < vc[cur].size(); i++) 
    {
        int next = vc[cur][i];
        depth[next] = depth[cur] + 1;
        func(next);
    }
}
 
int main() 
{
    int n;
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++) 
    {
        scanf("%d", &p[i]);
        vc[p[i]].push_back(i);
    }
 
    func(1);
 
    for (int i = 1; i <= n; i++)
        cnt[depth[i]]++;
 
    int ret = 0;
 
    for (int i = 0; i < 100002; i++)
        if (cnt[i] % 2)   
            ret++;
 
    printf("%d\n", ret);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

이 문제는 트리의 레벨에 홀수개가 있으면 1개만 가고, 짝수개가 있으면 0개가 된다.

따라서 func를 통해 트리를 구성해주고

그다음 for문에서 현재 depth의 cnt를 ++해준다.

마지막으로 for문을 돌면서 현재 depth의 cnt가 홀수개이면 ret ++를 해주면 정답을 구할 수 있다.