Codeforces Round 601 + 616 (Practice)

dlwocks31 이랑 코드포스 Division 1 라운드 두개를 붙여서 같이 연습을 돌았다. Division 2는 A/B를 푸는게 실제로는 별로 의미가 없고, Div2 F는 못 풀 가능성이 높으니 실제로는 풀 만한 문제가 3개밖에 없어서 2시간 반을 잡고 Div1 두 라운드의 ABC 세문제씩만 뽑았다.

 

Round 616 Problem A. Mind Control

사람들이 줄을 서 있고, 어떤 배열의 맨 앞과 맨 뒤 중 하나를 골라서 뽑아 올 수 있다. 이때 $m$ 번째에 서서 최대한 큰 수를 가져가고 싶은데, 앞에 있는 $m-1$ 명 중 $k$ 명의 선택을 강제할 수 있다. 나머지 $m-k-1$ 명은 어떤 선택을 할 지 알 수 없지만 내가 최대한 손해를 보는 상황이 되었을 때 얻는 값을 찾는 문제.

생각해 보면, $k$ 명 중 몇명을 앞에 놓고 몇명을 뒤에 놓을지 정하는 경우는 $k+1$ 가지 있고 (앞에 놓는 사람이 0명 이상 $k$명 이하) 나머지 사람들이 어떻게 행동할지를 판단하는 경우가 앞뒤로 $m-k-1$ 가지 있으므로, 대략 $k^2$ 시간에 가능한 모든 경우를 확인할 수 있다. $n = 3500$ 이므로, 이정도면 충분,

dlwocks가 multiset을 이용해서 $n \log n$ 에 해결하는 방법도 찾았다. :fan:

#include <bits/stdc++.h>
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
 
int arr[4040];
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i<=n; i++)
        cin >> arr[i];
    k = min(k, m-1);
    int u = m-k-1;
    int x = INT_MIN;
    for (int i = 0; i<=k; i++)
    {
        int aa = INT_MAX, bb = INT_MAX, cc = INT_MAX;
        for (int j = 0; j<=u; j++)
        {
            aa = arr[i+j+1];
            bb = arr[n-k-u+i+j];
            cc = min(cc,max(aa, bb));
        }
        x = max(cc,x);
    }
    cout << x << '\n';
}

int32_t main()
{
    usecppio
    int t;
    cin >> t;
    while(t--)
        solve();
}

 

 

Round 601 Problem A. Feeding Chicken

$r \times c$ 그리드를 연결된 공간들로 분할하되, 각 공간이 최대한 균일한 개수의 체크된 칸을 갖게 하는 문제.

문제의 차원을 내려서, 1차원 상황이었다면 적절한 좌우 구간을 정해서 자름으로써 최대한 균일하게 만들기 쉽다. 이제, 2차원 그리드를 1차원으로 펴되, 1차원에서 고른 임의의 구간이 항상 연결된 공간으로 매핑되도록 펴면 된다. 

가장 쉽게 ㄹ자 모양으로 펴면, 1차원 버전의 문제에서 고른 구간을 몇 줄에 걸쳐서라도 연결된 공간으로 표현하는 데 문제가 없다. 

#include <bits/stdc++.h>
#define all(x) ((x).begin()),((x).end())
using namespace std;

int arr[120][120];
char mp[120][120];
int linear[10101];
vector <int> lp;
char ans[100] = ",0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
void solve()
{
    lp.clear();
    int r, c, k;
    int n = 0;
    scanf("%d %d %d",&r,&c,&k);
    int pt = 1;
    for (int i = 1; i<=r; i++)
        scanf("%s",mp[i]+1);
    for (int i = 1; i<=r; i++)
    {
        if (i%2)
        {
            for (int j = 1; j<=c; j++)
            {
                arr[i][j] = pt;
                if (mp[i][j]=='R')
                {
                    n++;lp.push_back(pt);
                }
                pt++;
            }
        }
        else
        {
            for (int j = c; j>=1; j--)
            {
                arr[i][j] = pt;
                if (mp[i][j]=='R')
                {
                    n++;lp.push_back(pt);
                }
                pt++;
            }
        }
    }
    reverse(all(lp));
    int u = n/k;
    int cur = 1;
    for (int i = 1; i<=n%k; i++)
    {
        int ct = u+1;
        while(ct)
        {
            if (cur==lp.back())
            {
                ct--;
                lp.pop_back();
            }
            linear[cur] = i;
            cur++;
        }
    }
    for (int i = n%k+1; i<k; i++)
    {
        int ct = u;
        while(ct)
        {
            if (cur==lp.back())
            {
                ct--;
                lp.pop_back();
            }
            linear[cur] = i;
            cur++;
        }
    }
    while(cur<=r*c)
    {
        linear[cur] = k;
        cur++;
    }
    for (int i = 1; i<=r; i++)
    {
        for (int j = 1; j<=c; j++)
            printf("%c",ans[linear[arr[i][j]]]);
        printf("\n");
    }
}
int32_t main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
}

 

 

