Little Piplup 9월 19일 팀연습

시간이 딱 3시간 정도 밖에 없어서, 2017 대전 인터넷 예선을 팀연습으로 돌았다. 

 

등록을 제외하고 5솔브에 페널티 487분이면 실 대회에서는 등록이 있어서 6솔브 / 페널티 매우 높은 편이라 22등 정도

2017 ICPC 때는 6솔이상 전체진출 했으니까 간당간당한 등수인데, 아마 올해 참가자들이었으면 못 나갔을 수도 있을 것 같다 ㅠㅠ

등록 (K) 이 없어서 K번이 실제로는 대회 L번이다

---

A. Closest Pair

Solve : Gratus907

Code : Gratus907

뭔가 평소 팀연습에 비해 상당히 산만하고 집중을 못하긴 했지만 아무튼 큰 문제 없이 내가 풀었다.

Coffeetea랑 Diordhd 둘다 이 문제를 본 적이 있다고 해서, 그냥 둘다 넘기고 무조건 내가 생각해서 짜기로 했는데 다행히 잘 보니 별로 어려운 문제는 아니라서...

어차피 정답으로 가능한 후보는 lower bound (보다 하나 앞)과 upper bound 근처의 두 개씩밖에 없다. 약간의 예외 케이스 (lower bound가 0을 리턴하는 경우) 들을 피하기 위해서 앞뒤로 -2억, 2억 같은 매우 큰 값들을 넣어서 vector bound error만 방지해 주면 어렵지 않게 해결할 수 있다. 

 

끝나고 Diordhd가 투포인터 접근을 이용하면 $O(n)$ 에도 풀 수 있다고 알려줬다. 

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
vector <int> a;
vector <int> b;
int ct = 0;
int ydist = 0;
int len = INT_MAX;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n, m;
    int yy, yyy;
    cin >> n >> m;
    cin >> yy >> yyy;
    ydist = abs(yy-yyy);
    for (int i = 0; i<n; i++)
    {
        int x;
        cin >> x;
        a.push_back(x);
    }
    for (int i = 0; i<m; i++)
    {
        int x;
        cin >> x; 
        b.push_back(x);
    }

    a.push_back(-200000000);
    b.push_back(-300000000);
    a.push_back(200000000);
    b.push_back(300000000);
    sort(all(a));
    sort(all(b));
    for (auto it:a)
    {
        int hi = upper_bound(all(b),it) - b.begin();
        int lo = lower_bound(all(b),it) - b.begin()-1;
        if (hi - lo > 1)
        {
            if (len == 0)
            {
                ct++;
                continue;
            }
            else 
            {
                len = 0, ct = 1;
                continue;
            }
        }
        int hid = abs(b[hi]-it);
        int lod = abs(b[lo]-it);
        int d = min(lod, hid);
        if (d<len)
        {
            len = d;
            ct = 1 + (lod==hid);
        }
        else if (d == len)
            ct+= (1+(lod==hid));
        else continue;
    }
    cout << len+ydist << ' ' << ct << '\n';
    
}

---

I. Pizza Boxes

Solve : Coffeetea

Code : Coffeetea

내가 A번을 푸는 동안 Coffeetea랑 Diordhd가 문제를 쭉 읽어보고 있었는데, B C D E F G 6문제 모두 상당히 어려운 문제라는 판단이 들었고, Coffeetea는 I번, Diordhd는 H번을 풀었다. 둘중 조금 더 먼저 풀이를 생각한 Coffeetea가 바로 코딩 시작해서 00:51에 AC를 받았다.

생각 외로 문제 난이도에 비해 첫 AC -> 두번째 AC까지 시간이 오래 걸렸는데, B~G까지 모두 지금 우리 실력으로는 상당히 어려운 문제라서 그런 것 같다.

 

아무튼 이건 무슨 문제인지 잘 모르겠는데 딱히 뭘 많이 적지도 않은걸 보면 그냥 구현문제인듯?

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

