ICPC 2022 예선 후기

참고: ICPC 2022 Seoul Regional 후기

2022 ICPC Seoul Preliminary (인터넷 예선)

ICPC 2022 Seoul 인예 결과

 

고려대학교 스코어보드

I hate PS 팀 결과

 

7솔!!

항상 대회때 끝나기 N분 전에 이렇게 극적으로 맞추는 것 같다.

이번에도 막판에 J를 비트셋 상수컷팅으로 뚫어서 기분이 좋았다

그나저나 올해 난이도분포 왜이럼?

오늘 특히나 초반 푸쉬가 병신이었던 우리 팀에게는 정말 최악의 상황이었다.

하지만 다행히 6솔 → 7솔 벽이 컸고 우리는 그걸 넘었기 때문에 리저널은 프리패스다.

어차피 리저널 결과가 중요한거 아니겠는가? ㅋㅋ

리저널 때는 진짜 잘 해야지...

후기

이번에는 컴퓨터학과 쪽으로 신청을 해서 그쪽에서 봤다. (과학도서관 611호)

특히 2019년 이후 처음으로 모여서 보는 ICPC 라서 더 재밌었다.

 

근데 프린터가 분명히 네트워크 로 된다고 했었는데, USB선 달랑달랑...

노트북을 들고 옮겨서 뽑아야 하거니와 테스트 인쇄 조차도 되지 않았다.

그래서 인쇄는 포기했다.

 

이번에는 나와 남일이 똥을 잔뜩 쌌다.

일단 맨 처음 A에서 누군가가 문제를 잘못 (대충) 읽어서 몇 번 틀리고,,

C, E도 한 번에 못 맞추고 절었다. (내가 짬..)

내가 그래도 초반 스퍼트에는 어느 정도 자신 있었는데, 굉장히 부진한 결과였다. (페널티 +40..ㅋㅋ)

 

그 뒤로도 많이 절어서 6솔까지가 느리기도 매우 느렸고, 페널티도 왕창 안아버렸다. (1:28 6솔)

하지만 스코어보드 상 한 문제만 더 풀면 백프로 리저널이다 라는 확신이 들었다.

그래서 1시간 반 동안 편하게 J만 때려맞추고 끝났다.

 

솔직히 결과는 매우 마음에 안들지만, 인예니까.. 인예니까...

괜찮다고 자기 위로 중이다.

리저널 때는 진짜 이러면 안된다.

시간 기록

한글 문제부터 읽었다.

 

0:17 (A +2) - knon0501

- 가벼운 쪽에만 올릴 수 있다는 조건을 빼먹었단다. 아이고..

 

0:20 (E +1) - amel

- 문제는 개쉬운데 풀이가 바로 떠오르지 않아 남일에게 "해줘" 했다.

- 코드는 내가 바로 짰는데, ``+1`` 을 괜히 붙여서 한 번 틀렸다. 예제는 대체 왜 잘나오는거야?

 

0:26 (C +1) - amel

- 이어서 C도 내가 짰다. 여기서는 나머지가 더 "높아야" 하는데 더 "낮게" 배정해버려서 틀렸다 ㅋㅋㅋㅋ 여기도 예제는 기가막히게 잘나온다. 진짜 화가 난다

 

0:55 (F -3)

- F를 dfs로 cycle 찾고 깊은거 찾고 ... 하는 방식으로 짜서 냈다.

- 근데 런타임 에러가 났다. 화가 나서 조금 바꿔서 냈는데, TLE 2연빔 맞았다.

 

1:01 (K -2)

- 중간중간에 키보드를 좀 넘겼었기 때문에 빠르게 낼 수 있었다. (코딩: namil208)

- 문제에 조건이 없다길래 문제를 읽어봤는데 잘만 계셨다. 이거 한국어 문제다...

 

1:05 (G +) - knon0501

- 문제 읽고 바로 풀이가 나왔었던듯한 세윤이 키보드 잡자마자 바로 짜서 내더니 맞았다.

- 이럴 줄 알았으면 F 짜지 말고 넘겨줄걸 싶었다. G가 이렇게 큰 확신이 있는 줄 몰랐다. 앞으로는 재깍재깍 넘겨야지..

 

1:22 (F -5)

- 그 뒤로 엄준식의 향연을 벌이고 있었다.

- 세윤이 갑자기 "그거 indegree가 0인 것부터 빼면 돼"라고 외쳤다. (씨발 진작에 얘기해주지...ㅠㅠㅠ)

- 그래서 그렇게 짰는데 틀렸댄다.

 

1:34 (K +2) - namil208

- 디버깅 끝에 엄준식을 찾아서 순조롭게 제출하였다.

 

1:38 (F +5) - knon0501, amel

- 아까 틀릴때 좀 오래 걸려서, 진짜 호~~~옥시나 ``0 0``에서 -1이 나오는거 호~~~옥시나 예외처리해서 내봤는데 맞았다...