Round 601 Problem B. Send Boxes to Alice

$n$ 개의 더미들 ($a_1, a_2, \cdots a_n$) 이 있고, 이들을 적당히 모아서 각각의 더미가 어떤 1이 아닌 소인수를 공유하도록 하고 싶다. 즉, 만약 $3, 1, 2, 3, 3$ 형태라면 1을 2 쪽으로 몰아서 $3, 0, 3, 3, 3$ 으로 만들 수 있고, 이들은 3의 배수가 되므로 성공. 한 개의 초콜릿을 한 칸 옮길때 1의 시간이 들고, 최소 시간에 하고 싶다.

 

자명하게, 소인수 $k$ 는 $\sum a_i$ 의 약수이다. 이때 소인수는 많아야 15개 정도이므로, 각각의 소인수에 대해 수백만 정도의 연산으로 빠르게 판정할 수 있으면 된다. 

 

소인수 $k$ 가 답임을 미리 정했다고 하자. 이때, 더 멀리 있는 더미끼리 합치는 것은 의미가 없고, 연속한 segment를 적절히 맞춰서 합치면 된다. 예를 들어, 답이 2가 되도록 하고 싶다면 $3, 1, 2, 3, 3$ 을 $1, 1, 0, 1, 1$ 로 바꾸고, 앞의 1 두개와 뒤의 1 두개를 합치면 된다. 

 

합치는 데 드는 최소 비용은 전체 배열의 가중 중간값 (나머지가 4라면 그 자리를 4번 생각) 으로 합쳐야 하고 (귀류법으로 증명할 수 있다) 각 소인수에 대해 합쳐 보고 최선의 값을 골라내면 된다.

#include <bits/stdc++.h>
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;
int choco[1010100];
int tmpchoco[1010100];
int total, tmp;
vector <int> pf;
int resolve_choco(vector <pii> &cur, int lpf)
{
    int u = 0;
    int target = 0;
    for (auto it:cur)
    {
        u += it.second;
        if (u >= (lpf+1)/2)
        {
            target = it.first; break;
        }
    }
    int res = 0;
    for (auto it:cur) res += (abs(it.first-target)*it.second);
    return res;
}
int32_t main()
{
    usecppio
    int n;
    cin >> n;
    for (int i = 1; i<=n; i++)
    {
        cin >> choco[i];
        total += choco[i];
    }
    if (total == 1)
    {
        cout << -1 << '\n';
        return 0;
    }
    tmp = total;
    for (int i = 2; i*i<=total; i++)
    {
        if (tmp%i==0)
        {
            while(tmp%i==0)
                tmp/=i;
            pf.push_back(i);
        }
    }
    if (tmp>1)
        pf.push_back(tmp);
    int fans = LLONG_MAX;
    for (int lpf:pf)
    {
        int ans = 0;
        vector <pii> mvs;
        int cur = 0;
        for (int i = 1; i<=n; i++)
        {
            tmpchoco[i] = choco[i]%lpf;
            if (tmpchoco[i])
            {
                if (cur + tmpchoco[i]>=lpf)
                {
                    mvs.push_back({i,lpf-cur});
                    tmpchoco[i] -= lpf-cur;
                    ans += resolve_choco(mvs, lpf);
                    mvs.clear();
                    mvs.push_back({i,tmpchoco[i]});
                    cur = tmpchoco[i];
                }
                else
                {
                    mvs.push_back({i,tmpchoco[i]});
                    cur += tmpchoco[i];
                }
            }
        }
        fans = min(fans, ans);
    }
    cout << fans << '\n';
}

 

Round 601 Problem C. Point Ordering

$n$ 개의 점으로 이루어진 볼록 $n$각형에 대해 다음과 같은 두 종류의 쿼리를 쓸 수 있다.

- $1\ i\ j\ k$ 쿼리는 $\overrightarrow{P_i P_j}$ 와 $\overrightarrow{P_i P_k}$ 의 외적의 절대값을 반환한다.

- $2\ i\ j\ k$ 쿼리는 $\overrightarrow{P_i P_j}$ 와 $\overrightarrow{P_i P_k}$ 의 외적의 부호를 반환한다.

 