int going[1005][1005];
int num[1005][1005];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for ( int i = 0 ; i < n ; ++i ) {
        int ty = 0, retj;
        for ( int j = 0 ; j < m ; ++j ) {
            scanf("%d", &num[i][j]);
            if ( num[i][j] > ty ) {
                ty = num[i][j];
                retj = j;
            }
        }
        going[i][retj] = true;
    }
    for ( int j = 0 ; j < m ; ++j ) {
        int ty = 0, reti;
        for ( int i = 0 ; i < n ; ++i ) {
            if ( num[i][j] > ty ) {
                ty = num[i][j];
                reti = i;
            }
        }
        going[reti][j] = true;
    }
    long long int ret = 0;
    for ( int i = 0 ; i < n ; ++i) {
        for ( int j = 0 ; j < m ; ++j ) {
            if ( !going[i][j] ) ret += num[i][j];
        }
    }
    printf("%lld", ret);
}

---

H. Multimax
Solve : Diordhd

Code : Diordhd

Coffeetea가 I번을 푼 직후에 코딩하기 시작해서 케이스 조금 나누더니 맞았다. 이것도 무슨 문제인지는 잘 모르겠는데, 대충 숫자 3개 골라서 곱을 최대로? 하는 문제인걸보니 그냥 케이스 분류...

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

vector<int> a;
vector<int> b;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0,x; i<n; i++)
    {
        scanf("%d",&x);
        if(x>0)
            a.push_back(x);
        else if(x<0)
            b.push_back(-x);
    }
    sort(a.begin(),a.end(),greater<int>());
    sort(b.begin(),b.end(),greater<int>());
    if(a.size()+b.size()<2)
    {
        printf("0");
        return 0;
    }
    else
    {
        int maxi = -INT_MAX;
        if(a.size()>=2)
        {
            maxi = max(maxi, a[0]*a[1]);
            if(a.size()>=3)
                maxi = max(maxi, a[0]*a[1]*a[2]);
        }
        if(a.size()>=1&b.size()>1)
            maxi = max(maxi, a[0]*b[0]*b[1]);
        if(a.size()==1&&b.size()==1)
            maxi = max(maxi, 0);
        if(b.size()>=2)
            maxi = max(maxi, b[0]*b[1]);
        printf("%d",maxi);
    }
}

---

L. Telescope

Solve : Gratus907, Diordhd

Code : Gratus907

행렬 위에서 행의 개수가 같고 열이 적은 다른 행렬을 밀면서, 내적 (열벡터들끼리 내적한 값의 합을 내적이라고 대충 정의하자) 을 빠르게 구할 수 있으면 된다. 즉, 행렬이 k행 n열이라고 하면 k행 m열짜리 작은 행렬을 밀면서, 

 

작은 행렬이 1열에 위치했을 때 열벡터들의 내적의 합을 구하고

작은 행렬을 2열로 밀었을 때 열벡터들의 내적의 합을 구하고...

 

이걸 행렬 크기의 곱보다 빠른 시간에 구해야 한다. (행렬 크기가 최대 100만 항, 30만 항)

 

행렬의 원소를 왼쪽 열부터 열 단위로 나열하고, 이걸 다항식처럼 생각하자. 즉, (1, 1) 위치의 항을 상수항으로, (2, 1) 위치의 항을 1차항으로... 이런 식.

 

이때, 작은 행렬 쪽은 뒤집어서 나열한다. (k, m) 위치가 상수항이고, (k-1, m) 위치가 1차항이고, ... 이런 식으로 나열하고 나면, 이 두 다항식을 곱셈했을 때 우리가 원하는 값들 (밀었을 때의 내적의 합) 이 정해진 차수 항들의 계수로 나타난다는 것을 알 수 있다. 물론 사이사이에 쓸데없는 항들이 있지만, 이것들은 우리가 행렬을 열 단위로만 밀 수 있기 때문에 (값 1개 단위로 stream하며 미는 게 아니라, k행이면 k개씩만 밀 수 있어서) 생기는 값들이므로 무시하면 된다.

 

다항식을 빨리 곱하는 방법은 FFT를 사용하면 되고, 대충 이게 뭔지는 알고 있으나 코드로 짤 자신은 전혀 없으므로 팀노트에 https://blog.myungwoo.kr/54의 코드를 베껴 넣어 두었다. FFT로 다항식 곱셈하는거만 짜면 되는 문제이므로, 약간 "알면 순삭하고, 모르면 절대 못 푸는" 스타일. 

