Educational Codeforces Round 102 (Rated for Div. 2) A ~ D

codeforces.com/contest/1473

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

 

풀은 문제: A, B, C

못 풀은 문제: D, E, F, G

풀이만 보고 풀은 문제: D

풀이와 코드를 보고 풀은 문제:

 

 

 

난이도

A - 

B - 

C - 

D - 

E - 

F - 

G - 

 

 

 

 

 

C번 한번에 통과했으면 1000등은 올라가고 바로 민트로 올라갔을텐데 너무 삽질을 했다

 

D번은 prefix array를 만지작 거리다가 끝났는데 학회분들이랑 이야기하니까 suffix array도 필요하다고해서 매우 아쉬웠다.

D번을 처음보고 바로 세그트리가 생각났지만 세그먼트 트리 코드를 까먹어서 세그트리 구현은 바로 포기하고 다른 방법을 찾아보았는데 아쉬웠다. 세그먼트 트리인걸 알면서 놓치는 문제가 점점 생기는데 공부 좀 해야겠다.

그리고 코포 댓글을 보니까 평방분할로도 가능했다고 한다. 평방분할에 적용되는 문제들 유형을 보면 충분히 쓰일 수 있는 것 같다.

 

 

 

 

 

A. Replacing Elements

 

a[i]의 값을 a[j] + a[k]로 변경할 수 있을 때, 배열 a의 모든 값이 d이하로 만들 수 있냐는 문제이다.

이건 배열 a를 오름차순 정렬해서 a[0] + a[1] <= d이거나 max(a) <= d인지 확인하면 된다.

 

def main():
    for _ in range(int(input())):
        n,d = map(int,input().split())
        A = sorted([*map(int,input().split())])
        if max(A) <= d or A[0]+A[1] <= d:print('YES')
        else:print('NO')

 

 

 

 

B. String LCM

 

문자열 a와 문자열 b의 각 길이를 최소공배수로 늘려주고 둘이 문자가 같은지 비교하면 된다.

 

lcm(a,b) = a * b / gcd(a,b)

def main():
    def gcd(a, b):
        mod = a % b
        while mod > 0: a = b;b = mod;mod = a % b
        return b
    def lcm(a, b):
        return a * b // gcd(a, b)
    for _ in range(int(input())):
        s = input()
        t = input()
        x = lcm(len(s),len(t))
        s, t = s * (x//len(s)), t * (x//len(t))
        flag = True
        for i in range(len(s)):
            if s[i] != t[i]:flag = False
        if flag: print(s)
        else:print(-1)

 

 

 

 

C. No More Inversions

 

순열에 규칙성이 있을 것 같아서 k값을 고정해두고 n의 값을 계속 바꿔보니까

n = 5, k = 5 일 때 -> 1 2 3 4 5

n = 6, k = 5 일 때 -> 1 2 3 5 4

n = 7, k = 5 일 때 -> 1 2 5 4 3

n = 8, k = 5 일 때 -> 1 5 4 3 2

n = 9, k = 5 일 때 -> 5 4 3 2 1

이런식으로 규칙성이 있었다.

 

답은 1, 2, .. , k-1, k, k-1, .... , 2k - n 에서 k-1, .... , 2k - n 부분을 반대로 뒤집어야한다고 한다.

 

def main():
    for _ in range(int(input())):
        n, k = map(int,input().split())
        p = [i for i in range(1,k+1)][::-1]
        p = p[:n-k+1][::-1] + p[n-k+1:]
        print(*p[::-1])

 

 

 

 

 

D. Program

 

일단 prefix array와 suffix array에 들어갈 값은 x부터 y까지의 최대값과 최소값 그리고 지금까지 연산하여 나온 x의 값으로 3개가 필요하다.

prefix array로 1부터 l-1까지의 최대값, 최소값, x의 값을 구하고

suffix array로 r+1부터 n까지의 최대값, 최소값, x의 값을 구한다

그리고 둘이 붙여줘야하는데 prefix[l-1]일 때의 x의 값에 따라 suffix array의 시작 x의 값이 달라지므로 suffix의 최대값과최소값에 x만큼 더해주고, 두 배열의 최대값과 최소값을 구해서 개수를 계산하면 된다.

 

suffix array에 들어가는 x값은 아무데도 쓰이지 않지만 prefix array와 형태의 통일감을 주기 위해서 넣어주었다.

 

def main():
    for _ in range(int(input())):
        n,m = map(int,input().split())
        s = input()
        res1 = [[0,0,0] for _ in range(n)] #min, max, x
        res2 = [[0,0,0] for _ in range(n)] #min, max, x
        res1 = [[0,0,0]] + res1 + [[0,0,0]]
        res2 = [[0,0,0]] + res2 + [[0,0,0]]
        x = 0
        for i in range(1,n+1):
            if s[i-1] == '-':
                x -= 1
                res1[i] = [min(res1[i-1][0],x), res1[i-1][1],x]
            else:
                x += 1
                res1[i] = [res1[i-1][0],max(res1[i-1][1],x),x]
        for i in range(n,0,-1):
            if s[i-1] == '-':
                res2[i] = [min(res2[i+1][0]-1,0),max(res2[i+1][1]-1,0),x]
            else:
                res2[i] = [min(res2[i+1][0]+1,0),max(res2[i+1][1]+1,0),x]
        for i in range(m):
            l,r = map(int,input().split())
            a,b = res1[l-1],res2[r+1]
            MIN = min(a[0],b[0]+a[2])
            MAX = max(a[1],b[1]+a[2])
            print(MAX-MIN+1)