Little Piplup 9월 27일 팀연습

몇 안 되는 4시간짜리 ICPC 셋인 
2018-2019 NEERC Southern Subregional, Qualification Round 를 돌았다.

https://codeforces.com/gym/101911

계정 넣는걸 실수해서 Coffeetea 개인 계정으로 돌았다.

 

예전에 이 셋 문제들로 만들어진 코드포스 라운드에 참여한 적이 있어서 (작년 쯤...) B I J는 내가 풀었었던 문제였고, 내가 손 안 대기로 했다.

 

---

시작은 Diordhd가 A, Coffeetea가 B, 내가 C번을 잡았고, C번이 쉬운 문제라서 바로 구현 들어갔다.

C. Bacteria

Solve : Gratus907

Code : Gratus907

2개씩 합쳐야 하기 때문에, 가장 작은 수 $x$를 기준으로 $x \times 2^n$ 에 해당하지 않는 수가 하나라도 있다면 불가능하다. 만약 모두 이런 형태라면, 전부 $x$ 로 나눠서 $2^n$들만 남기면 된다. 

이제 가장 작은 것부터 greedy하게 합치려고 시도해 보고, 필요하다면 추가로 사와서 시도한다.

이 과정은 priority queue를 사용해서 쉽게 할 수 있다.

#include<bits/stdc++.h>
#define sz(a) (int)(a).size()
using namespace std;
#define int ll
#define ll long long

vector <int> v;
priority_queue<int, vector <int>, greater<int>> pq;
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    v.resize(n);
    for (int i = 0; i<n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int s = v[0];
    for (int i = 1; i<n; i++)
    {
        if (v[i]%v[0])
        {
            cout << -1;
            return 0;
        }
        int k = 1, e = 0;
        int tg = v[i]/v[0];
        while(k < tg)
        {
            k*=2;
            e++;
        }
        if (k!=tg)
        {
            cout << -1;
            return 0;
        }
        v[i] = (1LL<<e);
    }
    v[0] = 1;
    for (auto it:v)
        pq.push(it);
    int ans = 0;
    while(pq.size()>1)
    {
        int p = pq.top();
        pq.pop();
        int q = pq.top();
        pq.pop();
        if (p == q)
            pq.push(p*2);
        else
        {
            pq.push(q);
            pq.push(2*p);
            ans++;
        } 
    }
    cout << ans << '\n';
}

---

A. Coffee Break

Solve : Diordhd

Code : Gratus907

C번을 내가 AC 받은 후, Coffeetea가 B번 구현에서 고통받고 있었고 (...) Diordhd는 A번 풀이는 생각났지만 코딩이 자신 없다고 해서 내가 풀이를 받아서 코딩하기로 했다. 

가능한 날짜에서 최대한 많은 커피를 챙기기 위해서 set 의 lower bound를 이용해서 계속 삭제하는 식으로 하면 된다는 풀이였고, 들어보니 $O(n \log n)$ 풀이가 맞는 것 같아서 set iterator 사용에 매우 자신이 없었지만 일단 짜기로 했고, 의외로 한번에 맞았다.

#include<bits/stdc++.h>
#define sz(a) (int)(a).size()
using namespace std;

using pii = pair<int, int>;

int n, m, d;
set <pii> s;
int day[202020];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    for (int i = 1; i<=n; i++)
    {
        int a;
        cin >> a;
        s.insert({a,i});
    }
    int curday = 0;
    while(!s.empty())
    {
        curday++;
        auto it = s.begin();
        pii u = *(it);
        pii x = *(s.begin());
        day[x.second] = curday;
        s.erase(x);
        while(it != s.end())
        {
            it = s.lower_bound(pii(u.first+d+1, -1));
            if (it == s.end())
                break;
            else 
            {
                pii v = *(it);
                u = *(it);
                day[v.second] = curday;
                s.erase(v);
            }
        }
    }
    int M = 0;
    for (int i = 1; i<=n; i++)
        M = max(M, day[i]);
    cout << M << '\n';
    for (int i = 1; i<=n; i++)
        cout << day[i] << ' ';
    cout << '\n';
}

---

I. Heist

Solve : Diordhd

Code : Diordhd

Coffeetea가 B번 마지막 디버깅 작업을 하는 동안 Diordhd가 쉬운 문제를 하나 먹고 지나갔다. 

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

int arr[1020];
int main()
{
    int n;
    int maxi = 0;
    int mini = INT_MAX;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",arr+i);
        maxi = max(maxi,arr[i]);
        mini = min(mini,arr[i]);
    }
    printf("%d",maxi-mini+1-n);
}

---

B. Glider

Solve : Coffeetea

Code : Coffeetea

꽤 오랜 시간을 여기 붙잡혀 있단 Coffeetea가 드디어 빡구현 문제에서 탈출했다. 