- 개빡친다. 상식적으로 정점은 1개 이상 줘야지..ㅋㅋ

 

2:21 (J -1)

- 내가 문제 읽자마자 bitset으로 뚫자고 말했지만, "그래서 어떻게 할건데"가 없었다.

- 이런 류는 무조건 sqrt decomposition마냥 작은거 큰거 나누는 문제라는걸 알고는 있었다.

- 세윤이 작은 줄 큰 줄 나눠서 이렇게 저렇게 해보자고 했다.

- 그 말을 듣고 영감을 받아 후딱 짜서 내봤는데, 어김없이 TLE 빔을 맞았다.

 

2:46 (J +4) - amel

- 결국 시간복잡도 $\mathcal{O}(N^{4/3} \cdot \frac{N}{64})$ 안에 돌아가도록 짜서 AC

- 이게 좌표값이 1번만 등장하는 점은 없애버리는 최적화를 했기 때문에, N(좌표 개수)가 최대 35,000 이기는 하다.

- bitset은 신이다.

 

결국 7솔 하고 기분 좋게 시마이 했다. 만약에 이거 못풀었으면 페널티 개쎄서 ㄹㅇ 분위기 험악했을듯...ㅋㅋ

풀이

우리 팀이 대회 도중 푼 것만, 푼 순서대로 정리해보았다

A. Balanced Scale

예상 난이도: 실버 4~3

알고리즘: Knapsack DP 혹은 Greedy

- 일단 자갈 올리는건 써져 있는대로 하기

- 그 후 무게추 매다는 것은, 일단 이 문제 조건 상에서는 greedy하게 무거운거부터 채워도 됨.

- 불안하면, (무게추 종류) × (총 무게) = 7천만 DP 돌리면 된다. 우리도 DP 돌린거로 앎

E. Gift Discount

예상 난이도: 실버 2

알고리즘: 투포인터?

- 선물을 X개 살거면, 가장 가벼운 X개를 고른 뒤, 가장 무거운 k개를 할인하는게 낫다.

- 이걸 X = 1 ~ n 까지 결과값을 계산해주면 된다.

- X가 1 증가할 때마다 일반 선물도 한 개 늘어나고, 할인받는 금액이 하나씩 빠지고 채워지니까 그 처리를 투포인터 느낌으로 잘 해주면 된다.

C. Container Rearrangement

예상 난이도: 실버 4

알고리즘: 수학

- 컨테이너의 높이는 정해져 있다. sum / n 혹은 여기에 +1

- 각 높이가 몇 개 있어야 하는지도 정해져 있다. +1된 높이는 sum % n 개만큼 있어야 한다.

- 따라서 높이를 정렬한 후, 앞 n - sum % n 개는 높이를 sum / n에 맞추고, 뒤 sum % n 개는 높이를 sum / n + 1에 맞추면 된다.

- 높이 차이의 합을 절반으로 나누면 정답이다. (옮기기 때문에 +1과 -1이 같이 되므로)

G. Jar Game

예상 난이도: 골드 4

알고리즘: DP

- 100*100*100. 제발 DP 돌려주세요 라고 애원하고 있다.

- 근데 이건 라운드마다 가져가는게 달라서 바텀업으로 짜기 매우 힘들다.

- 따라서 재귀함수로 탑다운 짜주면 된다.

- 내가 x라운드이고 i, j, k개 있는 상태에서 먹을 수 있는 최대 돌의 개수를 dp[x][i][j][k]에 저장하자.

- dp[1][a][b][c]를 구해서 a+b+c의 절반 이상인지 확인해주면 된다.

- 라운드가 해봐야 25라운드 정도 라서 2천5백만번 정도 안에 돌아간다.

K. Temporal Graph

예상 난이도: 골드 5~4

알고리즘: 벨만 포드

- 이것도 나 벨만 포드요 소리치고 있다.

- 그냥 써있는 대로 해주면 된다...

- 각 시간마다 최대 하나의 간선을 택할 수 있으므로, 그냥 간선 하나 입력받을 때마다 이전 거리표 -> 현재 거리표 찾아서 update 해주면 되는 것이다.

- 물론 메모리가 터질 염려가 있으니 배열 copy해서 왔다리 갔다리 해주는 정도만 신경쓰면 된다.

F. Islands Tour

예상 난이도: 골드 1 ~ 플래 5

알고리즘: 위상정렬

- cycle은 서로 전부 다 갈 수 있다. (좋은 녀석)

- 따라서 각 cycle 마다, cycle의 각 점에서 "역방향"으로 갔을 때 가장 깊은 친구가 중요하다.

- 이런식으로 DFS 돌리는 코드 냈다가 멸망했다.

- 비슷하게 SCC 짠 팀도 멸망했다고 한다. (TLE 빔)

