Codeforces Global Round 19 ABCD

[10번째 Contest]

빠른 3솔로 블루 퍼포냈다. DE는 너무 어렵다.. 특히,, E는 정수론이라 당했다.

지난 3번의 코포에서 떡락으로 300점을 날려서 2주 동안 슬럼프가 있었다.

버추얼을 돌려도 0솔을 했다. 자신감이 많이 떨어진 상황이었다.

어제 하루 코딩을 놓고 넷플과 롤체를 하며 힐링 시간을 가졌다. 오늘은 가볍게 업솔빙하면서 자신감을 회복했다.

그리고 오늘 코포에서 블루 퍼포 회복하고 +100 레이팅을 가져갔다.

A. NIT orz!

길이가 $n$인 배열과 정수 $z$가 입력된다. 다음 작업을 무수히 많이 해서 배열 안에 가장 큰 수를 구하는 문제다.

임의의 $i \, (1 \leq i \leq n)$에 대해서, $a_i = (a_i \; or \; z)$, $z = (a_i \; and \; z)$

풀이

$z$는 위의 작업으로 초기의 $z$보다 커질 수 없다. $and$ 연산은 아무리 해도 없던 비트가 생기지 않기 때문이다.
따라서 초기의 $z$와 배열 $a$ 안에 원소를 $or$ 연산을 한 최댓값을 구하면 된다.

코드

def solve():
    a, b = map(int, input().split())
    arr = list(map(int, input().split()))
    
    c = 0
    for x in arr:
        c = max(c, x|b)
    print(c)


for __ in range(int(input())):
    solve()

B. NIT Destroys the Universe

길이가 $n$인 배열 $a$가 들어온다. 다음 작업을 통해 $a$의 모든 수를 $0$으로 만들어야 한다. 사용하는 작업의 최소갯수를 구하라.

$l, r (1≤l≤r≤n)$를 고른다. $w=mex({a_l,a_{l+1},…,a_r})$ 라고 하면, $a_i = w (l≤i≤r)$로 초기화 한다. $mex(a[l:r])$은 구간 안에 없는 가장 작은 $0$보다 큰 정수이다.

풀이

$0$을 기준으로 접근해야 한다. 연속된 양의 정수 그룹의 갯수에 따라 풀이가 나뉜다. 그룹이 없다면 모두 $0$이므로 작업할 필요가 없다. 그룹이 $1$개 있다면, 그 그룹만 작업을 한 번 실행하면 된다. 그룹이 $2$개 이상이라면, 각 그룹에 대해 작업하면 실행 횟수가 최소화되지 않는다. 이 경우에 전체에 대해서 작업을 두 번만 실행하면 된다.

$a$의 원소가 모두 $0$이라면 작업할 필요가 없다.

$a = [0, 1, 2, 3, 0]$ 이라면 $l=2, r=4$에 대해 작업을 한 번만 실행하면 된다.

$a = [0, 1, 0, 2, 0, 3]$ 이라면 $l=1, r=6$으로 두고 작업을 두 번 실행하면 된다.

코드

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    l, r = -1, -1
    for i in range(n):
        if arr[i]!=0:
            if l==-1:
                l = i
            r = i
            
    if l==-1:
        return 0
    for i in range(l+1, r):
        if arr[i]==0:
            return 2
    return 1
 
 
for __ in range(int(input())):
    print(solve())

C. Fishingprince Plays With Array

정수 $n, m, k$ 와 각각 길이가 $n$과 $k$인 배열 $a, b$가 입력된다. 우리는 다음 작업을 무수히 수행해서 $a$를 $b$로 바꿀 수 있는지 확인해야 한다.

• 쪼개기: $m$으로 나눠 떨어지는 $a_i$를 선택한다. $a_i$ 위치에 $a_i/m$ $m$개를 삽입한다.
• 합치기: 연속된 동일한 수 $m$개를 선택한다. 모든 수를 없얘고 그 위치에 $a_i*m$를 삽입한다.

풀이

쪼개기와 합치기는 반대되는 작업이다. 작업을 꼭 a에만 적용할 필요는 없다. a와 b를 적절하게 변형하고 동일한지 확인하면 된다. 가장 간단한 방법은 a와 b를 최소 단위로 쪼개서 확인하는 거다. 최소 단위로 쪼갰을 때, 구성이 같다면 합쳤을 때도 같다.

