Little Piplup 6월 21일 팀 연습

시험 기간이라 잘 돌지 못했는데, 시험 끝나고 나서 Road to Grandmaster 셋으로 4시간짜리 연습을 돌았다.

 

RTG는 1700~2400난이도 문제들을 적당히 잘 매시업해서 매주 진행되는 연습인데, 대략적인 난이도가 엥간한 대회에서 최고난도 문제 한두개와 최하 난이도 문제 한두개를 뺀 느낌인데다가 12문제, 4시간 등 포맷이 실제 대회랑 보다 비슷하고, 무엇보다 문제 난이도를 번호로부터 유추할 수 없다는 장점이 있어서 앞으로 연습 셋으로 애용할 듯 하다.

 

문제번호	A	B	F	G	H	J
문제 레이팅	2000	1900	1700	1900	1800	2000
Solve time	02:00 (+1)	01:28	00:14	00:30	03:29 (+6)	00:59

---

(문제 번호는 푼 순서)

 

F. Dima and Lisa

Solution : Coffeetea, Gratus907, Diordhd

Code : Gratus907

 

홀수 $n$을 3개 이하의 소수의 합으로 표현하는 문제. 

약한 골드바흐의 추측에 따르면, 7 이상의 홀수는 세 소수의 합으로 항상 표현할 수 있다. 또한, 3과 5는 소수이므로, 사실 2개의 소수는 필요가 별로 없고... 약한 골드바흐 추측은 참임이 증명되었으므로 잘 쓸 수 있겠다.

Coffeetea가 문제를 보자마자 "소수 간 간격이 얼마나 되냐" 라고 물었고, 나랑 Diordhd가 "충분히 작다. 아마 10억까지 소수에서 천 넘는게 없을 것 같긴 한데, 넉넉히 한 2천 잡으면 되지 않을까?" 라고 생각했고, 바로 세명다 비슷한 솔루션에 도달했다.

$n$보다 작은 최대의 소수 $p$를 찾으면, $n-p$의 값은 어떤 적당히 작은 값 (2천이라고 믿었다) 을 넘지 않는다.

미리 2천까지의 모든 소수를 구해 놓고, 이제 남은 짝수를 두 소수의 합으로 나타내어 주면 된다. (이것도 아직 증명되지는 않았지만 골드바흐 추측에 의하면 되어야 하고, 골드바흐 추측은 매우 큰 수까지 반례가 없으므로 믿어도 좋다) 

3, 5 같은 케이스를 매뉴얼하게 처리해 버렸기 때문에 코드는 상당히 길지만, 핵심적인 생각은 단순하다.

#include <bits/stdc++.h>
using namespace std;
int n;
bool smallprime[2020];
vector <int> primes;
bool is_prime(int p)
{
    if (p<2)
        return 0;
    if (p==2 || p==3 || p==5)
        return 1;
    int u = (int)(sqrt(p)+0.5);
    for (int i = 2; i<=u; i++)
    {
        if (p%i==0)
            return 0;
    }
    return true;
}
int main()
{
    scanf("%d",&n);
    if (n==3)
    {
        printf("1\n3");
        return 0;
    }
    else if (n==5)
    {
        printf("1\n5");
        return 0;
    }
    else if (is_prime(n))
    {
        printf("1\n%d",n);
        return 0;
    }
    else if (is_prime(n-2))
    {
        printf("2\n2 %d",n-2);
        return 0;
    }
    int p1 = n-4;
    for (int i = 2; i<=2000; i++)
    {
        bool a = is_prime(i);
        smallprime[i] = a;
        if (a)
            primes.push_back(i);
    }
    while(!is_prime(p1))
    {
        p1 = p1 - 2;
    }
    for (auto it:primes)
    {
        if (smallprime[n-p1-it])
        {
            printf("3\n%d %d %d",p1,it,n-p1-it);
            return 0;
        } 
    }
}

