Codeforces Round 898 (Div. 4) (버추얼)

 

이번에는 2시간 30분 짜리 셋이었는데, 문제는 총 8문제 있었다.

 

이번에는 친구 2명과 함께 시작했다.

 

 

저번과 마찬가지로 이번에도 올솔에 성공했다!

 

문제 모음

https://codeforces.com/contest/1873

 

 

A번 문제

abc 3글자가 순서가 바뀐 채로 주어진다. 단 한번 두 글자를 스왑했을 때 abc로 만드는게 가능하면 YES 불가능하면 NO 이다.

예시로 cba는 a와 c를 스왑하면 abc를 만들 수 있다. cab의 경우 스왑 한번으로 abc를 만들 수 없다.

 

리뷰때 풀이가 크게 2개가 나왔는데

cab와 bca 가 아니면 모두 YES, abc 순서에 맞지 않는 자리의 수가 3개면 NO 이 두 가지 정도였다.

(대충 제출했다 1WA 적립..)

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
 
for _ in range(int(input())):
    s=input().rstrip()
    if s in ["bca","cab"]:
        print("NO")
    else:
        print("YES")

B번 문제

n개의 숫자가 주어진다. 주어진 숫자들 중 하나에 +1을 해서 수 전체의 곱이 최대가 되도록 하는 문제였다.

그냥 가장 작은 숫자에 곱해주면 된다. 다 같은 경우, 0인 경우, 오름차순인 경우 모두 가장 작은 숫자를 올리는 것이 가장 컸다.

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
 
for _ in range(int(input())):
    n=int(input())
    arr=sorted(map(int,input().split()))
    arr[0]+=1
    ans=1
    for i in range(n):
        ans*=arr[i]
    print(ans)

C번 문제

이러한 형태의 과녁이 주어진다. 

입력은 이렇게 주어지는데 X가 과녁을 맞춘 부분이라 치고, 점수를 계산하는 문제다.

(i,j)가 좌표라 했을 때 min(i,j)가 점수이다. 좌표가 0~4일때 이게 성립하는데 5를 넘어가면 9에서 빼주는 식으로 반전시켜줘서 해결했다. 10*10이니까 그냥 쌩구현으로도 풀릴 것 같다. 1111222333444 하면서..

for i in range(int(input())):
    arr=[input().rstrip() for i in range(10)]
    case=[]
    for i in range(10):
        for j in range(10):
            if arr[i][j]=='X':
                case.append((i if i<5 else 9-i,j if j<5 else 9-j))
    ans=0
    for x,y in case:
        ans+=(1+min(x,y))
    print(ans)

D번 문제

어째선지 최근 많이 보는 듯한 유형이다. 구멍이 있고, 구멍을 덮는 문제인데 덮을 수 있는 덮개의 너비가 주어지고 최소한으로 사용했을 때 몇개의 덮개를 쓰는지 구하는 문제다.

 

굳이 어렵게 생각할 필요 없이 처음 구멍부터 차근차근 채워주면 풀린다. i,j가 있을 때 덮개의 너비가 k면 i+k가 j보다 작으면 어차피 j는 따로 채워줘야 하고, i+k보다 작은 j는 그냥 넘어가면 된다. 따라서 현재 덮고 있는 부분만 구해주고 그 값만 갱신해주면 된다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=input().rstrip()
    cov=-1
    ans=0
    for i in range(n):
        if cov<i:
            if arr[i]=='B':
                cov=i+(k-1)
                ans+=1
    print(ans)

E번 문제

이 사진에서 h를 구하는 문제다. h는 수조의 벽면의 높이이다. h가 즉 수면의 높이이고, 저렇게 배열 안의 블럭들의 높이가 주어지므로 수면과 바닥의 차이만큼 물이 들어있게 된다. 그 물의 총량이 w라 했을 때 맨 처음 입력으로 들어오는 k보다 작으면서 최대가 되도록 하는 h를 구하는 문제이다.

 