#include <bits/stdc++.h>
#include <complex>
#define __USE_MATH_DEFINES
#define ll long long
#define int ll
#define sz(v) ((int)(v).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
double PI = 3.1415926535;
typedef complex<double> base;
typedef vector <int> vi;
typedef vector <base> vb;
void fft(vb &a, bool invert)
{
    int n = sz(a);
    for (int i = 1, j=0; i<n; i++)
    {
        int bit = n>>1;
        for (; j>=bit; bit>>=1)
            j -= bit;
        j += bit;
        if (i < j)
            swap(a[i],a[j]);
    }
    for (int len = 2; len <= n; len <<= 1)
    {
        double ang = 2*PI/len*(invert?-1:1);
        base wlen (cos(ang),sin(ang));
        for (int i = 0; i<n; i+= len)
        {
            base w(1);
            for (int j = 0; j<len/2; j++)
            {
                base u = a[i+j], v = a[i+j+len/2]*w;
                a[i+j] = u+v;
                a[i+j+len/2] = u-v;
                w *= wlen;
            }
        }
    }
    if (invert)
        for (int i = 0; i<n; i++)
            a[i] /= n;
}

void multiply(const vi &a, const vi &b, vi &res)
{
    vector <base> fa(all(a)), fb(all(b));
    int n = 1;
    while(n < max(sz(a),sz(b)))
        n <<= 1;
    fa.resize(n); fb.resize(n);
    fft(fa,0), fft(fb,0);
    for (int i = 0; i<n; i++)
        fa[i] *= fb[i];
    fft(fa,1);
    res.resize(n);
    for (int i = 0; i<n; i++)
        res[i] = int64_t(fa[i].real()+(fa[i].real()>0?0.5:-0.5));
}
vi aa, bb, cc;
vi res;
int T[101][10101];
int P[101][3030];
int ct = 0;
int32_t main()
{
    int n, l, m, w;
    cin >> n >> l >> m >> w;
    aa.resize(m*n);
    bb.resize(m*n);
    for (int i = 0; i<m; i++)
        for (int j = 0; j<n; j++)
            cin >> T[i][j];
    for (int i = 0; i<m; i++)
        for (int j = 0; j<l; j++)
            cin >> P[i][j];
    for (int i = 0; i<n; i++)
        for (int j = 0; j<m; j++)
            aa[i*m + j] = T[j][i];
    for (int i = 0; i<l; i++)
        for (int j = 0; j<m; j++)
            bb[i*m + j] = P[m-j-1][l-i-1];
    multiply(aa, bb, cc);
    for (int i = m*l-1; i<m*n; i+=m)
    {
        if (cc[i] > w)
        {
            ct++;
            res.push_back(cc[i]);
        }
    }
    cout << ct << '\n';
}

FFT 코드를 그대로 베껴넣으면서 내가 평소에 쓰던 스타일이랑 다른 점들 때문에 약간 헷갈리는게 있었는데, 이런부분들을 줄이기 위해 저 코드에 기반해서 쓰기 편하게 조금 수정해 둬야겠다는 생각이 들었다.

---

D. Grasshopper Route

Solve : Coffeetea, Diordhd, Gratus907

Code : Gratus907, Diordhd

트리에서 정점 $s$에서 $t$까지 가는데, 각 정점을 모두 정확히 한 번씩 지나야 한다. 당연히 이러면 자식 정점이 2개만 있어도 탐색할 수 없으므로, "점프" 가 가능한데, 점프는 거리가 3 이하인 정점으로 바로 점프할 수 있다. 점프를 적절히 활용하면 임의의 트리에서 두 정점을 지날 수 있음이 증명되어 있다고 한다.

 

$s$에서 $t$까지 트리에서 path가 유일하게 하나 존재한다. 이 path 위를 따라가면서, path 위의 각 노드를 루트로 하는 서브트리를 모두 방문하고 (단 path는 건드리지 않고) 돌아오는 재귀함수를 작성한다. 이때 path 위에 있는 노드로 시작해서 적당히 path와 거리 2 이하인 노드로 돌아오는 경로를 찾으면, path 위의 다음 노드까지의 거리가 3 이하이므로 반드시 점프 가능하다.