여담으로, 2천이라는 바운드는 별 생각 없이 잡았지만, Strong Cramer's Conjecture에 따르면 인접한 소수 간의 차는 $p$가 커짐에 따라서 $\log^2 p$ 정도로 잡힌다고 한다. 그리고 실제로 10억 미만의 소수 중 가장 큰 gap은 282라고 한다(2천까지도 필요 없었다!)

---

G. Optimal Number Permutation 

Solution : Coffeetea, Gratus907, Diordhd

Code : Gratus907

1부터 $n$ 까지의 숫자가 두번씩 주어질 때, 이 배열을 재배열한다고 하자. 그러면 같은 숫자가 두 번씩 나올 텐데, 각각의 $i$에 대해서 $i$가 나오는 위치를 $x_i$, $y_i$ 라고 하자. ($y_i > x_i$). 그리고 $y_i - x_i = d_i$ 로 정의하자.

다음 값을 최소화하는 재배열을 찾아야 한다.

$$S = \sum_{i = 1}^{n} (n - i) \cdot |d_i + i - n|$$

Coffeetea가 처음에 "항상 0으로 맞출 수 없나?" 라는 얘기를 했고, 내가 잘 Construct해서 다음과 같은 결과를 얻었다.

$n = 5$ 일 때를 예로 들면,

1 3 5 3 1 2 4 4 2 5

이런 식으로 배열하면 1과 1 사이 거리가 4, 2와 2 사이 거리가 3, ... 하기 때문에, 항상 모든 값이 0이 된다.

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

vector <int> v;
int main()
{
    int n;
    cin >> n;
    if (n%2)
    {
        for (int i = 1; i<=n; i+=2)
            v.push_back(i);
        for (int i = n-2; i>=1; i-=2)
            v.push_back(i);
        for (int i = 2; i<n; i+=2)
            v.push_back(i);
        for (int i = n-1; i>0; i-=2)
            v.push_back(i);
        v.push_back(n);
    }
    else 
    {
        for (int i = 1; i<n; i+=2)
            v.push_back(i);
        for (int i = n-1; i>=1; i-=2)
            v.push_back(i);
        for (int i = 2; i<=n; i+=2)
            v.push_back(i);
        for (int i = n-2; i>0; i-=2)
            v.push_back(i);
        v.push_back(n);
    }
    for (auto it:v)
    {
        printf("%d ",it);
    }
}

---

J. Random Query

Solution : Diordhd, Coffeetea, Gratus907

Code : Gratus907

뭔가 내가 계속 컴퓨터를 잡게 되긴 했는데, 실제 구현 시간은 여기까지가 대략 1시간 이었다. 수학 구현은 대부분 내가 하게 되는 것 같은데, 우리 팀 기본 전략이 뭔가 수식 중심의 짧은 문제부터 들어가는 거였기 때문에 초반에 내가 구현을 많이 하게 되었다. 

$n$개 짜리 배열에서, 어떤 적당한 Window를 잡자. ($l_i, r_i$ 의 Subarray를 Window라고 표현하였다) 

이때, Window 안에서 서로 다른 원소의 개수를 셀 수 있을 것이다. (1 1 2 3 1 1 이 잡히면 3개)

이 기댓값을 구하는 문제.

 

$a_i$ 가 10만 이하임에 착안하여, 각각의 원소가 갖는 Contribution을 계산할 수 있다. 즉, 전체 window의 수 $n^2$ 개 중, 이를테면 3을 포함하지 않는 Window가 몇 개인지를 빠르게 셀 수 있기 때문에, 이걸 통해서 각 원소를 포함하는 Window의 수를 세고, 이걸 10만개에 대해 모두 반복한 다음 마지막에 $n^2$ 으로 나눠주면 기댓값이 나온다.

 

우리팀의 비교적 확실한 강점 (수학) 이 가장 잘 드러나는 문제인 것 같다.

#include <bits/stdc++.h>
#define int long long 
#define MAX(a,b) (a)>(b)?(a):(b)
#define ll long long
using namespace std;

