Codeforces Round #618 (Div. 1) 후기 + 풀이

Predictor에 +116이라고 뜨는 것과는 달리, 실제로는 +115를 받아서 2099점이 되었다.

오렌지 갔나 했는데, :blobsad: ㅠㅠ

라운드는 굉장히 재밌게 했던것 같다. 

---

A. Anu has a function

수열 $a_1, a_2, a_3 \dots a_n$ 과 함수 $f(x, y) = (x | y) - y$ 이 주어질 때, 이들을 적당히 재배열해서 $$f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)$$ 의 값을 최대화하는 문제.

 

잘 생각해 보면, $f(x, y)$ 는 $x$의 On bit 들을 모은 집합에서 $y$의 On bit 들을 모은 집합의 차집합을 반환한다는 사실을 알 수 있다. 즉, 최대한 '가치' 가 높은 비트(큰 비트) 들을 살리는 방향으로 가야 하고, 비트를 살리려면 그 비트를 가진 원소가 수열에서 한 개밖에 없어야 하며 그 한 개가 맨 앞에 와야 한다는 것을 알 수 있다.

 

미리 각 비트별로 켜진 원소를 모두 모은 다음, 최대한 끝 ($2^{30}$ 에 가까운 비트) 에서부터 한 개밖에 없는지 확인하고, 한개밖에 없으면 그 원소를 맨 앞에 놓고 나머지는 아무렇게나 놓는다. (어차피 나머지 원소는 비트를 끄기만 하고, 새로 켜는 역할은 할 수 없다) 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;

vector <int> v;
vector <pii> vv;
vector <int> numbers[32];
int save = -1;
set<int> st;
int32_t main()
{
    usecppio
    int n;
    cin >> n;
    v.resize(n);
    for (int i = 0; i<n; i++)
    {
        cin >> v[i];
        for (int j = 0; j<31; j++)
            if ((1<<j) & v[i])
                numbers[j].push_back(v[i]);
    }
    for (int i = 31; i>=0; i--)
    {
        if (numbers[i].size()==1)
        {
            if (st.find(numbers[i][0])==st.end())
            {
                vv.push_back({i,numbers[i][0]});
                st.insert(numbers[i][0]);
            }
        }
    }
    for (auto it:v)
        if (st.find(it)==st.end())
            vv.push_back({0,it});
    for (auto it:vv)
        cout << it.second << ' ';
    cout << '\n';
}

---

B. Aerodynamic

도형 $P$를 적당히 평행이동하되, 원점이 $P$에 포함되게 하자. 이때 모든 가능한 $P$들의 합집합을 $T$라 하고, $T$가 $P$와 닮음인지 판단하는 문제.

 

Proof by AC 로 점대칭을 찍을 수도 있지만, 나는 대충 이런 식으로 생각했다.

 

$O(n^2)$ : 각 점에 원점이 위치할 때, 나머지 $n$개 점들이 어디에 가 있는지를 본다.

이때, 총 $n^2$ 개의 점들에 대해, Convex Hull을 따면 $T$를 얻는다.

 

이 Convex Hull 에 $n$개 보다 많은 점들이 꼭짓점으로 있게 된다면, 닮음이 될 수 없다. 즉, 도형의 점 $a$ 에서 $b$로 원점을 옮기는 동안, Convex hull에 점이 추가되지 않아야 하고, 이러려면 점대칭일 때만 성립한다는 것을 약간의 관찰 + 종이에 그려 보면 알 수 있다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;