- dp[i]에 i번 점의 "깊이"를 저장하자. (어떤 점에서 i번 점까지 왔을 때 방문한 점의 최대 개수)

- indegree = 0 인 점부터 보면서, 간선 따라 가면서 dp[next]에 dp[i]+1과 max를 취해주자.

- 사용한 간선은 없애버리자. (edge[now] = -1 과 같이)

- 위상정렬이 끝나면, cycle만 예쁘게 남아있을 것이다.

- 남아있는 간선들로 간단한 dfs를 돌리면 cycle의 크기를 손쉽게 파악할 수 있다.

- 저장된 dp값에 cycle 크기를 더하면 해당 점에서의 답을 구할 수 있다. 이들 중 max를 구하면 된다.

J. Rectangles

예상 난이도: 플래 1 ~ 다이아 5

알고리즘: sqrt decompostion

어떻게 풀든 가로줄 기준으로, 점이 많이 들어있는 big 그룹과 적게 들어있는 small 그룹으로 나누어 풀어야만 한다.

그림을 첨부하면 좋겠으나 귀찮아서 생략

1. 우리 팀의 풀이 (bitset 비비기)

- $N^{1/3}$ 개를 기준으로 점이 더 많이 포함된 가로줄은 big, 적게 포함된 가로줄은 small

- 직사각형을 만들려면 가로줄 2개를 정해야 합니다.

- 길이 N짜리 bitset을 N개 만들어 줍시다. (메모리 $N{2}/64$ → N=70,000 이므로 약 77MB)

- x, y좌표 따로따로 좌표압축도 해줍시다.

- big - all :

-- i번째 가로줄(y=i)을 i번째 bitset에 대응시켜, 점의 x좌표들의 bit를 켜줍니다.

-- 그리고 모든 big 줄의 bitset에 대하여 다른 모든 가로줄과 대보면서 개수를 세줍니다. (가로줄 2개 정한 상태에서 세로줄 2개 정하는 가짓수 더하기)

-- → 이 때 두 가로줄에 해당하는 bitset을 AND 한 다음, 켜져 있는 bit 중 2개를 고르는 가짓수니까 nC2 더해주면 됨

- small - all :

-- 이번엔 i번째 세로줄(x=i)를 i번째 bitset에 대응시켜, 점의 y좌표들의 bit를 켜줍니다.

-- 그리고 각 small 줄에서 점을 2개씩 잡아서(nC2), 두 점의 세로줄(y좌표)에 몇 개나 점이 겹치는지 세줍니다. (가로줄 1개, 세로줄 2개 정한 상태에서 가로줄 1개 정하는 가짓수 더하기)

-- → 이 때 두 세로줄에 해당하는 bitset을 AND 한 다음, 켜져 있는 bit 중 1개 고르는 가짓수

- small - big :

-- 이 경우가 중복되어 세집니다.

-- 이건 간단한데, big - all 셀 때 bitset 구성을 모든 점에 대해서 하지 말고, small 가로줄만 돌면서 켭니다.

-- 그 다음에 big 가로줄을 돌면서 big - all 과 같은 방식으로 세면 됩니다.

- 나는 어떤 점의 좌표가 단 한번 밖에 등장하지 않았다면 삭제시켜버렸기 때문에 사실상 N=35,000이었다.

- 시간복잡도는 $\mathcal{O}(N^{4/3} \cdot \frac{N}{64})$. N=35,000 기준 6~7억밖에 안되고 시간제한도 2초라 돌아가고 남는다.

2. 정해 (sqrt)

- $\sqrt{N}$ 개를 기준으로 점이 더 많이 포함된 가로줄은 big, 적게 포함된 가로줄은 small

- big - all :

-- big 가로줄의 개수는 해봐야 $\sqrt{N}$개이다. 따라서 하나의 가로줄에 대해서, 다른 모든 가로줄을 하나씩 돌면서 점의 x좌표를 배열에 count해주면 됩니다. 위와 비슷하게 두 가로줄에 동시에 존재하는 x좌표 개수를 구하면 된다.

-- 모든 가로줄을 다 돌아봤자 점은 N개 뿐이기 때문에 개수 세는데에는 아무 문제가 없다!

-- 심지어 big - small 인 경우를 손쉽게 예외처리 할 수 있다.

- small - all :

-- small 점들이 속한 모든 세로줄(x좌표)들에 대해서 for문을 돕시다. (최대 N개)

-- 그 세로줄에 있는(그 x좌표를 가진) 점들에 대해 점이 속한 가로줄에 있는 모든 x좌표들을 배열에 count 해줍니다. (각각 $\sqrt{N}$개)

-- 각 x좌표에 count된 값에 대해 nC2를 더해주면 됩니다. (뭐 아니면 그때그때 답에 배열값을 더해줘도 되고)

- 시간복잡도는 당연하게도 $\mathcal{O}(N\sqrt{N})$. 널널~ 하다.