Little Piplup 7월 19일 팀연습

여섯 번째 팀연습. 한 달 만에 진행하는 건데, UCPC 2019 예선을 위해 3PC로 진행했다.

문제번호	A	B	C	D	E	G	I	J
레이팅	1700	1900	2100	2000	1800	1900	2100	2200
AC 시간	00:55	02:30	03:37	01:19	00:39	03:10	02:50	03:57

 

특별히 재밌었던 문제인 C번은 나중에 따로 포스팅하고, 이 포스트에서는 AC 순서대로 (EADBIGJ) 간다.

 

---

E. Promocodes with Mistakes

Solution : Gratus907, Coffeetea

Code : Gratus907

처음에 무슨 문제를 잡는지가 중요한데, 내가 처음에 C를 '쉬운 문제' 로 착각해서 코딩하는 동안, Diordhd가 D를, Coffeetea가 E를 읽었고 내가 틀린다음 이게 쉬운 문제가 아님을 인지하고 바로 E로 넘어가서 코딩했다. 

주어진 문자열들의 배열에서 두 문자열 간의 편집 거리를 $dist(i, j)$ 라고 할 때, 이 값들의 최소값을 찾고, 그 값을 $a$ 라고 하자. 이때, $(a-1)/2$ 개의 오류가 있더라도, 우리는 원래 입력하려던 문자열이 무엇인지를 유일하게 정할 수 있다. 0개일 때 실수를 해서 한번 틀렸지만, 별로 어렵지는 않게 해결할 수 있었다. 

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
char code[1010][10];
 
int editdist(int a, int b)
{
    int ans = 0;
    for (int i = 0; i<6; i++)
        ans += (code[a][i]!=code[b][i]);
    return ans;
}

int main()
{
    usecppio
    int n;
    int ans = INT_MAX;
    cin >> n;
    for (int i = 0; i<n; i++)
        cin >> code[i];
    for (int i = 0; i<n; i++)
        for (int j = i+1; j<n; j++)
            ans = min(ans, editdist(i,j));
    cout << min((ans-1)/2,6);
}

---

A. Vasya and Chess

Solution : Diordhd

Code : Diordhd

읽어보고 뭔가 매우 어려울 거 같다는 생각에 던졌는데, 오히려 아니었다. (내 선구안이 상당히 별로임을 깨닫고 간다.)

$n \times n$ 체스판에서, $(1, n)$ 에 흑 퀸이, $(1, 1)$ 에 백 퀸이 위치하고, 그 외의 모든 공간은 아무나 잡을 수 있는 초록색 폰으로 가득 차 있다. 상대 퀸을 먼저 잡을 수 있으면 이긴다.

$n$에 따라 누가 이길지, 그리고 백이 이긴다면 필승전략을 위한 첫 수는 무엇인지를 찾으면 된다.

Diordhd가 좋은 관찰 하나로 문제를 뚝딱해버렸는데, "짝수일 때, 백이 어떻게 움직이든, 흑이 대칭으로 움직이면 언젠가 백이 먼저 가운데로 나올 수밖에 없다" 는 것이다. 따라서, 짝수일 때 반드시 흑이 이긴다. 백이 이기기 위해서는, $n$이 홀수일 때, 한 칸 오른쪽으로 가고 나면 사실상 홀수에서 스스로 후공이 된 셈이 되기 때문에 끝난다.

따라서, 겨우 6줄짜리 main함수로 문제를 해결할 수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    scanf("%d",&n);
    if(n%2==0)
        printf("white\n1 2");
    else
        printf("black");
}

---

D. CGCDSSQ

Solution : Gratus907

Code : Gratus907

배열 $a$에서, 쿼리 $x$ 가 주어졌을 때, $a_l, a_{l+1} , \dots a_r$까지의 gcd가 $x$가 되게 하는 $(l, r)$ 부분배열의 개수를 찾는 문제.

임의의 $r$을 고정하고, 왼쪽으로 하나씩 늘리면서 subarray의 gcd를 계산한다고 생각해 보자. 이때, $a_r$이 포함되어 있기 때문에, 서로 다른 gcd값은 최대 $\log a_r$ 개 정도가 최대이다. 만약 gcd가 달라진다면 절반 이하로 떨어지고, 그렇지 않다면 아예 달라지지 않기 때문이다. 