vector <pii> v;
int32_t main()
{
    usecppio
    int n;
    cin >> n;
    if (n%2 ==1)
    {
        cout << "NO\n"; 
        return 0;
    }
    for (int i = 0; i<n; i++)
    {
        int x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    v.push_back(v[0]);
    for (int i = 1; i<=n/2; i++)
    {
        pii vt1 = {abs(v[i].first-v[i-1].first), abs(v[i].second-v[i-1].second)};
        pii vt2 = {abs(v[i+n/2].first-v[i+n/2-1].first), abs(v[i+n/2].second-v[i+n/2-1].second)};
        if (vt1 != vt2)
        {
            cout << "NO\n"; 
            return 0;
        }
    }
    cout << "YES\n";
}

---

C. Water balance

구간 $[l, r]$ 을 잡고, $a_l, a_{l+1} \dots a_r$ 을 모두 이 구간의 평균값으로 대체하는 연산을 하고 싶은 만큼 할 수 있다. 가능한 한 Lexiographically smallest 수열을 만들고 싶다.

사전순으로 최대한 앞에 오려면, 맨 앞 원소를 최소화하고, 그다음 원소를 최소화하고...이런 식으로 최적화해야 한다. 

 

잠깐 관찰해 보면, 감소하는 부분배열이 있다면 그 부분을 합치는 것은 반드시 이익이다. 감소하는 부분배열이 $a_3, a_4, a_5$ 라고 하면 이들을 합칠때 적어도 $a_3$이 원래보다 줄어들게 되므로, 사전순 앞에 오기 때문이다. 

 

 

이제 Convex Hull Trick 을 적용할 수 있는것 같지만, 대회 중에는 이런 생각을 못 하고 스택에다가 계속 올리면서 Segment를 관리하는 방법으로 풀었다.

감소하는 부분배열을 모두 합치고, 다시 확인하면서, 더이상 합칠 배열이 없다면 더이상 최적화할 방법이 없으므로 그만두면 된다. 다시 확인해야 하는 이유는, 앞서의 예시에서 $a_3, a_4, a_5$ 를 합치기 전에는 $a_2 < a_3$ 이었는데, 합친 후에는 $a_2 > a_3$ 이라면 다시 $a_2$ 도 같이 합치는 것이 $a_2$ 를 줄일 수 있어서 이득이기 때문이다.

 

이 풀이의 시간 복잡도는 사실 잘 모르겠는데, 3초 짜리 문제에서 2초에 도는걸 보니 그럭저럭 앞뒤는 맞는것 같다.

#include <bits/stdc++.h>
using namespace std;
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair <int, int>;

struct segment
{
    int left, right;
    double value;
    segment(int a = 0, int b = 0, double c = 0)
    {
        left = a, right = b, value = c;
    }
    bool operator<(const segment &other)
    {
        return value < other.value;
    }
    inline int length()
    {
        return right-left+1;
    }
    inline void print()
    {
        printf("Segment %d to %d : %lf\n", left, right, value);
    }
};

segment seg_merge(segment &a, segment &b)
{
    segment newseg;
    newseg.left = a.left;
    newseg.right = b.right;
    newseg.value = (b.value*b.length())+(a.value*a.length());
    newseg.value /= newseg.length();
    return newseg;
}

vector <segment> v;
vector <segment> tmp;
int n;

int32_t main()
{
    usecppio
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        int c; cin >> c;
        v.push_back({i,i,c*1.0});
    }
    while(true)
    {
        bool flag = 0;
        for (auto it:v)
        {
            if (tmp.empty())
            {
                tmp.push_back(it);
                continue;
            }
            segment u = tmp.back();
            tmp.pop_back();
            if (it < u)
            {
                flag = true;
                u = seg_merge(u,it);
                tmp.push_back(u);
            }
            else
            {
                tmp.push_back(u);
                tmp.push_back(it);
            }
        }
        v = tmp;
        tmp.clear();
        if (!flag)
            break;
    }
    for (auto it:v)
    {
        int u = it.length();
        for (int i = 0; i<u; i++)
            cout << fixed << setprecision(10) << it.value << '\n';
    }
}

---

남은 시간동안 D를 버리고 E를 고민하다가 아무것도 하지 못하고 끝났다. 대략 Chinese Remainder Theorem 을 이용해, 몇 개 소수로 나눈 나머지를 각각 알아낸 다음 합치는 풀이를 구상했는데 구체적으로 쿼리를 어떻게 써야 CRT 각을 잴 수 있을지 생각하다가 시간 끝. 정해는 대충 저게 맞는 것 같은데 아직 제대로 이해를 못 했다. 

 

Div 2는 또 뛰게 되면 이제 1페이지 안에 드는 정도 Performance가 나오지 않으면 아마 레이팅이 떡락할 예정이기 때문에, 당분간은 Div1만 뛸 생각이다. 근데 Div1이 있어야 말이지;;;