2023 전남대학교 PIMM 알고리즘 파티

xiaowuc의 벽은 높다....

https://www.acmicpc.net/contest/view/1095

이미 이 시점에서 나를 이길 수 있는 사람이 없는 것 같으니 2등은 확정이다.

 

A. 학점계산프로그램

 

평균 학점을 구하는 것이니 (학점의 합) / (학점의 개수)를 구하면 된다.

학점의 개수는 +이 아닌 char의 개수를 세면 된다.

+는 학점의 합에 0.5를 더해준다.

나머지 문자들의 경우에는 ('E' - x)를 더해주면 된다. (단, F는 학점의 합에 기여하지 않는다)

 

B. 알파빌과 베타빌

 

단순하게 명단 맨 앞의 M개 중에서 친구가 아닌 사람의 수를 세주면 된다.

 

C. 인기투표

 

두 입력들을 A[i], B[i]라고 칭하겠다.

그러면 A는 __gcd(A[1], ... A[N])으로, B는 __gcd(B[1], B[2], .. B[N])으로 미리 나눠준다.

그렇다면 우선 첫 번째 답은 단순하게 A에 남은 것들의 합이다.

이 때 두 번째 투표에서 각 항목의 값은 B[i] * times으로, 모든 i에 대해서 B[i] * times >= A[i]이다.

따라서 위를 만족하는 최소의 times = (Max( (A[i] - 1) / B[i] + 1))를 구해주자.

그러면 (B의 합) * times가 답이 된다.

 

D. 동전 탑 게임

 

dp[x][y] = (x개, y개가 남았을 때 선공이 몇 코인 더 이득을 볼 수 있는가)

마지막 플레이어가 k를 추가로 얻으므로, dp[0][0] = -k라고 여길 수 있다.

그러면 이제 dp[x][y] = Max( -dp[x - k][y] + k  OR  -dp[x][y - k] + k ) 임을 알 수 있다.

이때, -dp[x - k][y] + k = -dp[x - k][y] - (x - k) + x와 같다는 것에 착안할 수 있다.

따라서 R[1000], C[1000]을 만들어서, R[i] = Max( -dp[i][x] - x ), C[j] = Max( - dp[x][j] - x )로 정의하자.

(0, 0)부터 차례대로 (1000, 1000)으로 가면서 R, C를 업데이트 해 준다면

-> dp[x][y] = MAX( C[y] + x, R[x] + y ) 임을 확인할 수 있다.

 

E. 미술 시간

 

Lazy propagation을 사용하면 쉽게 풀 수 있다..

여러 다른 풀이가 가능할 것이다.

 

F. 나무나무나 심어야지

 

미리 모든 쿼리를 받으면 마지막에 남은 트리가 어떻게 생겼는지 알 수 있다.

따라서 이 트리를 기준으로 HLD를 만들어두자.

다시 쿼리를 순회하면서 첫 번째 쿼리 타입에 대해 Root ~ j 까지의 모든 점들에 w[j]를 더해주자

두 번째 쿼리 타입에 대해서 점 i의 값을 HLD를 통해 뱉어주면 쉽게 AC를 받을 수 있다..

이거도 HLD 까지 안가고 세그를 적당히 비벼도 풀린다.

 

G. PIMM 파티

 

다음과 같이 비트마스킹을 하자

-> 만일 어떤 비트 X < M이 켜져있다면, X번 위치에 인싸가 놓였다는 뜻

-> 만일 어떤 비트 X >= M이 켜져 있다면 X번 위치의 인싸가 현재 혼자 놓였다는 뜻

그럼 비트 DP를 dp[MASK][CNT] = {현재 상태 MASK, 놓인 총 인싸 CNT인 경우의 수)로 돌리면 된다.

그냥 일반적인 비트 DP이다.

시간 복잡도가 대략 N^2 * M * 2^(M * 3)으로 짰는데 잘 돌아간다.