이때 최대한 점프를 활용하기 위해서 path와 홀수 거리에 있는 점은 걸어서 방문하고, path와 짝수 거리에 있는 점은 점프로 방문하는 방법으로 이동하면 된다. 

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

vector <int> graph[101010];
bool visit[101010];
int par[101010];
vector <int> mainpath;
vector <int> answer;
void dfs(int r, int p)
{
    visit[r] = 1;
    par[r] = p;
    for (auto it:graph[r])
    {
        if (!visit[it] && (it!=p))
        {
            dfs(it,r);
        }
    }
}

void rec(int r)
{
    visit[r] = true;
    for (auto it:graph[r])
    {
        if (!visit[it])
        {
            visit[it] = true;
            answer.push_back(it);
            for (auto it2:graph[it])
            {
                if (!visit[it2])
                {
                    rec(it2);
                }
            }
        }
    }
    answer.push_back(r);
}
int main()
{
    usecppio
    int n, s, t;
    cin >> n;
    for (int i = 1; i<n; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    cin >> s >> t;
    dfs(s,0);
    mainpath.push_back(t);
    int tp = t;
    while(par[tp]!=s)
    {
        tp = par[tp];
        mainpath.push_back(tp);
    }
    mainpath.push_back(s);
    reverse(mainpath.begin(),mainpath.end());
    int plen = mainpath.size();
    memset(visit,0,sizeof(visit));

    answer.push_back(s);
    for (auto it:mainpath)
        visit[it] = true;
   
    for (auto it:graph[mainpath[0]])
        if (!visit[it])
            rec(it);
    for (int i = 1; i<plen; i++)
        rec(mainpath[i]);
    visit[mainpath[plen-1]] = true;

    for (auto it:answer)
        cout << it << '\n';
}

---

못 푼 문제들

B : 뭔가 잘 모르겠지만 이러면 되지 않을까? 라는 생각이 들었는데 당연히 안 되는것 같다. 풀이를 봐도 잘 모르겠고, 본 대회중에도 한 팀인가밖에 못 푼 문제인 걸 보니 그냥 갓갓문제인듯.

C : String Parsing을 보고 사실상 포기했지만 사실 시간이 남았다면 이걸 푸는게 맞았을 것 같은데... 잘 모르겠다. 파싱 외에는 그렇게 어려운 문제는 아니었다는것 같은데 우리는 이미 파싱부터가 너무 고통이라...

E : 문제를 읽어보고 나는 기하 + 플로우로 풀 수 있지만 둘 다 못 짠다는 생각이 들었고, Coffeetea가 이걸 듣고 그냥 같이 포기하기로 결정. 플로우는 ICPC 때까지 못 익힐수도 있을것 같지만 CCW는 어떻게 다룰지 좀 제대로 익혀봐야 할거같다.

F : 나는 안 읽어봐서 무슨 문제인지 모르겠는데, 푼 팀 수를 보니 D랑 비슷한듯. Diordhd가 "직선에 쿼리날리는거보니 Convex Hull Trick인데 어떻게 짜는지 모름. 던지자" 라길래 던졌다.

G : 안 읽어봐서 모르는 문제 2

J : KMP 활용이라는 생각이 들었는데 정해는 Suffix array라는 잘 모르는걸 쓰는거 같고, KMP풀이도 가능하긴한데 이상한 아이디어가 필요한 것 같았다. 솔브 팀 수를 보니 갓갓문제 2

---

개강하고 나니 다들 뭔가 시간이 애매해서 팀연습이 잘 안 맞는거 같다. 이 팀이 만약 올해 ICPC 이후로도 계속 같이 갈 수 있으면 겨울방학때는 더 빡세게 연습 돌아야지...

올해 ICPC 서울대 진출팀수가 9팀일 예정이라 사실 조금 들기 힘들것 같다는 생각이 들긴 하는데, 일단 어떻게 될지는 모르는 거고, 뭐 내년엔 나갈 수 있지 않을까? 라는 생각도 들고... ㅇㅁㅇ