Educational Codeforces Round 58 (Rated for Div. 2) A ~ E

codeforces.com/contest/1101

Dashboard - Educational Codeforces Round 58 (Rated for Div. 2) - Codeforces

풀은 문제: A, B, C, E

못 풀은 문제: D, F, G

풀이만 보고 풀은 문제:
풀이와 코드를 전부 본 문제: D

 

 

난이도

A - 1000

B - 1300

C - 1500

D - 2000

E - 1500

F - 2400

G - 2300

 

 

Python 3, Pypy 3 Fast IO

import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading
MAX = 10 ** 9

def main():
    return


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    """sys.setrecursionlimit(400000)
    threading.stack_size(40960000)
    thread = threading.Thread(target=main)
    thread.start()"""
    main()

 

 

 

 

A. Minimum Integer

x이상 y이하의 범위 [x, y]가 있고, 정수 z가 있을 때 [x, y]에 속하지 않으면서 z로 나누어 떨어질 수 있는 가장 작은 수를 구하면 되는 문제이다.

 

그러면 어떤 수 k가 있을 때 k < x이면서 z로 나누어 떨어질 수 있는 가장 작은 수를 구하거나, k > y이면서 z로 나누어 떨어질 수 있는 가장 작은 수를 구하면 된다.

만약 z < x이면 k = z가 될 것이고, k > y이면 y를 z로 나눈 몫에 1을 더하고 z를 곱한 값이다. k = {(y // z) + 1} * z

 

def main():
    for _ in range(int(input())):
        l,r,d=map(int,input().split())
        if d < l: print(d)
        else:print((r//d+1)*d)

 

 

 

B. Accordion

아코디언은 [: 로 시작하고 :]로 끝난다고 한다. 그리고 중간에 | 라는 문자가 들어갈 수 있다. 어떤 문자열을 주어질 때, 문자들을 삭제하여 얻을 수 있는 아코디언 최대의 길이를 구하는 문제이다. 이때 주의할 점은 최소 아코디언의 길이는 [::]로 :가 2개가 필요하다.

 

그러면 만약 [: :] 가 있을 때 중간에 |가 많이 들어가려면, 문자열 처음부터 시작해서 가장 가까이 있는 [와 [보다 멀리있는 :의 위치를 구하면 되고, 문자열 끝에서 시작해서 문자열 끝과 가장 가까이 있는 ]와 ]보다 멀리있는 :를 구하면 된다.

그다음 [:와 :]를 구했으면 중간에 있는 |의 개수를 구해주면 된다.

 

그래서 풀이 방법은 a, b, c, d, e = -1, -1, -1, -1, 0 라는 변수들을 만들어준다.

a = 첫 문자와 가장 가까이 있는 [ 의 위치

d = 마지막 문자와 가장 가까이 있는 ]의 위치

 

b = 첫 문자와 가장 가까이 있으면서도 [ 와 ] 사이에 있는 :의 위치

c = 마지막 문자와 가장 가까이 있으면서도 [ 와 ] 사이에 있는 :의 위치

 

e = [:와 :] 사이에 있는 |의 개수

 

이렇게 해서 for문으로 구해준다음

만약 아코디언의 최소 길이인 [: :]를 만족하지 못한다면 -1을 출력하고, [: :]를 만족하면 4 + e를 출력한다.

 

def main():
    a,b,c,d,e = -1,-1,-1,-1,0
    s = input()
    for i in range(len(s)):
        if s[i] == '[' and a == -1: a = i
        if s[len(s)-1-i] == ']' and d == -1: d = len(s)-1-i
    for i in range(len(s)):
        if s[i] == ':' and a < i < d and b == -1: b = i
        if s[len(s)-1-i] == ':' and a < len(s)-1-i < d and c == -1: c = len(s)-1-i
    for i in range(len(s)):
        if s[i] == '|' and b < i < c: e += 1
    if min(a,b,c,d) == -1 or not(a < b < c < d) : print(-1)
    else: print(4 + e)

 

 

 

 

 

C. Division and Union

 

숫자들이 겹치지 않게 구역을 2개로 나눌 수 있느냐 없느냐를 묻는 문제이다.

 

그래서 l, r 입력값이 들어올 때, index 번호도 리스트에 넣어서 l 기준으로 오름차순, l값이 같으면 r을 내림차순으로 정렬하였다.

 

이러면 먼저 최소의 l값일 때, 최대의 r값을 얻을 수 있다.

이때의 값을 각각 x1, y1이라고 한다.

그 후엔 x1 <= l <= y1이라면 y1의 값을 max(y1, r)로 갱신하고 구역 1에 보낸다.

그 이후 l > y1의 값이 나온다면 이제 구역 2로 보내고, x2, y2 = l, r을 저장해둔다. 이 값은 나중에 x2 == -1, y2 == -1 일 때 NO를 출력할 때 쓰이는 항목이라 값을 갱신해주지 않아도 된다. 이 이후 값들은 전부 구역2에 해당하는 값들이다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        D = []
        ans = [-1]*n
        for i in range(n):
            l,r = map(int,input().split())
            D.append([l,r,i])
        D.sort(key = lambda a: [a[0],-a[1]])
        x1, y1, x2, y2 = -1, -1, -1, -1
        for i in range(len(D)):
            if x1 == -1:
                x1, y1 = D[i][0], D[i][1]
                ans[D[i][2]] = 1
            else:
                if D[i][0] > y1 or x2 > y1:
                    if x2 == -1: x2, y2 = D[i][0], D[i][1]
                    ans[D[i][2]] = 2
                else:
                    y1 = max(y1,D[i][1])
                    ans[D[i][2]] = 1
        if x2 == -1:print(-1)
        else:print(*ans)

 

 

 

 

D. GCD Counting

g(x, y)는 x와 y를 포함하는 x와 y 사이의 모든 정점의 최대 공약수이고, dist(x, y)는 x, y를 포함하는 x와 y사이의 모든 정점의 개수이다. 이때 g(x, y) > 1인 값 중에서, dist(x, y)가 최대인 값을 구하는 문제이다.

 

일단 먼저 알아야할 내용은 당연하지만 1을 제외한 최대공약수는 소수로 나누어 떨어지는 값들인 점을 알아야한다.

그리고 dist(x, y)를 구하는 문제는 리프노드부터 출발하여 간선을 없애면서 나아가는 BFS/DFS를 이용하면 된다.

 

코드는 먼저 소수를 구하는 알고리즘을 짠 후, a배열의 값들을 소인수 분해하여 어떤 소수들로 나누어지는지 D배열에 각각 저장한다. 그다음 리프노드들을 구하여 큐에 넣어준다음, BFS를 돌리면서 간선을 없애주고 정점 x와 정점 y에 공통된 소수를 가지고 있는지 확인하여 x -> y로 이동중이면 y에 있는 소수의 너비에 x가 그동안 움직여서 획득한 너비만큼을 해준다. 이 너비가 dist(x,y)이다.

간선은 n-1개이고, 노드는 n개 이므로 BFS는 간선을 없애면서 이동하므로 n-1번 돌아간다.

 

 

코드는 48252706를 보고 이해했다.

 

def main():
    ans = 1
    flag = True
    primes = []
    for i in range(2, 500):
        v = 1
        for p in primes:
            if i % p == 0: v = 0
        if v: primes.append(i)

    n = int(input())
    a = [*map(int,input().split())]
    D = [[] for _ in range(n)]
    if sum(a) == n: flag = False
    for i in range(n):
        x = a[i]
        for p in primes:
            if x % p == 0:
                D[i].append([p,1])
                x = x//p
                while x % p == 0: x //= p
        if x != 1:D[i].append([x,1]) #아래에 설명

    adj = [[] for i in range(n)]
    for i in range(n-1):
        x, y =map(int,input().split())
        adj[x-1].append(y-1)
        adj[y-1].append(x-1)

    leaf = []
    for i in range(n):
        if len(adj[i]) == 1: leaf.append(i)

    for i in range(n-1):
        x = leaf.pop()
        y = adj[x][0]
        adj[y].remove(x)
        if len(adj[y]) == 1: leaf.append(y)
        for nx in D[x]:
            for ny in D[y]:
                if nx[0] == ny[0]:
                    ans = max([ans, nx[1] + ny[1]]) #아래에 설명
                    ny[1] = max([ny[1],nx[1]+1]) #아래에 설명

    if not flag:print(0)
    else:print(ans)

 

 

if x != 1: D[i].append([x,1]) 이 부분은 소수를 sqrt(200000) < 500 까지만 구했는데, 만약 소수들로 나누어지지 않는다면 그것은 500이상의 소수이므로 D[i]에 추가하도록 하였다.

 

ans = max(ans, nx[1] + ny[1])과 ny[1] = max(ny[1], nx[1]+1)은 만약 부모노드의 자식노드가 2개가 있을 때, 아래 사진을 봐보자

 

 

 

 

여기서는 dist(8, 12) = 7 이 답이다.

그래서 ans = max(ans, nx[1] + ny[1]) 이 들어가는 것은 이해가 갈 것이다.

그런데 ny[1] = max(ny[1], nx[1]+1) 이 부분은 뭐냐면 만약 2의 부모노드 14가 있다면 14와 2의 최대공약수는 2이므로 2의 자식 노드중에 하나를 택해야한다.(아래사진) 그래서 이때 ny[1] = max(ny[1], nx[1]+1)을 사용해야 정상적으로 답을 구할 수 있다.

 

 

 

 

 

 

 

 

 

 

E. Polycarp's New Job

h x w의 너비로 된 지폐가 있을 때, 입력값이 + h w면 지갑에 h x w의 넓이를 가진 지폐를 넣고, 입력값이 ? h w면 지갑에 높이가 h, 너비가 w이하인 지폐들만 있으면 'YES', 아니면 'NO'를 출력하는 문제이다.

 

일단 지폐들은 90도로 회전시켜서도 넣을 수 있으니 h,w 값중 작은 값을 h, 큰 값을 w로 해서 지폐에 넣어준다.

그리고 ? h w를 물어볼 때, 이것도 역시 h, w값중 작은 값을 h, 큰 값을 w로 해줘서 h x w 이하의 지폐만 있는지 확인하면 된다.

 

def main():
    h, w = 0, 0
    for _ in range(int(input())):
        a,b,c = input().split(); b = int(b); c = int(c)
        x, y = min(b, c), max(b, c)
        if a== '+':
            h = max(h, x)
            w = max(w, y)
        else:
            if x >= h and y >= w: print('YES')
            else:print('NO')