따라서, map이나 vector같은 적당한 자료구조를 잘 이용해서 (vector를 이용하려면 상당히 귀찮다. 이분탐색으로 잘 찾아줘야 시간복잡도가 유지될 것 같다), $r$이 하나 늘어날 때, 지금까지 특정 gcd값을 갖는 부분배열이 몇 개인지를 세주면 된다. map에 넣고 빼는 시간을 생각하면 $n \log A$ 시간 정도에 풀 수 있고, 이정도면 충분히 빠르다. 맨 끝까지 돌아준 뒤에는 그냥 쿼리를 받을 때마다 map에서 값을 빼서 보여주면 그만이므로, $q \log n$ 시간 정도가 드는데, 이것도 시간 내에 문제가 없다.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
typedef pair <int, int> pii;
map <int, int> m;
vector <pii> v;
map <int, int> mm;
map <int, int> res;
int arr[101010];
int32_t main()
{
    int n;
    cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> arr[i];
    for (int i = 1; i<=n; i++)
    {
        mm.clear();
        v.clear();
        for (auto it:m)
            mm[__gcd(it.first,arr[i])]+=it.second;
        mm[arr[i]]+=1;
        swap(m,mm);
        for (auto it:m)
            res[it.first]+=it.second;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        cout << res[x] << '\n';
    }
}

이 문제를 빨리 풀 수 있었던 배경에는, 내가 C번이 쉽다고 생각한 이유 (C번은, gcd가 1이 되는 subsequence의 개수를 세는 문제다) 가 이 알고리즘을 적용할 수 있다고 착각했기 때문이다. 결국은 C번에서 틀린 방법이 D번에서 맞는 방법이었던 셈이다. 랜덤으로 뽑은 문제들임을 감안하면...흠...;;;

 

이걸 풀고 나서 팀원들이 이제 다른 문제들을 읽어보고 있었는데, 다음에 뭘 잡을지가 상당히 꼬였다.

 

B번은 뭔가 nim 게임에 확률을 끼얹어서~~ 뭐 그런 거였고, nim 게임 승리 조건이 잘 기억이 안 났다. 

C번은 아까 내가 던진 거라서 일단 패스.

G번도 읽어보고 고민을 했는데, Disjoint Set Union에 뭔가 구간 연산을 적용해야 하는 문제였고, 이 시점에서는 어떻게 구간 연산을 빠르게 할 지 자신이 없었다.

I번은 Coffeetea가 문제를 읽으면서 혼란에 빠져 있었다. 어쨌든 B번에 Diordhd, I번에 Coffeetea가 붙어서 뭔가를 하는 상황이었고 나는 다른 문제를 풀 자신이 없었으므로 결정을 했어야 했고, B번을 생각하러 갔다.

---

B. Dexterina's Lab

Solution : Diordhd, Gratus907

Code : Gratus907

다행히(...) 일반적인 Nim 게임의 후공 승리 조건은 모든 Pile들의 돌 개수의 XOR을 했을 때의 값이 0인 것임을 기억해냈다. 이걸 '알아내기에는' 무리가 있기 때문에, 집에 와서 바로 팀노트 'Useful Facts' 에 때려넣었다.

두 사람이 Nim게임을 할 건데, Pile은 $n$개 있다. 각 Pile에는 $a_i$개의 돌이 있는데, 이 $a_i$는 $0$개 이상 $x$개 이하이다. 그런데, 이 $a_i$가 주어지는 것이 아니라, $0$부터 $x$까지 각각의 확률이 주어져 있다.

여기까지는 뭐 그러려니 하겠는데, $n$이 $10^9$ 까지이다. 즉, $n$ 시간으로도 불가능하다. ($x$는 작다. 최대 100)

잘 생각해 보면, 어차피 XOR 연산 할 것이므로, $n-1$개까지의 XOR값이 $p$일 때, $a_n$이 어떤 수가 올지 확률이 주어져 있으므로 $p$에서 새로운 $q$로 갈 확률을 모두 구할 수 있다. 즉, $0$부터 $x$까지의 각 확률을 벡터로 생각하면, Transition matrix를 작성해서 Markov chain처럼 문제를 풀 수 있다는 뜻이다.

100까지의 수들을 아무리 XOR해도 127 이하의 값만 얻을 수 있으므로, $128 \times 128$ 행렬을 $n-1$제곱하고, 벡터를 곱해주면 최종 XOR값이 $k$일 확률을 모두 얻을 수 있다.

Binary Exponentiation 을 적용하면 $\mathcal{x^3 \log n}$ 시간에 해결.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
typedef pair <int, int> pii;
 
double raw[128];
double res[128];
struct matrix
{
    double data[128][128];
    matrix()
    {
        for (int i = 0; i<128; i++)
            for (int j = 0; j<128; j++)
                data[i][j] = (i==j?1:0);
    }
};
 