이러한 쿼리 $3n$ 개를 써서 점들을 반시계 방향으로 정렬된 순서를 찾으려고 한다.

 

먼저, $\overrightarrow{P_1 P_n}$ 과 $\overrightarrow{P_1 P_i}$ 의 외적의 값과 부호를 모두 알아내자. 이를 위해서는 $2n-4$ 개의 쿼리를 필요로 한다. 이때 외적의 부호가 +이면 1-n 사이 선분의 위쪽에 있고, -이면 아래에 있다. 

이제, 추가로는 + 부분에서 가장 멀리 있는 점 (외적 절댓값을 이용하면 찾을 수 있다) 을 하나 잡자. 이 점을 $A$ 라고 하고, $\overrightarrow{P_1 P_A}$ 와 다른 + 구간의 점들 간의 외적 부호를 찾는다. - 부분에서도 가장 먼 점 $B$를 잡고 똑같은 과정을 수행할 수 있다. 

이제 4개의 구간으로 나누었을 때, 다음과 같은 순서로 정렬하면 점들이 반시계 방향 정렬되게 된다.

(1) , (-- 구간의 점들을 $\overrightarrow{P_1 P_n}$ 에 가까운 순서대로 나열) , (가장 먼 - 점 B), (-+ 구간의 점들을 먼 순서대로 나열), (n), (+- 구간의 점들을 가까운 순서대로 나열), (가장 먼 +점 A), (++ 구간의 점들을 먼 순서대로 나열)

#include <bits/stdc++.h>
#define ll long long
#define all(x) ((x).begin()),((x).end())
using namespace std;
#define int ll
using pii = pair<int, int>;

int n;
int farplus = -1, farminus = -1;
int n1pos[1010];
double n1area[1010];
vector <int> c1nplus,c1nminus, c1nplusplus, c1nplusminus, c1nminusplus, c1nminusminus;
bool comp_area(int &a, int &b)
{
    return n1area[a]<n1area[b];
}
int32_t main()
{
    scanf("%lld",&n);
    for (int i = 2; i<n; i++)
    {
        printf("2 1 %lld %lld\n",n,i);
        fflush(stdout);
        int sgn = 0;
        scanf("%lld",&sgn);
        n1pos[i] = sgn;
        (sgn==1)?c1nplus.push_back(i):c1nminus.push_back(i);

        printf("1 1 %lld %lld\n",n,i);
        fflush(stdout);
        double A = 0;
        scanf("%lf",&A);
        n1area[i] = A;
    }
    sort(all(c1nplus),comp_area);
    if (!c1nplus.empty())
    {
        farplus = c1nplus.back();
        c1nplus.pop_back();
        for (auto it:c1nplus)
        {
            printf("2 1 %lld %lld\n",farplus,it);
            fflush(stdout);
            int sgn = 0;
            scanf("%lld",&sgn);
            (sgn==1)?c1nplusplus.push_back(it):c1nplusminus.push_back(it);
        }
        sort(all(c1nplusplus),comp_area);
        reverse(all(c1nplusplus));
        sort(all(c1nplusminus),comp_area);
    }
    if (!c1nminus.empty())
    {
        sort(all(c1nminus),comp_area);
        farminus = c1nminus.back();
        c1nminus.pop_back();
        for (auto it:c1nminus)
        {
            printf("2 1 %lld %lld\n",farminus,it);
            fflush(stdout);
            int sgn = 0;
            scanf("%lld",&sgn);
            (sgn==1)?c1nminusplus.push_back(it):c1nminusminus.push_back(it);
        }
        sort(all(c1nminusplus),comp_area);
        reverse(all(c1nminusplus));
        sort(all(c1nminusminus),comp_area);
    }
    printf("0 1 ");
    for (auto it:c1nminusminus)
        printf("%lld ",it);
    if (farminus>0)
        printf("%lld ",farminus);
    for (auto it:c1nminusplus)
        printf("%lld ",it);
    printf("%lld ",n);
    for (auto it:c1nplusminus)
        printf("%lld ",it);
    if (farplus>0)
        printf("%lld ",farplus);
    for (auto it:c1nplusplus)
        printf("%lld ",it);
    printf("\n"); fflush(stdout);
}

---

Round 616 B, C는 일단 B부터 substring에 대한 문제기도 했고 뭔가 잘 모르겠길래 던졌다. 언젠가 다시 풀어봐야지...

 

그래도 601B가 비교적 수학 문제고, 601C가 기하 계열 문제라서 균형은 대충 맞는 셋이었던것 같다. :frozen_thinking_face: 언젠가 다시 풀어봐야지...