숫자가 커서 h를 1씩 늘려서는 해결이 안되고, 간단하게 매개변수탐색으로 h를 구할 수 있다.

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

def check(h):
    s=0
    for i in arr:
        s+=max(h-i,0)
    return s


for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))

    lo=0
    hi=10**10

    while lo<=hi:
        mid=(lo+hi)//2
        if check(mid)<=k:
            lo=mid+1
        else:
            hi=mid-1
    print(hi)

F번 문제

개인적으로 나한테는 가장 어려웠던 문제,

가치랑 높이 배열이 각각 주어진다.

가치의 합이 k를 넘지 않도록 최대한 긴 연속 부분을 구하면 되는데

여기까지는 일반적인 투 포인터 문제이다.

 

k는 10 가치가 5 4 3 2 1 이면 답은 (4,3,2,1) 로 4다.

 

근데 이 문제의 특이한 점은 높이 배열이 주어지는 것인데 이 높이 배열에 들어있는 h[i-1]이 h[i]로 나누어떨어지지 않으면 가져갈 수 없다.

 

따라서 k가 10 가치 배열이 5 4 3 2 1 높이 배열이 4 4 3 2 5 면 답은 (5,4)로 2이다. 나머지는 앞 높이와 나누어떨어지지 않아서 가져갈 수 없다.

 

이분 탐색, 매개변수탐색, 투포인터 문제를 풀 때 내 스타일을 정형화 시켜놓지 않고 보통 꼬라박으면서 푸는 편이라 이번에도 굉장히 고생했다. 마지막 문제보다 여기서 시간을 더 썼다.

 

가치 하나가 k보다 크거나, 높이 배열끼리 나누어 떨어지지 않으면 그냥 기존의 가지고 있던걸 싹 다 버린다는 느낌으로 코드를 짰다.

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for i in range(int(input())):
    n,k=map(int,input().split())
    v=list(map(int,input().split()))
    h=list(map(int,input().split()))
    p1=0
    s=0
    cnt=0
    ans=0
    for p2 in range(n):
        if p2 and h[p2-1]%h[p2]:
            s=0
            p1=p2
        s+=v[p2]
        while k<s and p1<=p2:
            s-=v[p1]
            p1+=1
        ans=max(p2-p1+1,ans)

    print(ans)

G번 문제

A와 B로만 이루어진 문자열이 주어진다.

문자열에 다음과 같은 연산을 할 수 있는데 AB를 BC로 바꾼다. BA를 CB로 바꾼다. 이 연산을 하면 +1점을 얻는다.

얻을 수 있는 점수의 최대값을 구하는 문제인데

 

AAAB는 AAAB -> AABC -> ABCC -> BCCC 이렇게, BAAA는 BAAA-> CBAA -> CCBA -> CCCB 이렇게 바꿀 수 있다.

결국 중요한건 B와 연결되어있는 A의 개수인데, 뭔가 경우의 수가 많은 느낌이지만 잘 생각해보면 B는 자신과 연결된 왼쪽 혹은 오른쪽의 A들의 그룹을 고를 수 있다. AABAAA의 경우 오른쪽을 골라야 이득인 것처럼, AABAAABAAAA 이런 예시도 생각해볼 수 있다. 결국 B의 개수만큼 A의 그룹을 고를 수 있다는 것이다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *

for _ in range(int(input())):
    s=input().rstrip()
    acnt=0
    bcnt=0
    ans=0
    ss=sorted([i.count("A") for i in s.split('B')],reverse=True)
    for i in range(s.count("B")):
        ans+=ss[i]
    print(ans)

 

H번 문제

이 문제 굉장히 좋았던 것 같다. 이번 대회에서 가장 좋은 문제였다고 생각한다.

 

플레이어 2명이 있다. 각 플레이어는 각각 지정된 위치 a, b 번 노드에서 시작하며, a에서 시작하는 플레이어가 b에서 시작하는 플레이어를 잡아야 한다. 한 번에 한 칸씩 이동이 가능하고, 이동하지 않고 머무르는 것도 가능하다. 위 게임이 그래프에서 진행되는데 게임이 진행되는 그래프의 특성은 다음과 같다.

 

