Codeforces Round 561 (Div. 2) 후기/풀이

이제 막 System Test 까지 끝난 라운드인데, 지금까지 뛰어본 코포 라운드 중 가장 큰 레이팅 상승을 받았다 :)

:dhk:

전반적으로 수학적인 센스가 약간 필요했던 라운드라는 생각이 든다. 

다른거보다 가장 마음에 드는건, 지난 몇번 라운드가 계속

40분만에 3~4문제 해결 -> 1시간 20분동안 멍때림 -> Hack이나 Systest Fail로 떡락

이 루틴을 따라가서 매우 재미가 없었는데, 오늘은 라운드 끝까지 계속 Active하게 참여할 수 있었다.

---

스포방지

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

A. Silent Classroom

[문제]

이름의 앞자리를 기준으로 각 글자당 학생의 수를 센 다음, 

\[_{\frac{n}{2}}C_{2}\]

를 잘 계산해 준다. 홀짝에 따라서 실제로는 3이면 1, 2 식으로 나눠줘야 하지만.

 

코드

 

#include <bits/stdc++.h>
#define MAX(A,B) ((A)>(B)?(A):(B))
using namespace std;

int occ[26];
int comb2(int n)
{
    return MAX(n*(n-1)/2,0);
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i<n; i++)
    {
        char str[120];
        scanf("%s",str);
        occ[str[0]-'a']++;
    }
    int ans = 0;
    for (int i = 0; i<26; i++)
    {
        ans+=(comb2(occ[i]/2));
        ans+=(comb2(occ[i]-occ[i]/2));
    }
    printf("%d",ans);
}

 

---

B. All the Vowels Please

[문제]

약간 당황했었는데...

aeiouaeio

eiouaeiou

iouaeioua

...

이런식으로 써주면 된다. 그런데, 만약 행이나 열의 수가 5보다 작다면 불가능하므로, $\sqrt{n}$에 가장 가까운 약수를 찾아서 그걸 기준으로 배열해 주자.

 

#include <bits/stdc++.h>
#define MIN(A,B) ((A)<(B)?(A):(B))
using namespace std;

typedef pair<int,int> pii;
typedef pair<int,string> pis;
typedef pair<int,double> pid;

string vowel = "aeiou";

char word[1000][1000];
int main()
{
    int n;
    scanf("%d",&n);
    int a = 1, b = n;
    for (int i = 1; i*i<=n; i++)
    {
        if (n%i==0)
        {
            a = i;
            b = n/i;
        }
    }
    if (MIN(a,b)<5)
        printf("-1");
    else
    {
        for (int i = 0; i<a; i++)
            for (int j = 0; j<b; j++)
                printf("%c",vowel[(i+j)%5]);
    }
}

 

---

C. A Tale of Two Lands

[문제]

그냥 수학 문제

정수들이 20만개 주어지고, 이 정수들 중에서 2개를 뽑아서 각각을 $a$, $b$ 라고 할 때,

 

이 식을 성립시키면 된다.

 

어차피 우리에게 중요한 것은 원래 식의 값이 아니라 절댓값과 대소만이므로,

일단 각 숫자의 절댓값만을 쭉 가져오자. 부호는 신경쓸 필요가 없다. 그러고 나서, 핵심적인 발상은 

 

"$a$를 고정했을 때, 어떤 $b$ 들이 이 문제의 해가 되는가?" 이다.

 

부등식을 열심히 풀어보면, 절댓값이 $\frac{|a|}{2}$ 보다 크고, $2|a|$ 보다 작은 값들이 해가 된다는 사실을 파악할 수 있다. 이것들을 binary search를 통해, 해가 되는 개수를 세 주자.

 

이 작업은 결국 binary search 두 번이므로, $\mathcal{O}(\log n)$ 시간에 동작한다. 이 작업을 모든 $a$ 에 대해 수행해야 하는데, 한 순서쌍을 모두 두 번씩 셌으므로, 2로 나누어 주면 끝.

 

Overall Complexity : $\mathcal{O}(n \log n)$

 

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