matrix matmul (matrix &A, matrix &B)
{
    matrix ans;
    for (int i = 0; i<128; i++)
    {
        for (int j = 0; j<128; j++)
        {
            double u = 0;
            for (int k = 0; k<128; k++)
                u += A.data[i][k] * B.data[k][j];
            ans.data[i][j] = u;
        }
    }
    return ans;
}
 
matrix fastexpo(matrix &B, int n)
{
    matrix ans;
    matrix m = B;
    int b = n;
    while(b)
    {
        if (b&1)
            ans = matmul(ans,m);
        b = b>>1;
        m = matmul(m,m);
    }
    return ans;
}
 
int main()
{
    int n, x;
    cin >> n >> x;
    for (int i = 0; i<=x; i++)
        cin >> raw[i];
    matrix trans;
    for (int i = 0; i<128; i++)
        for (int j = 0; j<128; j++)
            trans.data[i][j] = raw[i^j];
    trans = fastexpo(trans,n-1);
    for (int i = 0; i<128; i++)
    {
        double u = 0;
        for (int j = 0; j<128; j++)
            u += trans.data[i][j]*raw[j];
        res[i] = u;
    }
    cout << 1-res[0];
}

솔직히 행렬제곱으로 짜는 문제를 꽤 많이 틀렸었기 때문에 자신 없었는데, 공학수학 2를 B-맞으면서 얻은 Markov Chain에 대한 지식이 도움이 되었...나? ;;;;

---

I. Chip 'n Dale Rescue Rangers

Solution : Coffeetea, Gratus907

Code : Coffeetea, Gratus907

점 $(a, b)$ 에서 $(c, d)$ 로 가려고 하는데, 바람이 처음 $t$ 초 동안은 $(u, v)$ 속도 벡터로 주어지다가, 이후에는 $(u', v')$ 으로 바뀐다. 배를 타고 최대 $v_{max}$ 속도로 원하는 방향으로 이동할 수 있을 때, 도착할 수 있는 최소 시간을 구해야 한다.

 

다행히도 바람보다는 배가 항상 빠르다는 사실이 주어져 있으므로, 언젠가는 반드시 도착 가능하다. 따라서, 매우 큰 시간에는 도착 가능할 것이다. 또한, 꼭 최대 속도로만 항해할 필요가 없으므로 어떤 시간 $T$ 에 도착 가능하다면 그보다 긴 시간에는 반드시 도착 가능하다. (그냥 $T$에 간 다음 목적지에서 바람이 주는 속도벡터에 반대로, 바람 속도에 맞춰 가면 목적지에서 버티는 셈이 된다)

 

즉, 임의의 시간 $k$초 후에 도착 가능한지만 파악하면 이분 탐색 문제가 된다는 얘기이므로, 이것을 판정해 보자.

$k$초 동안 내가 아무것도 하지 않으면 바람에 의해 어디로 실려 갈지는 쉽게 알 수 있다.

또한, 그 실려 간 지점에서 목적지까지의 거리는 온전히 $k$초동안 항해로 도달할 수 있는지만 판정하면 되므로, 간단히 해결 가능.

 

이분 탐색을 이상하게 짜서 5WA (이쯤되니 체력 문제가...) 

$t_1-t_2$를 $t_2-t_1$로 써서 3WA

오차를 너무 크게/작게 잡아서 2WA

#include<bits/stdc++.h>
using namespace std;
 
#define ocha 0.0000001
 
int x, y;
int v, t;
int wx1, wy1, wx2,wy2;
 
double leftdist(double time) {
    if ( time <= t ) {
        double leftx = abs(x-time*wx1);
        double lefty = abs(y-time*wy1);
        return sqrt(pow(leftx, 2) + pow(lefty, 2));
    } else {
        double curx = t * wx1 + (time-t) * wx2;
        double cury = t * wy1 + (time-t) * wy2;
        double leftx = abs(x - curx);
        double lefty = abs(y - cury);
        return sqrt(pow(leftx, 2) + pow(lefty, 2));
    }
}
 
int main () {
    int a, b;
    scanf("%d %d %d %d", &a, &b, &x, &y);
    x-= a, y-=b;
    scanf("%d %d", &v, &t);
    scanf("%d %d %d %d", &wx1, &wy1, &wx2, &wy2);
 
    double hitime = 1073741824;
    double lotime = 0;
    while( true ) {
        double midtime = (hitime+lotime)/2;
        double left = leftdist(midtime);
        double going = midtime * v;
        if (abs(hitime-lotime)<ocha/10)
            break;
        if ( going > left ) {
            hitime = midtime;
        } else {
            lotime = midtime;
        }
    }
    printf("%.10lf", hitime);
}