대략 내가 오래 전에 이 문제를 풀었었던 기억 + 그때 썼던 후기를 찾아보니,

- 반드시 상승기류의 시작점 중 하나에서 시작하는 것이 이득이고

- 상승기류가 없는 부분의 길이와 있는 부분의 길이로 나눠서 저장하면서 다이나믹? 

뭐 이런 문제인거같다. Coffeetea가 케이스 나누는거에서 약간 고생했지만 Diordhd나 내가 잡았으면 더 오래 걸렸을 문제라서...

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

int main(){
    int n, h;
    scanf("%d %d", &n, &h);
    vector<pair<int, int> > flow;
    for ( int i = 0 ; i < n ; ++i ) {
        int a, b;
        scanf("%d %d", &a, &b);
        flow.push_back({a,b});
    }
    sort(flow.begin(), flow.end());
    int up[n], dist[n-1];
    for ( int i = 0 ; i < n ; ++i ) {
        up[i] = flow[i].second - flow[i].first;
        dist[i] = flow[i+1].first - flow[i].second;
    }
    int cur = h;
    int ret = cur;
    int left = h;
    queue<int> curup;
    queue<int> curdist;
    for ( int i = 0 ; i < n ; ++i ) {
        if ( curup.empty() ) {
            cur += up[i];
            curup.push(up[i]);
        } else {
            cur += up[i];
            curup.push(up[i]);
            left -= dist[i-1];
            curdist.push(dist[i-1]);
            while( !curdist.empty() && left <= 0 ) {
                cur -= curup.front();
                curup.pop();
                left += curdist.front();
                curdist.pop();
            }
        }
        ret = max(ret, cur);
    }
    printf("%d", ret);
}

---

D. Masquerade Strikes Back

Solve : Gratus907, Diordhd

Code : Gratus907

어떤 수 $c_i$ 들이 주어졌을 때, $a_i \times b_i$ 로 잘라야 하는데, 같은 $(a, b)$ 쌍이 두 번 이상 나와서는 안 된다. 

$c_i$ 들은 $10^7$ 까지, 숫자는 20만 개.

만약 같은 숫자가 2개 이하 들어온다면, 자명한 방법 $(1, c)$ 와 $(c, 1)$ 로 해결할 수 있다. 즉, 최악의 경우에는 $10^7$ 정도 되는 수를 6.7만 번 정도 소인수분해해야 한다는 뜻이고, 각 소인수분해 스텝은 $O(\sqrt{C})$ 로 할 수 있으니까 대략 2억 번 정도의 연산으로 할 수 있다. 요즘 컴파일러 + 이렇게 간단한 연산이면 이정도는 충분히 된다! 라는 믿음을 가지고 짜서 맞았다.

$(1, c)$ 와 $(c, 1)$ 을 쓸 수 없는 $c = 1$ 케이스 때문에 1WA를 받았지만 속도는 나쁘지 않았다. 풀이가 확실해진 시점부터 Diordhd가 다른 문제를 생각하러 가서 시간을 많이 아낄 수 있었다.

#include<bits/stdc++.h>
#define sz(a) (int)(a).size()
using namespace std;
using pii = pair<int, int>;
#define ll long long

