AtCoder Beginner Contest 406 대충 복기(증가하다가 감소하는 수열의 개수)

1. D번

 

https://atcoder.jp/contests/abc406/tasks/abc406_d

D - Garbage Removal

 

 

H*W 배열에서 (x,y) 위치에 쓰레기가 N개 주어진다.

 

Q개의 쿼리가 다음과 같이 주어진다.

 

1 x는 x행의 모든 쓰레기 수를 출력하고, x행의 쓰레기를 모두 제거

 

2 y는 y열의 모든 쓰레기 수를 출력하고, y열의 쓰레기를 모두 제거

 

 

먼저 x행, y열 별로 각각 쓰레기들을 모아둔다.

 

1 x가 주어지면 x행의 쓰레기들을 조회해서 제거하지 않은 개수를 출력하고 제거 여부를 표시해둔다.

 

2 y가 주어지면 y열의 쓰레기들을 조회해서 제거하지 않은 개수를 출력하고, 제거 여부를 표시해둔다

 

이러면 제곱시간이 걸릴것 같은데, 시간안에 동작할 수 있는 이유는?

 

(x,y) 쓰레기를 x행, y열 최대 2번만 검사하기 때문에 가능하다.

 

이렇게 단순하게 해도 시간안에 돌더라고?

 

h,w,n = map(int,input().split())

X = {}
Y = {}

for _ in range(n):
    
    x,y = map(int,input().split())
    
    if X.get(x,0) == 0:
        
        X[x] = set()
    
    X[x].add((x,y))

    if Y.get(y,0) == 0:
        
        Y[y] = set()

    Y[y].add((x,y))
    
q = int(input())

for _ in range(q):
    
    a,b = map(int,input().split())

    if a == 1:
        
        print(len(X.get(b,[])))

        for x,y in X.get(b,[]):
            
            Y[y].remove((x,y))
        
        if X.get(b,[]) != []:

            del X[b]
    
    else:
        
        print(len(Y.get(b,[])))

        for x,y in Y.get(b,[]):
            
            X[x].remove((x,y))
        
        if Y.get(b,[]) != []:
        
            del Y[b]

 

 

혹은 다음과 같이, 행 제거 여부 배열, 열 제거 여부 배열, 쓰레기 제거 여부 배열을 두고

 

X[x]는 x행에 존재하는 쓰레기 번호

Y[y]는 y열에 존재하는 쓰레기 번호

 

remove[i] = i번 쓰레기 제거 여부

 

remove_row[i] = i행 제거 여부

remove_col[i] = i열 제거 여부

 

 

i행을 제거하면 remove_row[i] =1로 표시해서 다시는 i행을 검사하지 않도록,

 

remove_col[i] = 1로 표시해서 다시는 i열을 검사하지 않도록

 

X[x]나 Y[y]를 돌면서 i번 쓰레기를 제거했다면, remove[i] = 1로 표시해서 다시는 i번 쓰레기를 검사하지 않도록

 

h,w,n = map(int,input().split())

X = [[] for _ in range(h+1)]
Y = [[] for _ in range(w+1)]
remove = [0]*n

for i in range(n):

    x,y = map(int,input().split())

    X[x].append(i)
    Y[y].append(i)

remove_row = [0]*(h+1)
remove_col = [0]*(w+1)

q = int(input())

for _ in range(q):

    a,b = map(int,input().split())

    if a == 1:
        
        count = 0

        if remove_row[b] == 0:

            for i in X[b]:

                #(b,y)
                if remove[i] == 0:
                    
                    count += 1
                    remove[i] = 1

            remove_row[b] = 1
        
        print(count)

    else:

        count = 0

        if remove_col[b] == 0:

            for i in Y[b]:

                if remove[i] == 0:
                    
                    count += 1
                    remove[i] = 1

            remove_col[b] = 1

        print(count)

 

 

여기서 h,w가 20만이기 때문에 remove = [[0]*(w+1) for _ in range(h+1)]로 초기화해서,

 

(x,y) 좌표별로 제거 여부를 추적한다면 메모리 초과로 에러난다

 

메모리가 충분하다고 하더라도, 애초에 h,w가 20만으로 크기 때문에 remove 배열을 초기화하는데도 시간이 오래걸린다

 

어쨌든 핵심은, x행별로 모으고 y열별로 모으고,

 

(x,y)의 쓰레기는 최대 2번 검사하므로 시간안에 돈다는 것

 

 

 

2. C번

 

https://atcoder.jp/contests/abc406/tasks/abc406_c

C - ~

 

 

A1,A2,...AN 수열이 주어지는데, 길이가 4 이상이고 P1 < P2이고 수열 (P1,P2,...,PM)에서 유일하게 극대점이 하나 존재하고,

 

유일하게 극소점이 하나 존재하는 수열 P의 개수를 구한다.

 

극대점은 Pi-1 < Pi > Pi+1인 점 Pi를 말하고, 극소점은 Pi-1 > Pi < Pi+1인 점 Pi를 말한다.

 

---------------------------------------------------------------------------------------------------------------------------------------------------------

 

깔끔한 풀이?는 DP인데

 

dp1[i] = 점 i를 끝점으로 하는 연속하는 증가하는 부분 수열의 개수

 

dp2[i] = 점 i를 끝점으로 하는, 유일하게 극대점이 하나 존재하고 극소점은 존재하지 않는 수열의 개수

 

dp3[i] = 점 i를 끝점으로 하는, 문제에서 구하고자 하는 부분 수열의 개수

 

그러면 dp1[0] = 0, dp2[0] = 0, dp3[0] = 0이다.

 