무지성 쪼개서 저장하면 메모리랑 시간이 터질 수도 있다. 연속된 같은 수가 있다면, 개수를 세서 저장하면 된다.

코드

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))
    
    if sum(a)!=sum(b):
        return 0
    
    c = []
    for i in range(n):
        x = a[i]
        cnt = 0
        while x%m==0:
            x //= m
            cnt += 1
        t = (x, m**cnt)
        if not c:
            c.append(t)
            continue
        if c[-1][0]==t[0]:
            c[-1] = (x, c[-1][1]+t[1])
        else:
            c.append(t)
            
    d = []
    for i in range(k):
        x = b[i]
        cnt = 0
        while x%m==0:
            x //= m
            cnt += 1
        t = (x, m**cnt)
        if not d:
            d.append(t)
            continue
        if d[-1][0]==t[0]:
            d[-1] = (x, d[-1][1]+t[1])
        else:
            d.append(t)
    
    if c==d:
        return 1
    return 0


for __ in range(int(input())):
    print('Yes' if solve() else 'No')

D. Permutation Graph

길이가 $n$인 $permutation$ 이 주어진다. $permutation$은 $1$부터 $n$까지 중복된 숫자 없이 구성된 배열이다. $permutation$으로 다음 조건을 만족하면 $edge$를 추가해서 그래프를 구성할 수 있다.

$p = [a_i,...,a_j]$ 라고 하면 $min(p)=a_i, max(p)=a_j$ 또는 $min(p)=a_j, max(p)=a_i$ 인 경우에 $i$와 $j$를 연결하는 $edge$를 추가한다.

우리는 $1$번 $vertex$에서 시작해서 $n$번 $vertex$로 가는 최단 경로를 찾아야 한다.

풀이

여러 풀이가 있고, 어떤 자료구조를 사용하냐에 따라 시간 복잡도가 갈린다.

이 문제의 전반적인 그리디함은 한 번의 이동에서 최대한 멀리 가야 한다. 이것의 정당성은 증명이 간단해서 넘어가도록 한다.

그리디와 투포인터를 이용한 풀이: $O(N)$

$p$의 길이가 $1$이면 시작과 끝이 같아서 최단 경로는 $0$.

$i$부터 $j$까지 잇는 간선이 있다고 하자. 이걸 $edge(i, j)$라고 하자. 그러면 $p[i:j]$를 $minmax$ 조건을 충족하는 하나의 구간이라고 생각할 수 있다.

$p[i]$는 $min(p[i:j])$거나 $max(p[i:j])$이다. $p[i] < p[i+1]$ 라면 $min(p[i:j])=p[i]$이고 $p[i]>p[i+1]$이라면 $max(p[i:j])=p[i]$이다.

$min(p[i:j]) = p[i]$인 경우를 보자. 우리는 가능한 $j$의 가장 큰 값을 구해야 한다. $i+1$부터 $n$까지 포인터를 움직이며 최대한 멀리 가보자. 이 포인터의 위치를 $k$라고 하자.

$p[k]=max(p[i+1:n])$일 때, $j=k$이다. $p[k+1:n]$에서 $p[k]$보다 큰 값이 없어서 간선이 연결될 수 없기 때문이다. 이 경우에 $edge(i, k)$가 존재한다.

$p[k] < p[i]$일 때, $j=k-1$이다. $p[k]<[i]$면 $min(p[i:j])=p[i]$라는 초기 조건이 충족되지 않기 때문이다.

$max(p[i:j]) = p[i]$인 경우는 반대로 하면 된다.

여기서 $min(p[i:j])$와 $max(p[i:j])$는 $p$가 $permutation$이라는 특성을 이용해 투포인터로 관리하면 된다.

코드

# 그리디, 투포인터 풀이 O(N)
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    if n==1:
        print(0)
        return 
    
    c = [1]*(n+1)
    c[a[0]] = 0
    p, q = n, 1
    ans = 0
    
    l, r = a[0], a[1]
    for i in range(1, n-1):
        
        while p>0 and c[p]==0:
            p -= 1
        while q<n and c[q]==0:
            q += 1
            
        c[a[i]] = 0
        
        if l < r:
            if r==p:
                ans += 1
                l, r = a[i], a[i+1]
                continue
        else:
            if r==q:
                ans += 1
                l, r = a[i], a[i+1]
                continue
        
        if l < r:
            if a[i+1] < l:
                ans += 1
                l, r = r, a[i+1]
            if a[i+1] > r:
                r = a[i+1]
        else:
            if a[i+1] > l:
                ans += 1
                l, r = r, a[i+1]
            if a[i+1] < r:
                r = a[i+1]
                
    print(ans+1)