int ct[10101010];
pii ans[202020];
map <int, vector<int>> m;
vector <int> num;
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    num.resize(n);
    for (int i = 0; i<n; i++)
    {
        cin >> num[i];
        ct[num[i]]++;
        m[num[i]].push_back(i);
    }
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    if (ct[1] > 1)
    {
        cout << "NO\n";
        return 0;
    }
    for (auto it:num)
    {
        if (ct[it]==1)
            ans[m[it][0]] = {1, it};
        else if (ct[it]==2)
        {
            ans[m[it][0]] = {1, it};
            ans[m[it][1]] = {it, 1};
        }
        else 
        {
            int k = it;
            vector <int> v = m[k];
            
            int sz = v.size();
            int u = 0;
            for (int i = 1; i*i<=k; i++)
            {
                if (k%i)
                    continue;
                else
                {
                    int t = k/i;
                    if (i == k/i)
                    {
                        ans[v[u]] = {i, t};        
                        u++;
                    }
                    else 
                    {
                        ans[v[u]] = {i, t};
                        u++;
                        if (u >= sz)
                            break;
                        ans[v[u]] = {t, i};
                        u++;
                    }
                }
                if (u >= sz)
                    break;
            }
            if (u < sz)
            {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << "YES\n";
    for (int i = 0; i<n; i++)
        cout << ans[i].first << ' ' << ans[i].second << '\n';
}

---

K. Medians and Partition

Solve : Diordhd, Coffeetea

Code : Diordhd

잘 모르겠는데 DP 문제라는거 같다. 내가 D 코딩을 끝냈을 때 이미 K를 다 풀고 바로 Diordhd가 컴퓨터 앞에 앉고, 아직 제대로 안 본 F번 읽어 보라길래 그렇게 했다.

중간값이 얼마 이상이 되게 최대한 많은 조각으로 자르는? 문제인거 같던데, $O(n^2)$ dp로 풀 수 있다고 한다.

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

int arr[5020];
int sum[5020];
int dp[5020];
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=1,x; i<=n; i++)
    {
        scanf("%d",&x);
        if(x>=m)
            arr[i]=1;
        else
            arr[i]=-1;
        sum[i] = sum[i-1]+arr[i];
    }
    fill(dp,dp+n+2,-1);
    for(int i=1; i<=n; i++)
    {
        for(int j=i-1; j>=0; j--)
        {
            if(sum[i]-sum[j]>0)
            {
                if(dp[j]!=-1||j==0)
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
    printf("%d",dp[n]+1);
}

---

J. Buying a TV set

Solve : Coffeetea

Code : Coffeetea

매우 쉬운 문제. 약분 잘 하고 잘 세면 된다.

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

int main(){
    long long int a, b, x, y;
    scanf("%lld %lld %lld %lld", &a, &b, &x, &y);
    long long p = __gcd(x, y);
    x /= p;
    y /= p;
    printf("%lld", min(a/x, b/y));
}

---

F. Tickets

Solve : Gratus907

Code : Gratus907, Diordhd

어떤 수 $k$의 각 자리 수의 합을 $g(k)$ 라고 하고, $f(k)$ 를 $|g(k/1000) - g(k%1000)|$ 으로 정의하자.

이때 다음의 개수를 모든 $i$에 대하여 세면 된다.

$$ 1 \leq j < i, f(j) < f(i) $$

000000부터 999999까지 돌면서, $f(i)$ 의 값은 상수 시간 (기본 연산 10번 내외) 에 구할 수 있다. 이걸 이용해서 $f(i)$ 가 특정 $x$값인 것들의 개수를 세는 배열 $\texttt{count}$ 를 만들면, 그 배열에서 지금 들어온 $x$ 보다 작은 것들의 개수의 합, 즉 부분합이 답이 된다.

따라서 구간의 prefix sum을 빠르게 계산하는 자료구조를 이용해서 $i$를 올리면서 계산-갱신-계산-갱신 을 반복하면 된다.

 

이런 일을 할 수 있는 자료구조는 Fenwick Tree나 Segment Tree가 있는데, 내가 펜윅 코드 구현을 숙지를 못했고 연습때 팀노트를 안 놓고 해서 세그를 짜려고 했는데 (세그는 대충 외웠다) Diordhd가 펜윅 구현을 외웠다고 해서 펜윅 구현만 맡기고 그 위에 내가 짜서 맞췄다. 

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

struct BIT{
    int n;
    int tree[1000020];
    void update(int i, int v){for(int j=i; j<=n; j+=j&-j) tree[j]+=v;}
    int query(int i){
        int sum = 0;
        for(int j=i; j>0; j-=j&-j)
            sum+=tree[j];
        return sum;
    }
} bit;

inline int func(int x) 
{
    int u = 0;
    u -= (x%10);
    x/=10;
    u -= (x%10);
    x/=10;
    u -= (x%10);
    x/=10;
    u += (x%10);
    x/=10;
    u += (x%10);
    x/=10;
    u += (x%10);
    x/=10;
    return abs(u)+1;
}

int ans[1010101];
int main()
{
    int n;
    scanf("%d",&n);
    bit.n = 1000000;
    memset(bit.tree, 0, sizeof(bit.tree));
    for (int i = 0; i<=999999; i++)
    {
        int u = func(i);
        ans[i] = bit.query(u-1);
        bit.update(u, 1);
    }
    for (int i = 0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
}

---

G. Tree Reconstruction

Solve : Coffeetea, Diordhd, Gratus907

Code : Gratus907

대략적인 발상은, "각 점이 몇 번 나왔는지만 세면 된다" 와, "가장 큰 노드를 루트로 잡으면, 한 번 나온 노드는 모두 리프로 생각할 수 있다" 라는 두 가지. 그 외에는 "여러 번 나온 노드" 와 "한 번도 안 나온 노드" 를 구분해서 여러 번 나온 노드를 하나 붙일 때마다 나온 적 없는 노드를 적당히 연결해서 조건에 맞는 트리를 구성하려고 그리디하게 시도하면 된다.

#include<bits/stdc++.h>
#define sz(a) (int)(a).size()
using namespace std;
using pii = pair<int, int>;
#define ll long long

int ct[1010];
int ab[1010];
bool mark[1010];
int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 1; i<n; i++)
    {
        int a, b;
        scanf("%d %d",&a,&b);
        if (a != n && b != n)
        {
            printf("NO\n");
            return 0;
        }
        if (a==b)
        {
            printf("NO\n");
            return 0;
        }
        int u = a+b-n;
        ct[u]++;
    }
    for (int i = 1; i<=n; i++)
    {
        ab[i] = ab[i-1] + (!ct[i]);
    }
    for (int i = 1; i<=n; i++)
    {
        if (ct[i-1]-1 <= ab[i-1])
            continue;
        else
        {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    for (int i = 1; i<n; i++)
    {
        if (ct[i]==1)
        {
            printf("%d %d\n",n,i);
            mark[i] = 1;
        }
        else if (ct[i] > 1)
        {
            int u = ct[i]-1;
            int t = 0;
            int pt = i-1;
            vector <int> v;
            while(t<u)
            {
                if (!ct[pt] && !mark[pt])
                {
                    v.push_back(pt);
                    mark[pt] = 1;
                    t++;
                }
                pt--;
            }
            v.push_back(i);
            int s = v.size();
            printf("%d %d\n",n,v[0]);
            for (int i = 0; i<s-1; i++)
            {
                printf("%d %d\n",v[i], v[i+1]);
            }
        }
    }
}

---

H. Theater Square

Solve : Gratus907

Code : Gratus907

왜 이거 지금까지 안 봤지? 코딩 큐가 밀려서 안 짠 쉬운 문제.

그냥 각 행별로 왼쪽과 오른쪽에 몇 개의 블록을 써야 하는지를 잘 세면 된다.

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

pair<int, int> ans[202020];
int main()
{
    int n, m;
    scanf("%d %d",&n,&m);
    int a, b, c, d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for (int i = 1; i<=n; i++)
        ans[i].first = m;
    for (int i = a; i<=c; i++)
        ans[i] = {b-1, m-d};
    int res = 0;
    for (int i = 1; i<=n; i++)
        res += ((ans[i].first)%2 + (ans[i].second)%2);
    printf("%d",(res+1)/2);
}

---

L. Ray in the Tube

Solve : Gratus907, Diordhd

Code : Gratus907

Coffeetea가 E번을 생각하러 가고, 나랑 Diordhd가 L번을 잡았다.

먼저 출발은 임의로 한참 왼쪽에서 시작해도 되므로 답이 되는 빛의 폭 $S$ 를 정할 수 있다면, 위치는 크게 생각하지 않아도 된다는 점을 관찰하자. 그리고 어떤 빛의 폭 $S$가 이미 고정되었다면, 몇 개의 센서를 맞출 수 있는지는 map과 모듈러를 이용해서 (그 빛의 폭 $S$의 2배인 $2S$에 대한 나머지가 같은 모든 센서를 맞출 수 있으므로, 모든 센서를 map에 넣고 가장 많은 센서가 들어 있는 값을 찾는다) $O(n \log n)$ 정도 시간에 찾을 수 있다.

따라서 $S$의 후보를 최대한 줄여야 하는데, http://codeforces.com/contest/1220/problem/D 와 비슷한 방법이다. 몇개 그림을 그려보면, 어떤 $S$로 빛을 쏴 보면 $S$의 홀수 배인 $(2k+1)S$ 로 쐈을 때 지나는 모든 점을 다 지나고, 점을 더 지난다. 즉 $S$가 항상 $(2k+1)S$ 보다 나은 답이 된다.

그러므로 $2^i$ 들만 보면서 답을 찾아도 된다. 전체 시간 복잡도는 $O(n \log n \log Y)$.

#include<bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
int n, m, y;
vector <int> up, down;
map <int, int> mup;
map <int, int> mdown;
int check_max(int x)
{
    int maxi = 0;
    for (auto it:up)
        mup[it%(2*x)]++;
    for (auto it:down)
        mdown[it%(2*x)]++;
    for (auto it:mup)
    {
        int k = it.first;
        maxi = max(maxi, mup[k] + mdown[(k+x)%(2*x)]);
    }
    for (auto it:mdown)
    {
        int k = it.first;
        maxi = max(maxi, mdown[k] + mup[(k+x)%(2*x)]);
    }
    return maxi;
}
int32_t main()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> y;
    up.resize(n);
    for (int i = 0; i<n; i++)
        cin >> up[i];
    cin >> m >> y;
    down.resize(m);
    for (int i = 0; i<m; i++)
        cin >> down[i];
    int cand = 1;
    int ans = 2;
    for (int i = 0; i<31; i++)
    {
        mup.clear();
        mdown.clear(); 
        cand = (1LL<<i);
        ans = max(ans, check_max(cand));
    }
    cout << ans;
}

---