---

G. Restructuring Company

Solution : Gratus907, Coffeetea

Code : Gratus907

$n$개의 원소로 된 DSU 자료구조에, Range Union 연산을 빠르게 구현해야 한다. 

즉, $x$번부터 $y$번 까지의 모든 번호를 서로 Union하는 연산을 많이 ($q$번) 해야 하는데, 하나씩 union하면 연산을 시간 내에 도저히 할 수 없으므로, 이미 과거에 묶었던 구간을 관리해야 한다.

 

간단하게, $i$번에 대해서 "$i$번을 포함하는 선분의 가장 오른쪽 끝 원소보다 하나 더 오른쪽" 이 무엇인지를 보관하고 돌아다니면 된다. 이렇게 하면 많아야 $n$번 이상의 union 과정이 불필요하다.

(말로 설명하면 어렵지만 코드는 비교적 간단하다)

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
typedef pair <int, int> pii;
 
int n, q;
struct DSU
{
    int parent[202020], size[202020], next_el[202020];
    void init(int nn)
    {
        for (int i = 1; i<=nn; i++)
        {
            parent[i] = i;
            next_el[i] = i+1;
            size[i] = 1;
        }
    }
    int Find(int k)
    {
        while(k!=parent[k])
        {
            parent[k] = parent[parent[k]];
            k = parent[k];
        }
        return k;
    }
    bool indept(int x, int y)
    {
        return Find(x)==Find(y);
    }
    void unite(int x, int y)
    {
        int u = Find(x), v = Find(y);
        if (u==v)
            return;
        if (size[u]>size[v])
            swap(u,v);
        size[v]+=size[u];
        size[u] = 0;
        parent[u] = parent[v];
    }
};
 
int main()
{
    usecppio
    cin >> n >> q;
    DSU company;
    company.init(n);
    while(q--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a==1)
            company.unite(b,c);
        else if (a==2)
        {
            int i = b+1;
            while(i<=c)
            {
                company.unite(b,i);
                int nxt = company.next_el[i];
                company.next_el[i] = c+1;
                i = nxt;
            }
        }
        else if (a==3)
            cout << (company.indept(b,c)?"YES\n":"NO\n");
    }
}

내가 이걸 푸는 동안 Coffeetea는 J번을 읽고 있었고 (더 풀 수 있을 거라는 생각을 했다기 보다는, 한시간 남았으니 뭔가 읽자 였다. 이때까지 Coffeetea가 3시간째 고통만 받고 있었기도 했고), Diordhd가 C번을 거의 다 풀었다. (수학적으로는 다 찾았고, 세세한 구현 이슈만 잡으면 되는 상황). 그래서 사실 나는 다시 둘중에 고민을 해야 하는 상황이 되었고, 일단은 Diordhd C번에서 내가 딱히 도와줄게 없었기 때문에 J번을 읽어나 보러 갔다.

 

03:37에 Diordhd가 C번을 맞았고 (C번은 조금 재밌는 문제인것 같아서 따로 포스팅하려고 한다),

Coffeetea는 이때 J번에서 사실 자신은 없지만 이렇게 짜면 될거 같지 않냐? 라는 생각을 나한테 설명하고 있었다.

---

J. Three-dimensional Turtle Super Computer

Solution : Coffeetea, Gratus907

Code : Coffeetea

큐브를 $n \times m \times k$ 개로 쌓아 놓은 공간이 있고, 큐브는 0 또는 1의 값을 가진다고 하자.

0-큐브는 지나갈 수 없고, 1-큐브는 지나갈 수 있다. 또한, 큐브에서 다른 큐브로 이동할 때는 반드시 인접한 큐브로, $x+y+z$ 좌표의 합의 값이 증가하는 방향으로만 이동할 수 있다.

어떤 1-큐브가 0으로 바뀌었을 때, 기존에는 (a,b,c) 큐브에서 (d,e,f) 큐브로 도달 가능했는데 이제는 불가능해 진다면, 그 큐브는 "Critical" 하다. 

$n, m, k$ 가 100까지이므로, 총 100만 개의 큐브가 있다. 따라서 하나가 Critical한지를 파악하는 것이 $\mathcal{O(1)}$ 시간에 가능해야 할 것 같은데...

 

Coffeetea가 이런 문제를 푸는데 굉장히 좋은 습관(?) 을 가지고 있다. 차원을 내려서 2차원에서 문제를 본다던가 하는, 이런 생각들이 굉장히 도움이 된다. 2차원에서 생각해 보면, $(x, y)$가 Critical할 조건은 다음과 같다. (왜인지를 보이는 것도 생각해 보면 어렵지는 않다) 