for __ in range(int(input())):
    solve()

풀이

그리디와 분할정복, 세그먼트 트리를 이용한 $O(N\,logN)$

우리는 반드시 $max(p)$를 거쳐야 최적의 답을 구할 수 있다. $max(p) = a_i$를 하자. $i$는 $1$과 $n$이 아니라고 가정한다. 우리는 $1$번 $vertex$에서 시작해서 $i$번 $vertex$를 거쳐서 $n$번 $vertex$에 도달해야 한다. $2$개의 구간으로 나뉘게 된다. $p[1:i]$와 $p[i:n]$.

$p[1:i]$ 구간을 보자. $1$번 $vertex$ $\to ... \to$ $i$번 $vertex$로 이동해야 한다. $max(p[1:i]) = p[i]$이다. $i$번과 연결될 수 있는 가장 최적의 수는 $min(p[1:i])=j$이다.

그럼 또다시 $2$개의 구간으로 쪼개진다. $p[1:j]$와 $p[j:i]$. $p[j:i]$는 더이상 쪼갤 필요가 없고 $1$번의 이동하면 된다. 남은 건 $p[1:j]$이고, $min(p[1:j])=p[j]$이다. 위 작업을 계속 반복하면 된다.

$p[i:n]$ 구간도 동일하게 반복하면 된다.

특정 구간의 $min$, $max$를 구하는 건 세그트리를 이용해서 $O(N\,logN)$의 시간으로 구할 수 있다.

코드

// 그리디, 분할정복, 세그먼트 트리 풀이 O(N log N)
#include <bits/stdc++.h>
using namespace std;

vector<int> mintree;
vector<int> maxtree;
vector<int> arr;
vector<int> idx;

int mininit(int start, int end, int node)
{
    if (start == end)
        return mintree[node] = arr[start];
    return mintree[node] = min(mininit(start, (start + end) / 2, node * 2), mininit((start + end) / 2 + 1, end, node * 2 + 1));
}

int getmin(int start, int end, int node, int left, int right)
{
    if (end < left || right < start)
        return 1e9;
    if (left <= start && end <= right)
        return mintree[node];
    return min(getmin(start, (start + end) / 2, node * 2, left, right), getmin((start + end) / 2 + 1, end, node * 2 + 1, left, right));
}

int maxinit(int start, int end, int node)
{
    if (start == end)
        return maxtree[node] = arr[start];
    return maxtree[node] = max(maxinit(start, (start + end) / 2, node * 2), maxinit((start + end) / 2 + 1, end, node * 2 + 1));
}

int getmax(int start, int end, int node, int left, int right)
{
    if (end < left || right < start)
        return 0;
    if (left <= start && end <= right)
        return maxtree[node];
    return max(getmax(start, (start + end) / 2, node * 2, left, right), getmax((start + end) / 2 + 1, end, node * 2 + 1, left, right));
}

int run1(int n, int x)
{
    int f = 1, ret = 0;
    while (x > 0)
    {
        if (f)
            x = idx[getmin(0, n - 1, 1, 0, x)];
        else
            x = idx[getmax(0, n - 1, 1, 0, x)];
        ret++;
        f = !f;
    }
    return ret;
}

int run2(int n, int x)
{
    int f = 1, ret = 0;
    while (x < n - 1)
    {
        if (f)
            x = idx[getmin(0, n - 1, 1, x, n - 1)];
        else
            x = idx[getmax(0, n - 1, 1, x, n - 1)];
        ret++;
        f = !f;
    }
    return ret;
}

void solve()
{
    int n;
    cin >> n;

    arr.resize(n);
    idx.resize(n + 1);
    mintree.resize(n * 4);
    maxtree.resize(n * 4);

    for (auto &x : arr)
        cin >> x;

    for (int i = 0; i < n; i++)
        idx[arr[i]] = i;

    mininit(0, n - 1, 1);
    maxinit(0, n - 1, 1);

    int ans = 0;

    int mmax = idx[getmax(0, n - 1, 1, 0, n - 1)];

    ans += run1(n, mmax);
    ans += run2(n, mmax);

    cout << ans << '\n';

    arr.clear();
    idx.clear();
    mintree.clear();
    maxtree.clear();
}

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        solve();
}