vector <int> v[1001000];

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        v[x].push_back(i+1);
    }
    int ans = 0;
    for (int i = 0; i<1001000; i++)
    {
        int gapsum = 0;
        int u = v[i].size();
        if (u==0)
            continue;
        if (u>1)
        {
            for (int j = 1; j<u; j++)
            {
                int k = (v[i][j]-v[i][j-1])-1;
                gapsum+=k*k;
            }
        }
        gapsum += (v[i][0]-1)*(v[i][0]-1);
        gapsum += (n-v[i][u-1])*(n-v[i][u-1]);
        ans += (n*n-gapsum);
    }
    setprecision(9);
    cout << (ans*1.0/(n*n*1.0));
}

---

B. Dense Subsequence 

Solution : Diordhd, Coffeetea

Code : Coffeetea

내가 J번 코딩하는동안 둘이 다 풀어놨다.

사실 풀이 이해도 잘 안가고, 어떻게 짠건지도 잘 이해가 안가고.. 잘 짜려니 하고 믿고 A번 풀러 갔었다. 

아무튼 문제는, 문자열 S가 들어왔을 때, 이중 부분문자열의 재배열 T를 잡아서, S의 길이가 k인 모든 window가 T의 원소를 적어도 하나 이상 포함하게 하는 문제이다. 이때, 사전 순으로 가장 앞서는 T를 찾아야 한다.

 

핵심 발상은, 만약 a를 적어도 하나 뽑을 거라면, 가능한 a를 모두 다 뽑는게 이득이라는 점이다. (포함되는 window가 줄어들지 않으면서 사전순으로 앞서게 된다) 그래서, a를 다 뽑아서 되는지? b를 다 뽑아서 되는지? ... 하면서 확인한 다음, 예를 들어 d를 다 뽑았더니 된다! 라고 하면, 그때부터 d를 줄이면서 d가 실제 몇개 필요한지 찾으면 된다. 

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

int poham[30];          //0: 미포함 1: 현재 체크 중 2: 이미 들어가는 거 확정
int getsoo[30];
int pick[30];
char ch[100005];

int main(){
    int m;
    scanf("%d", &m);
    scanf("%s", ch);
    int len = strlen(ch);
    for (int i = 0 ; i < len ; ++i ) {
        ++getsoo[ch[i]-'a'];
    }
    for (int i = 0 ; i < 26 ; ++i ) {       //현재 체크하는 알파벳 = i번
        if ( getsoo[i] ) {
            poham[i] = 1;
            int cur = -1;
            int lim = m-1;

            bool possible = true;
            while(lim < len) {

                bool go = false;
                bool go2 = false;
                for ( int temp = lim ; temp > cur ; --temp ) {
                    if ( poham[ ch[temp] - 'a' ] == 2 ) {
                        cur = temp;
                        lim = cur + m;
                        go = true;
                    }
                }
                if ( !go ) {
                    for ( int temp = lim ; temp > cur ; --temp ) {
                        if (  ch[temp] - 'a' == i ) {
                            ++pick[i];
                            cur = temp;
                            lim = cur + m;
                            go2 = true;
                        }
                    }
                    if ( !go2 ) {
                        poham[i] = 2;
                    }
                }
                if ( !go && !go2 ) {
                    possible = false;
                    break;
                }
            }
            if ( possible ) {
                break;
            }
        }
    }
    for ( int i = 0 ; i < 26 ; ++i ) {
        if ( poham[i] == 2) {
            int k = getsoo[i];
            while(k--) printf("%c", 'a' + i);
        } else if ( poham[i] == 1 ) {
            int k = pick[i];
            while(k--) printf("%c", 'a' + i);
        }
    }
}

---

A. Sockets 

Solution : Diordhd, Gratus907

Code : Gratus907

$x$짜리 소켓에는 $x$짜리 컴퓨터만 꽂을 수 있다. 어댑터 1개를 소켓에 꽂으면 출력이 $ceil(\frac{x}{2})$ 로 바뀐다. 