n개의 노드 n개의 간선이 존재한다. 모든 노드에 대해 한 노드 u1을 골랐을 때 다른 노드 u2로 가는 경로가 무조건 존재한다.

 

두 플레이어 모두 최선의 선택을 한다.

이러한 n=4그래프에서 각각 1, 3번에서 시작한다 했을 때 a 플레이어는 b 플레이어를 잡을 수 없다. 1->2 로 가면 3->4 이렇게 이동해버리고 뻉뺑 돌면 그만이다.

 

저렇게 돌 수 있는 부분을 안전지대라고 부르겠다.

 

그래프에 안전지대는 n>2인 그래프에 적어도 하나씩은 존재한다. n개의 노드를 안전지대가 생기지 않도록 n-1개의 에지를 사용해 일렬로 세워도, 마지막 n번째 에지를 추가하면 결국 크기가 3인 안전지대가 하나는 생긴다.

 

안전지대가 무조건 존재함을 확인 했으니, b 플레이어는 a 플레이어가 안전지대를 모두 점거하기 전에 안전지대에 도착해야 한다. 

 

이러한 그래프에서 a 플레이어가 2, b 플레이어가 5에서 시작하는 경우에 b플레이어가 안전지대로 들어오기 위한 3번 노드에 a 플레이어가 점거하게 되면 b번 플레이어는 이길 수 없다. 그러므로 a, b번 위치에서 bfs를 돌려서 b번 플레이어가 a번 플레이어가 길을 막기 전에 안전지대에 도착 할 수 있는지 판별하면 된다.

 

그럼 이제 안전지대에 해당하는 노드를 찾기만 하면 된다. 그런데 안전지대에 해당하는 노드를 어떻게 찾을까?

 

위상정렬을 풀 듯이 연결된 노드의 개수가 1개인 노드들을 찾는다. 그리고 그 노드들을 제거한다. 그러면 이제 연결된 노드의 개수가 1개인 노드가 생겼다면 위 과정을 반복한다. 그러다 보면 안전지대에 속하는 노드들을 제외한 모든 노드를 구할 수 있다.

 

from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(3000)
from collections import deque,defaultdict
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
from math import *
 
for _ in range(int(input())):
    n,a,b=map(int,input().split())
    con=[0]*(n+1)
    graph=[[] for i in range(n+1)]
    safeArea=[1]*(n+1)
    for _ in range(n):
        u,v=map(int,input().split())
        con[u]+=1
        con[v]+=1
        graph[u].append(v)
        graph[v].append(u)
    
    toplo=deque([])
    for i in range(1,n+1):
        if con[i]==1:
            toplo.append(i)
 
    while toplo:
        now=toplo.popleft()
        safeArea[now]=0
        for nxt in graph[now]:
            con[nxt]-=1
            if con[nxt]==1:
                toplo.append(nxt)
    
    queue1=deque([a])
    queue2=deque([b])
    vi=[0]*(n+1)
    vi[b]=2
    vi[a]=1
    ans=False
    while queue1 or queue2:
        le1=len(queue1)
        for i in range(le1):
            now=queue1.popleft()
            for nxt in graph[now]:
                if vi[nxt]==0:
                    vi[nxt]=1
                    queue1.append(nxt)
        
        le2=len(queue2)
        for i in range(le2):
            now=queue2.popleft()
            if safeArea[now] and vi[now]!=1:
                ans=True
            for nxt in graph[now]:
                if vi[nxt]==0:
                    vi[nxt]=2
                    queue2.append(nxt)
    if ans:
        print("YES")
    else:
        print("NO")

 

 

H번 까지 푸는데 딱 2시간 걸린 것 같다.

 

 

퍼포는 저번이랑 비슷하게(?) 나온 것 같다. 퍼플퍼포 한번 띄워보나 싶었는데 역시 퍼플의 벽은 높았다.