여기서 핵심은 처음 P1 < P2인 수열을 구해야하므로, 극소점이 존재하다가 극대점이 존재하는 것은 불가능하다.

 

왜냐하면 P1 < P2를 만족하므로, 계속 증가한다면 P1 < P2 < .... Pi

 

그러다가 감소하면 P1 < P2 < ... < Pi > Pi+1...로 반드시 극대점이 먼저 생길 수밖에 없다.

 

 

이제 Pi-1 < Pi로 증가한다고 해보자.

 

그러면 i-1번까지 본 증가하는 수열 dp1[i-1]개의 끝에 Pi를 붙이면 되므로, dp1[i] = dp1[i-1] + 1

 

i-1번까지 본 극대점이 존재하는 수열 dp2[i-1]개는 현재 감소하고 있기 때문에, 끝에 증가하는 Pi를 붙이면 감소하다가 증가하므로 극소점이 하나 생기고,

 

또 이미 극대점 존재하고, 극소점이 존재하는 수열 dp3[i-1]개의 끝에는 Pi를 붙여도 계속 증가하므로

 

dp3[i] = dp2[i-1] + dp3[i-1]

 

그리고 현재 증가하고 있으므로, 극대점은 생길 수 없으니 dp2[i] = 0

 

왜냐하면 dp1[i]에는 증가하는 수열만 있고, dp3[i]에는 극소점이 존재하므로 dp2[i]와 연결될 수 없고 

 

dp2[i-1]에는 극대점이 존재해서 감소하고 있으므로, Pi를 붙이면 극소점이 생겨버려서 연결지을 수 없음

 

 

다음 Pi-1 > Pi로 감소한다고 해보자.

 

더이상 증가하는 수열이 아니므로, dp1[i] = 0

 

그리고 i-1번까지 본 증가하는 부분 수열 dp1[i-1]에 Pi를 붙이면 극대점이 생긴다.

 

그리고 극대점이 존재하는 수열 dp2[i-1]에 감소하는 값을 붙여도 여전히 극대점이 존재하는 수열이 되므로, dp2[i] = dp1[i-1] + dp2[i-1]

 

극대점이 존재하다가 극소점이 존재하는 수열 dp3[i] = 0이다.

 

왜냐하면 dp3[i-1]은 극대점이 생기다가 극소점이 생기고 있어서 현재 증가하고 있는 상태이므로 감소하는 Pi를 붙이면 극대점이 2개 생겨서 안된다.

 

n = int(input())

P = list(map(int,input().split()))

#dp1[i]: i를 끝점으로 하는 증가하는 부분수열의 개수
dp1 = [0]*n

#dp2[i]: i를 끝점으로 하는 산형 부분 수열의 개수
#처음은 증가하다가, 중간에 유일하게 극대점을 가지고 극소점은 가지지 않는 수열
dp2 = [0]*n

#dp3[i]: i를 끝점으로 하는 구하고자 하는 부분 수열의 개수
dp3 = [0]*n

for i in range(1,n):
    
    if P[i] > P[i-1]:
        
        dp1[i] = dp1[i-1] + 1
        dp3[i] = dp2[i-1] + dp3[i-1]
        dp2[i] = 0
    
    else:
        
        dp2[i] = dp1[i-1] + dp2[i-1]
        dp1[i] = 0
        dp3[i] = 0

print(sum(dp3))

 

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

dp도 어렵긴한데 공식해설도 쉽지는 않다

 

수열 P1,P2,...,PN에 대하여 Pi < Pi+1이면 Si = <으로 두고, Pi > Pi+1이면 Si = >으로 둬서 수열 S로 변형한다.

 

예를 들어 

 

1 3 6 4 2 5는 < < > > <이다.

 

문제에서 요구하는 수열은 처음에 증가하다가 < < < < < ... 

 

1번 감소하고 < < < < < > > > > > ....

 

1번 다시 증가하고 그대로 쭈욱 증가해야한다.

 

< < < < < > > > > > < < < < < ... <

 

이 수열을 자세히 보면

 

< < < < < ///// > > > > > > ////// < < < < < < ...

 

<와 < 사이에 >이 들어가는 수열이다.

 

이제 수열 S를 다음과 같이 압축한다

 

< < > > < 을 <2 >2 <1

 

각 부호의 연속하는 개수를 세서 옆에 기억해준다.

 

i번째 >을 기준으로 바로 양 옆에 <의 개수를 찾으면 i-1번째에 <이 존재한다면, 그것의 개수가 a개이고,

 

i+1번째 <이 존재한다면, 그것의 개수가 b개라고 하자.

 

그러면 연속하는 부분 수열의 개수는 >을 기준으로 왼쪽에서 a개의 <중 선택하고 오른쪽에서 b개의 <중 선택해서 조합하면 되므로,

 

a*b개이다.

 

n = int(input())

P = list(map(int,input().split()))

S = []

for i in range(n-1):
    
    if P[i] < P[i+1]:
        
        S.append('<')
    
    else:
        
        S.append('>')

SS = []

c = S[0] 
x = 0

for i in range(len(S)):
    
    if S[i] == c:
        
        x += 1
    
    else:
        
        SS.append((c,x))
        c = S[i]
        x = 1

SS.append((c,x))

count = 0

for i in range(1,len(SS)-1):
    
    if SS[i][0] == '>':
        
        if SS[i-1][0] == '<' and SS[i+1][0] == '<':
            
            count += (SS[i-1][1] * SS[i+1][1])

print(count)

 

다시 보니까 이 풀이가 더 지리는 것같은