몇개의 어댑터를 어떻게 꽂아야 최대한 많은 컴퓨터에 전기를 공급할 수 있을까? 단, 같은 개수의 컴퓨터에 전력 공급이 가능하다면 어댑터의 사용 개수를 최소화 해야 한다.

 

의외의 그리디 전략이 먹히는데, 가장 작은 파워의 소켓부터 파워를 계속 줄여 나가면서, 하나라도 연결할 수 있는 컴퓨터가 있으면 바로 끊고 연결해 버리면 된다. 이게 되는 이유는 처음 소켓 파워가 정해지면 어댑터를 몇개 꽂는지에 따라 나오는 숫자가 유일하기 때문. 이걸 잡고 가면 코딩 자체는 그럭저럭.. 일줄 알았는데, Multimap 사용을 개못해서 엄청오래걸렸다.

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
using namespace std;
int n, m;
int c, u;
multimap <int, int> computer_by_index;
int oneoper(int start)
{
    return (int)(start*1.0/2 + 0.5);
}

vector <pair <int, int>> socket;
int cpind[202020];
int arr[202020];
int count_operation(int s, int sind)
{
    int ss = s;
    int op = 0;
    while(ss>1)
    {
        auto it = computer_by_index.find(ss);
        if (it != computer_by_index.end())
        {
            pair <int, int> data = *it;
            cpind[data.second] = sind;
            computer_by_index.erase(it);
            return op;
        }
        op++;
        ss = oneoper(ss);
    }
    auto it = computer_by_index.find(ss);
    if (it != computer_by_index.end())
    {
        pair <int, int> data = *it;
        cpind[data.second] = sind;
        computer_by_index.erase(it);
        return op;
    }
    if (ss == 1)
        return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        computer_by_index.insert({x,i+1});
    }
    for (int i = 0; i<m; i++)
    {
        int x;
        cin >> x;
        socket.push_back({x,i+1});
    }
    sort(socket.begin(),socket.end());

    for (auto it:socket)
    {
        int ct = count_operation(it.first, it.second);
        u += ct;
        arr[it.second] = ct;
    }

    int c = n - computer_by_index.size();

    cout << c << ' '<< u << '\n';

    for (int i = 1; i<=m; i++)
    {
        cout << arr[i] << " ";
    }
    cout << '\n';
    for (int i = 1; i<=n; i++)
    {
        cout << cpind[i] << " ";
    }
    cout << '\n';
}

 

심지어 구현 실수로 find, count 너무 많이 써서 TLE 받았다가 O3, Ofast 붙이고 상수줄여서 맞았다.

:uwek:

---

H. E-mail Addresses

Solution : Diordhd, Gratus907

Code : Gratus907

이메일 주소 규칙을 보며, 주어진 String에서 Vaild E-mail Address인 Substring의 개수를 센다.

@를 기점으로, 좌우로 포인터를 보내면서 시작점과 끝점이 될 수 있는 원소의 개수를 세면 되는데

 

꼼꼼한 구현을 개못하는 내가 어쩌다 이걸 잡아서 무려 6틀했다.

Coffeetea가 잡았어야 하는데... 어쩌다 그렇게 된거냐면, 내가 A번 구현 하는 동안 Coffeetea랑 Diordhd가 I번을 풀려고 시도했고, Coffeetea가 I번 구현하는 동안 나랑 Diordhd가 H번 솔루션이 생각나서, I번 WA가 났을 때 물어보니 로직에 문제가 있는 것 같다길래 두명 I번 생각하게 하고 내가 H번 코딩을 잡았다.

그리고 첫 제출부터 디버깅까지 무려 30분이 걸렸다.

#include <bits/stdc++.h>
#define int long long
#define ll long long
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
using namespace std;

bool is_alphabet(char c)
{
    return ('a' <= c) & (c <= 'z');
}

