solved.ac Grand Arena #3 div2 문제 후기

재밌었고 난이도도 적절했다. 하지만 골드중상위 문제가 증발한건 아쉽다. div1과 달리 div2는 난이도 정렬이었다.

 

A

https://www.acmicpc.net/problem/30802

30802번: 웰컴 키트

 

풀이과정

티셔츠 정보는 배열로 받던가 a,b,c,d,e로 받자.

티셔츠는 각 사이즈에 대해 정수 나눗셈(int or // if python)을 하면 된다. 나머지가 발생한다면 +1을 해주자. 그러고 다 합해주자.

연필은 몫과 나머지(// %)연산자를 이용해 그대로 출력하자.

 

B

https://www.acmicpc.net/problem/30803

30803번: 수도꼭지

 

시점 i에 현재 나오는 양이 S = A1 + A2 + ... + An이라고 하자.

만약에 Aj가 나오는 상태인데 j번째 수도꼭지를 잠군다면 Si+1 = Si - Aj이다.

Aj가 나오지 않는 상태인데 j번째 수도꼭지를 연다면 Si+1 = Si + Aj 이다.

Aj를 변경시킬때를 생각하자.

Aj가 나오지 않는 상태라면 Aj = x 로 갱신만 해주자.

Aj가 나오는 상태라면

1. Si+1 = Si - Aj

2. Aj = x

3. Si+1 = Si+1 + Aj

를 해주면 된다.

그렇다면 쿼리를 O(1)에 처리 가능하다.

 

C

https://www.acmicpc.net/problem/30804

30804번: 과일 탕후루

O(N)풀이가 존재하는 것 같으나 대회땐 이렇게 풀었다.

1. i~j를 이용해 만든 탕후루의 과일 종류 갯수는 i~j+k (k>0)을 이용해 만든 과일 종류 갯수 이하이다.

2. 최대 과일 갯수를 구하는 것이다. 1번에 의해 매개변수 탐색이 가능하다.

3. 각 매개변수에 대해, 슬라이딩 윈도우 테크닉을 사용한다.

Ai~Ai+k의 과일 종류별 갯수 데이터 Di를 알고있다고하자. Ai+1~Ai+k+1의 과일 종류별 갯수 데이터 Di+1는 다음과 같이 구할 수 있다.

3-1 Di에서 Ai과일 종류의 개수를 하나 뺸다. 만약 0이된다면 과일종류가 하나 줄어든 것이다.

3-2 Di에서 Ai+k+1과일 종류의 개수를 하나 더해준다. 만약 1이된다면 과일종류가 하나 늘어난 것이다.

3-3 과일종류의 개수가 2이하라면 True를 리턴한다.

 

D

https://www.acmicpc.net/problem/30805 

30805번: 사전 순 최대 공통 부분 수열

재밌었던 문제이다.

최대 공통 부분 수열을 구하는 알고리즘을 이용해 풀 수 있다곤 하지만, 난 그리디한 풀이를 사용했다.

사전순으로 맨 나중이므로 어떻게든 큰 순서대로 최대한 많이 추가해야하기 때문에 그리디한 풀이를 생각했다.가장 큰것 부터 보면서, 큰 것을 최대한 많이 추가해준다. 그 다음 큰 것도 똑같은 과정을 수행한다.

배열에 나올 수 있는 정수의 종류는 최대 100개이다.

indexX[t]: 배열X에서 Xi가 t가 되는 i값을 담고 있는 스택이라고하자.

A와 B를 순회하며 indexA와 indexB를 만들어주자.

def makeindex(arr):
    result = [[] for _ in range(101)]
    for i,t in enumerate(arr):
    	result[t].append(i)
    // result[t]의 원소는 오름차순 정렬돼 있으므로 거꾸로 만들어준다.
    for t in range(1,101):
    	result[t].reverse()
    return result

이제 우린 100부터 1까지 역으로 순회하면서, result[t]를 pop해주면 된다.

ans = []
curA = -1 #현재 보고있는 인덱스이다.
curB = -1
for i in range(101,0,-1):
    while indexA[i] and indexA[i][-1] < curA:
        indexA[i].pop() #이미 추가한 것보다 앞에있는 것들은 추가하면 안된다.
    # B에 대해서도 똑같은 과정을 수행한다.
    for _ in range(min(len(indexA[i]),len(indexB[i])):
    	curA = indexA[i].pop() # 인덱스를 갱신해준다. 
        curB = indexB[i].pop()
        ans.append(i) # 정답을 갱신한다.

 

E

https://www.acmicpc.net/problem/30806

30806번: 교차 집합 크기 합

재밌었고 드럽게 어려웠다. 괜히 플레가 된게 아니다.(모듈러 역원의 자체 난이도가 있기도 하다.)

문제를 쉽게 풀어쓰면 이거다.

집합 N개를 준다. 각 집합은 중복을 허용하지 않는다. "가능한 모든" 교집합에 대해 교집합 크기의 합을 구하여라.

그대로 푼다면 O(상수? * 2^1000000)이라는 엄청난 복잡도가 나올 것이다.(가능한 모든 교집합은 가능한 모든 조합을 계산하란 것과 같다. 각 교집합을 직접 계산해내야한다.)

관점의 변화로 다음을 유추해 낼 수 있어야한다.

만약 주어진 집합에서 어떤 수 X가 t번 나왔다고 하자.

주어진 집합중에서 k개를 골라 만들 수 있는 교집합들에 대해서, X는 tCk (t<=k)번 나온다.

교집합결과에 X가 나오려면, X를 포함한 집합들로만 교집합을 구성해야한다. 그 집합들은 t개 있다.

다른말로 주어진 집합을 k개고른다 할때, 그중 X를 포함한 집합들로만 k개를 고르는 경우이다. 그래서 tCk이다.

그러므로 나오는 모든 수 종류 Xi에 대해 Xi가 주어진 집합에서 ti번 나온다고하자. Ak는 모든 가능한 i에 대해 tiCki 의 합이다.

 

이제 이걸 최적화하면된다.... 모듈러 역원으로 조합을 구한다고해도 구해야할 조합수가 너무나도 많다.

조합의 식을 보자.

tCk = t!/((t-k!)*k!)

t는 집합 N에서 나오는 수의 개수이다. 따라서 100만을 넘지 않는다.

k는 t보다 작아야한다. 따라서 100만을 넘지 않는다.

t-k도 100만을 넘지 않는다.

모든 조합을 전처리한 팩토리얼 값을 이용해 구할 수 있다. 

1!~100만!을 구해주자.

MAX = 1000000
facto = [0] * (MAX +1)
facto[1] = 1
for i in range(2,MAX+1):
	facto[i] = facto[i-1] * i % R

 

나눗셈은 모듈러 연산이 제대로 먹히지 않으므로 모듈러 역원을 구해야한다.

A^(-1) % R == A^(R-2) % R (R is prime)이다.

R이 998244353이다. 따라서 거듭제곱을 분할정복 거듭제곱으로 처리한다.

ivsfacto = [0] * (MAX + 1)
for i in range(1,MAX+1):
    ivsfacto[i] = getinverse(facto[i],998244353)

 

 필자의 경우엔 각 수 카운트를 하고 N*(N-1)*(N-2)...*(N-k)를 전처리 해준다음에 ivsfacto[k]로 값을 구해줬다.

그러면 O(상수 * 백만)에 값을 구할 수 있다. (상수는 좌표압축으로 생긴 상수이다.)

 

E

https://www.acmicpc.net/problem/30807

30807번: TSM

 

이 문제 보고 껐다. 못푼다.