ll lid(int size, int val)
{
    int l = 0, h = size - 1;
    while (l <= h)
    {
        int mid = (l + h) / 2;
        if (positions[mid] >= val)
            h = mid - 1;
        else
            l = mid + 1;
    }
    return l;
}
ll uid(int size, int val)
{
    int l = 0, h = size - 1;
    while (l <= h)
    {
        int mid = (l + h) / 2;
        if (positions[mid] <= val)
            l = mid + 1;
        else
            h = mid - 1;
    }
    return h;
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        positions.push_back(abs(x));
    }
    sort(all(positions));
    ll ans = 0;
    for (int i = 0; i<n; i++)
    {
        ll low = lid(positions.size(),abs(positions[i]+1)/2);
        ll high = uid(positions.size(),abs(positions[i])*2);
        ans+=(high-low);
    }
    printf("%lld",ans/2);

}

---

D. Cute Sequences

[문제]

하나도 안 Cute 하다.

$i$번째 항이 $i-1$번째 항까지의 누적합보다 최소 1, 최대 $m$만큼 더 클 수 있을 때, $a$로 시작해서 $b$ 로 끝나는 수열을 찾는 문제.

 

초항 $a$에 대해서, $n$ 번째 항의 최소값과 최댓값을 찾자.

먼저, 모든 항에서 +1을 고른다면 (즉, 증가분을 최소화한다면) 

$x_2 = x_1 + 1$

$x_3 = x_2 + x_1 + 1 = 2x_1 + 2$ 

이런식으로 나아가게 되고, 

$x_n = x_1 * (2^{n-2}) + (2^{n-2})$ 가 최솟값이다.

 

비슷한 방법으로 $m$만 계속 고르면 (즉, 증가분을 최대화하면)

$x_n = x_1 * (2^{n-2}) + m(2^{n-2})$ 가 최댓값이다.

 

그 안에 있는 모든 수를 다 만들어 줄 수 있긴 한데... 어떻게 만들어야 하는지를 생각해 보자.

 

5번째 항을 가정하면, 1~5번째까지 각각 이렇게 쓸 수 있다.

$x_1, x_1+r_2, x_2+x_1+r_3 = 2x_1+r_2+r_3 , 4x_1 + 2r_2 + r_3 + r_4, 8x_1 + 4r_2 + 2r_3 + r_4 + r_5$

잘 관찰해 보면 현재로부터 j번 전에 더해졌던 항은 $2^{j-1}$ 만큼의 가중치가 곱해진다는 점을 알 수 있다.

이것을 이용해서, 앞에서부터 최대한의 가중치를 갖도록 그리디하게 만들어주면 끝.

 

Overall Complexity :  일단 쿼리는 개별적으로 처리하는데, 쿼리가 $q$ 개. $a b m$은 $10^14$까지지만, 어차피 가능한 최대 항의 개수는 $\log(\frac{b}{a})$ 개 정도밖에 안된다. 즉 최대 $\log b$ 정도.

$\mathcal{O}(q \log b)$ 

 

#include <bits/stdc++.h>
#define ll long long
#define MAX(A,B) ((A)>(B)?(A):(B))
#define MIN(A,B) ((A)<(B)?(A):(B))
#define MP make_pair
#define PB push_back
using namespace std;
typedef pair<ll, ll> pll;
ll maxi, mini;
inline ll pow2(ll x)
{
    ll ans = (1<<(x/3));
    ans *= (1<<(x/3));
    ans *= (1<<(x-x/3-x/3));
    return ans;
}

pll maxminval(ll n, ll x1, ll m)
{
    return MP((pow2(n-2)*x1+pow2(n-2)),(pow2(n-2)*x1+pow2(n-2)*m));
}