bool is_number(char c)
{
    return ('0' <= c) & (c <= '9');
}
char str[1010100];
vector <int> ind;

int check_each(int x)
{
    int pt1 = x-1;
    int ct1 = 0;
    int pt2 = x+1;
    int ct2 = 0;
    while(str[pt1])
    {
        if (str[pt1]=='.' || str[pt1] == '@')
            break;
        if (is_alphabet(str[pt1]))
        {
            pt1--;
            ct1++;
        }
        else if (is_number(str[pt1]) || str[pt1]=='_')
        {
            pt1--;
        }
    }
    //cout << ct1 << endl;
    if (str[pt2]=='.' || str[pt2]=='@' || str[pt2]=='_')
        return 0;
    while(str[pt2]!='.' && str[pt2])
    {
        pt2++;
        if (str[pt2]=='@' || str[pt2]=='_' )
        {
            return 0;
        }
    }
    pt2++;
    while(str[pt2])
    {
        if (str[pt2]=='.' || str[pt2] == '@')
            break;
        if (is_alphabet(str[pt2]))
        {
            pt2++;
            ct2++;
        }
        else if (is_number(str[pt2]) || str[pt2]=='_')
        {
            break;
        }
    }    
    //cout << ct2 << endl;
    return ct1*ct2;
}
int32_t main()
{
    scanf("%s",str+1);
    int len = strlen(str+1);
    for (int i = 1; i<len; i++)
    {
        if(str[i] == '@')
            ind.push_back(i);
    }
    int ans = 0;
    for (auto it:ind)
    {
        ans += check_each(it);
    }
    cout << ans;
    return 0;
}

---

풀이 실패한 문제들

D : Segtree로 잘 세는 문제 같이 보이고, 짧아서 다른문제 푸는 틈틈이 계속 봤는데 답이 안보였다. 

나중에 알고보니 Persistent Segment Tree라는, 내가 모르는 자료구조를 쓰는 2400 문제였다.

 

I : 단순 그리디로 될거 같은데 왜 $N = 3000$ 밖에 안되지? -> 단순 그리디가 안 되기 때문이다.

I번에 날린 시간이 거의 3~40분 이상인 것도 문제지만, 사실 그보다 이거때문에 내가 H번 코딩을 잡고 6틀한게...

---

후기

짧은 문제가 수학을 많이 요구하는 경향이 많으므로, 난이도가 비슷하다면 짧은 문제부터 읽는다 라는 전략은 우리 팀한테는 매우 유용한 것 같다. 다만 문제는, 짧지만 어려운 문제나, 지나치게 높은 난이도의 수학 문제가 우리 팀에게 늪이 되어 버릴 우려가 있다는 점이다. 특히 빡센 수학 문제는 '뭔가 풀릴거 같은데' 라는 상태로 끝없이 시간이 갈 우려가 좀 있다.

내가 구현을 너무 많이 맡았다. 초반 FGJ 구현을 내가 한 것까지는 괜찮았는데, 적어도 A랑 H번 중 하나는 내가 하지 말았어야 했다. 후반에는 코딩하는 사람이 집중력이 매우 후달리다 보니 상당히 힘든데, 페어코딩이 안되는 우리팀으로서는...

뭔가 그래프나 이런 문제가 적어서, Coffeetea가 나보다 구현을 현저히 잘하는 것은 아니기 때문에 (그래프, 문자열 등은 확실히 잘한다) 그냥 되는 사람이 맡았는데, Coffeetea가 I번에 휘말려서 다른문제 구현을 맡아주질 못했다. 빨리 Diordhd가 구현연습 빡세게 돌아서 나랑 코딩 비중을 좀 나눠가져야 하는데, 아마 내가 3주정도 유럽 여행을 다녀올 예정이니 그동안 연습하면 확연히 나아질것 같아서 UCPC때 쯤에는 좀 나을 것 같다. 

별개로 RTG셋 자체는 너무 좋은 것 같다. 팀연습 돌때 매우 유용하게 써먹을듯...