- 당연히, $(x,y)$ 가 일단 1-큐브여야 하고

- $(x-1, y)$ 와 $(x+1, y)$ 가 1-큐브이거나 (즉, $x$방향으로 양옆에 1-큐브이거나)

- $y$방향으로 위아래에 1-큐브이거나

- 왼쪽과 위가 1-큐브이고, '왼쪽'에서 '위' 로 갈 수 있는 대안 경로, 즉 '$(x-1,y+1)$' 이 0 큐브라서 길이 없을 때.

- 아래와 오른쪽에 대해 똑같은 상황.

 

즉, 스스로가 1-큐브일 때 4개 방향의 경로를 봐야 한다는 뜻이다. 3차원이면 9개 경로를 확인함으로써, 즉 자신을 정가운데 큐브로 하는 $3 \times 3 \times 3$ 만 보면 된다.

조건을 그냥 하드코딩하면 끝.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
bool cpu[120][120][120];
bool critical[105][105][105];
 
int main () {
    int n, m, k;
    scanf("%d %d %d",&n,&m,&k);
    for (int i = 1; i<=n; i++)
    {
        for (int j = 1; j<=m; j++)
        {
            for (int h = 1; h<=k; h++)
            {
                int u;
                scanf("%1d",&u);
                cpu[i][j][h] = (u==1);
            }
        }
    }
 
    for ( int x = 1 ; x <= n ; ++x ) {
        for ( int y = 1 ; y <= m ; ++y ) {
            for ( int z = 1 ; z <= k ; ++z ) {
                if ( cpu[x-1][y][z] && cpu[x+1][y][z] ) critical[x][y][z] = true;
                if ( cpu[x][y-1][z] && cpu[x][y+1][z] ) critical[x][y][z] = true;
                if ( cpu[x][y][z-1] && cpu[x][y][z+1] ) critical[x][y][z] = true;
 
                if( cpu[x-1][y][z] && cpu[x][y+1][z] && !cpu[x-1][y+1][z] ) critical[x][y][z] = true;
                if( cpu[x-1][y][z] && cpu[x][y][z+1] && !cpu[x-1][y][z+1] ) critical[x][y][z] = true;
 
                if ( cpu[x][y-1][z] && cpu[x+1][y][z] && !cpu[x+1][y-1][z] ) critical[x][y][z] = true;
                if ( cpu[x][y-1][z] && cpu[x][y][z+1] && !cpu[x][y-1][z+1] ) critical[x][y][z] = true;
 
                if ( cpu[x][y][z-1] && cpu[x+1][y][z] && !cpu[x+1][y][z-1] ) critical[x][y][z] = true;
                if ( cpu[x][y][z-1] && cpu[x][y+1][z] && !cpu[x][y+1][z-1] ) critical[x][y][z] = true;
                
                if ( !cpu[x][y][z] ) critical[x][y][z] = false;
            }
        }
    }
    
    int ret = 0;
    for ( int x = 1 ; x <= n ; ++x ) {
        for ( int y = 1 ; y <= m ; ++y ) {
            for ( int z = 1 ; z <= k ; ++z ) {
                if(critical[x][y][z]) ++ret;
            }
        }
    }
    printf("%d", ret);
}

---

후기

무려 8솔! 생각보다 훨씬 잘했기 때문에, Whining할게 결과만 보면 거의 없어야겠지만 그건 나랑 Diordhd 얘기고, 정확히는 Coffeetea가 대략 3시간 정도 고통을 받고 마지막에 가서야 제정신을 차리고 J를 풀었다. 실제로 이렇게 실력차가 별로 없는 팀의 경우 사실 후반에 어려운 1문제를 풀어내는 것만으로도 팀 기여도가 상당히 높은걸 생각하면, 내가 초중반에 많이 풀긴 했지만 라운드 전체 관점에서는 나쁘지 않다고 본다.

 

사실 이번 셋이 수학문제가 우리가 건드려보기에 적절한 난이도 (2000, 2100) 이었고, 의외로 2200문제인 J가 관찰 한두개로 어렵지 않게 풀려서 우리 실력에 비해 많이 푼 것 같다. 특히 세그트리 같은 자료구조 쓰는 문제가 없어서... 

우리 팀이 레이팅에 비해 수학에 강하고 자료구조에 약한 것은 이미 여러번 연습 하면서 느꼈는데, 이게 생각보다 차이가 더 많이 난다는 생각이 들었다.