ll arr[60];
ll rem[60];
int main()
{
    int q;
    scanf("%d",&q);
    while(q--)
    {
        memset(arr,0,sizeof(arr));
        memset(rem,0,sizeof(rem));
        ll a, b, m;
        scanf("%lld %lld %lld",&a,&b,&m);
        ll n = 2;
        bool flag = 0;
        if (a==b)
        {
            printf("1 %lld\n",a);
            continue;
        }
        while(a<=b)
        {
            pll range = maxminval(n,a,m);
            if (range.first>b)
            {
                flag = 0;
                break;
            }
            if (range.first<=b && b <= range.second)
            {
                flag = 1;
                break;
            }
            if (n>50)
            {
                flag = 0;
                break;
            }
            n++;
        }
        if (!flag)
        {
            printf("-1\n");
            continue;
        }
        else
        {
            if (n == 2)
            {
                printf("2 %lld %lld\n",a,b);
                continue;
            }
            arr[1] = a;
            for (int i = 2; i<=n; i++)
                arr[i] = a*(pow2(i-2));
            ll gap = b-(a*pow2(n-2));
            for (int i = 2; i<=n; i++)
                rem[i] = 1;
            gap -= pow2(n-2);
            for (int i = 2; i<=n-1; i++)
            {
                ll r = gap/(pow2(n-i-1));
                r = MIN(m-1,r);
                rem[i] += r;
                gap -= r*(pow2(n-i-1));
            }
            if (gap)
            {
                rem[n] += gap;
                gap = 0;
            }
            for (int i = 2; i<=n; i++)
                for (int j = 2; j<i; j++)
                    arr[i] += rem[j]*(pow2(i-j-1));
                arr[i] += rem[i];

            printf("%lld ",n);
            for (int i = 1; i<=n; i++)
                printf("%lld ",arr[i]);
            printf("\n");
        }
    }
}

---

E. The LCMs Must be Large

 

[문제]

1~$n$까지의 숫자들($n \leq 10000$)의 부분집합 $A_i$ 들이 $m$개 주어질 때,

다음 조건을 만족하는 수열 $x_i$ 의 존재성을 판별해야 한다.

$$lcm(x_{A_i}) > lcm(x_{A_i^c})$$

(단, $x_{A_i}$ 는 수열 $x_i$ 에서, 인덱스가 $A_i$의 원소인 것들의 집합)

 

라운드 중에는 다음과 같이 생각했다.

"불가능한 경우, 즉, $A_i$ 가 $A_j^c$의 부분집합인 경우 외에는 다 될 것이다"

 

예를 들어, 다음과 같은 경우를 보자.

$n = 4$ 일 때,

$A_1 = {1, 2}$

$A_2 = {2, 3}$

$A_3 = {1, 2, 4}$

수열을 7,5,7,2 같은걸로 잡아주면 조건을 만족한다.

 

그러나, 같은 $n = 4$에서,

$n = 4$ 일 때,

$A_1 = {1, 2}$

$A_2 = {3, 4}$

이 경우는 불가능하다. $lcm(x_1, x_2) > lcm(x_3, x_4) > lcm(x_1, x_2)$ 가 되기 때문.

 

라운드 중에는 intuition만 갖고 일단 코딩을 하면서 생각을 해보긴 했는데...

 

먼저, $m$개의 서로소인 수 ($m$개의 소수면 충분하다!) 를 적당히 가져오자. 이것들을 각각 $p_1, p_2, ... p_m$ 이라고 하자.

$x_i$ 는 다음과 같이 구성한다.

만약 $m$번째 집합에 $i$ 가 들어 있다면, $x_i$는 $p_m$을 곱하고, 들어 있지 않다면 1을 곱한다.

 

이렇게 구성된 수열로 위 방법을 돌려보면, 

"$A_i$ 가 $A_j^c$의 부분집합인 경우 외에는 다 될 것"이라는 주장이 옳음을 알 수 있다.

 

따라서, 모든 집합 $A_i, A_j$ 에 대해, $A_i \subset A_J^c$ 가 아닌지 확인한다.

이 작업은 최대 $\mathcal{O}(n)$ 시간이 걸리는데, $_mC_2$ 번 해야 하므로,

 

Overall Complexity : $\mathcal{O}(nm^2)$

 

#include <bits/stdc++.h>
using namespace std;

bool bb[51][10010];
int n,m;
bool comsub(int a, int b) // check if b is subset of complementary of a.
{
    for (int i = 0; i<10010; i++)
        if (bb[b][i])
            if (bb[a][i])
                return false;
    return true;
}

int main()
{
    scanf("%d %d",&m,&n);
    for (int i = 0; i<m; i++)
    {
        int s;
        scanf("%d",&s);
        for (int j = 0; j<s; j++)
        {
            int buy;
            scanf("%d",&buy);
            bb[i][buy] = 1;
        }
    }
    bool ans = true;
    for (int i = 0; i<m; i++)
    {
        for (int j = 0; j<m; j++)
        {
            if (comsub(i, j))
            {
                ans = false;
                break;
            }
        }
        if (!ans)
            break;
    }
    printf("%s",ans?"possible":"impossible");
}