ICPC 2022 Seoul Regional 후기

참고: ICPC 2022 예선 후기

2022 ICPC Asia-Seoul Regional Contest

2022 ICPC 서울 리저널 결과 - 최종 10등!!

I hate PS 팀 결과 (8 Solve, 1037 min.)

(사진추가예정)

---

목차
1. 후기
2. 소감
3. 시간 기록
4. 풀이

---

1. 후기

원래 소감부터 쓰는게 맞는것 같지만 두괄식으로 씀

 

우리 팀의 어떤 사람이 코로나 이슈로 인하여 불참하게 되었다.

따라서 나와 노세윤 두 명이서 대회를 치르게 되었다.

나는 대회를 응시할 수 있다는 것만 해도 매우 다행이라고 생각하고 있었다. (그리고 버스기사는 멀쩡하기 때문에..)

 

그리고 어제 좀 일찍이 누워서 잠을 잘 잔 덕에 기분이 좋았다. 세윤도 컨디션이 좋아보였다. 과연 두 명이서 어디까지 할 수 있을지 기대가 되었다.

 

초반 푸시는 정말 좋았다. 두 명이라는게 믿기지 않을 정도로.

5등까지도 올라갔던 것 같다.

그러다가 프리즈 직전에는 8등으로 마무리했다.

이것도 C를 풀어서 망정인 거지만, 뭐 여튼.

 

L은 많이들 풀었으니 L을 풀고 A까지 야무지게 딱 풀고 가는게 우리의 목표였다.

그러나 L에서 12트를 박고.. 맞왜틀을 1시간동안 울부짖다가 끝났다.

개같이 망했다.

우리는 dfs도 못돌리는가?

 

중요한건 세윤도 틀린 점을 찾지 못했다.

심지어 틀린거 내가 찾았다.

물론 내가 싼 똥을 내가 치운거긴 하다. (220분의 페널티와 1시간의 시간 loss와 함께)

하... ㅅㅍ

 

8솔까진 꽤나 할 것 같아서 수상권인 14등도 애매하다고 생각했다.

그러나 결과는 놀랍게도 10등 이라는 높은 성적이었다.

9등까지가 동상인데, 이건 좀 안타깝다.

if도르지만 만약 L을 잘 풀었다면 무조건 9등이었다.

역시 if도르지만 3명이서 쳤다면 A까지 풀었을거같긴하다. 그렇지만 별 상관없다. 그거 풀어도 월파 못나갔다. NLP 가 원체 쎄서...

 

아무튼 50만원 자~알 먹고 갑니다.

 

2. 소감

와! 온사이트!

2019년 이후 첫 온사이트 리저널이다.

예비소집 때도 교수님들이 우리도 처음이라 미숙할거다. 같이 잘해보자. 라고 하시던데...

솔직히 대회 장소부터 에러가 아닌가 싶다. 일산은 진짜 멀어도 너무 멀었다. 오늘은 아침에 가뜩이나 구파발행 와서 죽는줄

하지만 우리는 온사이트로 이렇게 성대하게 열어주는거 자체에 감사하여야 한다.

 

스텝들은 적어도 온사이트 리저널을 많이 겪어보신 분들이어서 순조롭게 진행된 편인 것 같다.

스텝들도 그때나 지금이나 다 똑같은 사람들인것 같다. ㅋㅋㅋㅋ

사진 찍는 분이 몇 분 없던 것 같아서 아쉬웠다. 19년도때는 그래도 팀장 2~3장은 찍어줬었는데 올해는 어떨지 모르겠다.

풍선 달아주랴 프린트물 가져다주랴 열심히 움직이셨던 것 같다.

근데 프로즈 뒤에 맞춘 문제도 풍선을 달아주셔서 뭐지 싶었다.

 

대회장 환경은 정말 좋은 편이었던 것 같다.

모니터도 상태 좋았던 것 같고, 무엇보다 에디터 종류가 매우 많아서 정말 좋았다. CLion, VSCode, 기타등등... 심지어 보통 이런건 초기세팅을 귀찮게 일일히 해줘야 하는데 이게 기본적인건 다 되어있었기 때문에 편했다.

이렇게 우분투로 대회 쳐보는건 진짜 진짜 오랜만이었다. 감회가 새롭다..

다만 키보드가 정말 싸구려였는데, 우리는 키보드를 미리 챙겨와서 망정이지 별생각없이 온 팀들은.. 생각만 해도 끔찍하다.

 

그럼에도 불구하고 아쉬웠던 점들을 적어보자면..

- (중요) 중식이 샌드위치였는데, 비건 샌드위치인지 햄도 하나도 없고 야채밖에 없었다. 뜯자마자 뚜껑닫고 버렸다.

- 간식(물, 음료수, 과자, 쿠키 등) 을 원래는 마음대로 가져다가 먹을 수 있었는데 지급제로 바뀌었다

- 앞에 크게 스코어보드 띄워주는게 없었다

- 화장실을 한명 한명씩 가야했다 (한명 똥싸면 큰일남.. 그래서 나도 똥참아드림ㅎ)

- 세팅시간을 안줬다.

- 대회 끝나고 언프리즈 전까지 시간이 너무 붕 뜬다. (특강?도 다소 지루하고 루즈했다.)

 

3. 시간 기록

amel → 앞쪽 (A~F)

knon0501 → 뒷쪽 (G~L)

 

0:08 J (+) - amel

- 앞쪽 문제들이 좀 어려워 보여서, 뒷쪽 문제들을 훑어봤다.

- J가 딱봐도 쉬워 보여서 바로 짰다.

 

0:17 I (+) - knon0501

- 내가 문제 설명을 해줬더니, 문자열 뒤집어서 LCS 하면 된다고 하더라.

- 그래서 너가 짜라고 했다.

 

0:40 K (+) - knon0501

- 내가 F를 무지성 코딩 박다가, 조금 생각을 하고 짜야 함을 깨닫고 세윤에게 키보드를 넘겼다.

- 알아서 잘 내더니 맞았다. 덕분에 문제도 모르고 풀이도 모른다.

 

0:47 F (+) - amel

- 세윤이 K 짜는동안 손코딩 하고 있다가 후딱 짜서 맞았다.

- 구간을 적당히 잘 합쳤다가 틈을 적당히 잘 prefix sum 해주면 된다. 맨 처음에 1번에서 시작하는줄 몰라서 당황했다.

 

1:23 E (+2) - knon0501

- 다익? 비스무리한거 돌리는데 초기화 같은걸 잘 안해줘서 틀린 것 같다.

- ans가 INF일 때 -1 안찍어서 한 번 더 틀렸다... (이제와서 보니 이게  선녀네 ㅋㅋㅋ)

- 아직 페널티도 좋고 순위도 좋아서 만족스러웠다.

 

1:44 D (+) - knon0501, amel

- 내가 무지성 그리디 박다가 예제 넣어보니까 이게 그리디로 하기엔 쉽지 않음을 깨달았다.

- 그리디가 아니면 무조건 dp이기 때문에 세윤에게 dp를 잘 설명해줬다.

- 1분만에 풀이를 알려주길래 그대로 짜서 맞았다. 대충 min세그 잡고 lifting 하면 된다.

 

3:17 C (+) - knon0501

- 이제 C 아니면 L을 풀어야 하는데, L은 아무리 생각해도 아이디어가 안떠올라 같이 C를 봤다.

- 세윤이 먼저 아이디어를 제시해서 코딩하였으나, 예제가 (다행히도!) 안나왔고 원인을 찾았다.

- 풀이가 개같이 멸망해서, 분위기가 침체되어 있었다.

- $_{n}C_{4}$가 대충 3억3천만 이고 시간제한이 2초라서 그냥 박아버리고 싶었지만, 세윤이 말려서 정풀이를 생각하기로 했다.

- 직선 기준으로 그라함 스캔마냥 기울기 정렬하면 풀 수 있을거같긴 했는데, 귀찮기도 하고 시간 안에 안들어올 것 같아서 다른 풀이 계속 생각하고 있었다.

- 그런데 세윤이 이 얘기를 하길래 들어보니까 그다지 귀찮지도 않고 시간 안에도 들어오는 ($\mathcal{O}(N^3 \log N)$) 풀이를 완성할 수 있었다. 대박!

- 기하 이기 때문에 둘이 같이 코딩해서, 같이 디버깅하고, 같이 냈다. 다행히 원큐에 맞았다. 근데 디버깅을 좀 오래하긴 했다. ㅋㅋ (이것도 내실수 ㅎ)

 

3:41 ~ 3:50 L (-3)

- 그런데 C를 풀고 L을 보자마자 세윤이 기가막힌 아이디어를 내는게 아닌가!!

- 진짜 나 혼자 풀었으면 백날 잡아도 못풀었을 것 같았다.

- 그래서 내가 아주 빠르게 코딩해서 냈는데, 틀렸단다.

- 심지어 TLE로 틀렸다. 이건 뭐지?

 

4:41 L (+11) - knon0501, amel

- 나는 직감적으로 par 따라 올라가면서 출력하는 부분이 무조건 문제라고 생각했다.

- 그런데 그런 일은 발생할 수가 없는 일이었던 것이다. 그래서 멘탈이 나가버리고 말았다.

- 코드도 개짧아서 뭐 말이 안나온다. 세윤도 내 코드에서 이상한 점을 발견하지 못했다.

- 랜덤 제너레이터도 짜보고 (별로 쓰진 않았지만) 세윤이 따로 코딩도 해보았지만 별 소득은 없었다.

- 그래서 그냥 assert 쳐서 내면서 어디가 문제인지 찾았다.

- back edge가 위로 올라갈 수도 있지만 아래로 내려갈 수도 있다는 사실을 깨달아버렸다.

- 그렇게 L을 겨우 맞추고 자괴감 + 멘붕 + 억울함 + 실력에 대한 회의가 동시에 밀려왔다.

미안해요 버스기사!

4. 풀이

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

J. Parentheses Tree

예상 난이도: 실버 4

알고리즘: Stack?

- ( 가 나오면 +1, ) 가 나오면 -1

- 그런데 ()가 나오면 현재 값을 ans에 더하기

I. Palindrome Type

예상 난이도: 골드 5~4

알고리즘: LCS

- 원래 문자열과 뒤집은 문자열을 가지고 LCS

K. Shuffle Game

예상 난이도: 골드 ?

알고리즘: ??

- knon0501이 풀었어요 ㅠㅠ

F. Frog Jump

예상 난이도: 골드 4

알고리즘: Sorting, Sweeping, Prefix sum

- 대회 때는 몰랐는데, 입력이 애초에 (시작점 기준) 정렬되어서 들어온다.

- 처음부터 끝까지 순회하면서 구간이 겹칠 때까지 계속 합쳐준다.

-- i번 구간이 몇 번 구간에 귀속되었는지 표시해놓는다.

 

- 그러면 합쳐진 구간들끼리는 반드시 떨어져 있게 된다.

- 구간들 사이의 틈새 크기를 prefix sum 해준다.

- 개구리 여행의 이전 구간 ~ 현재 구간을 prefix sum에서의 구간 쿼리로 생각하여 잘 풀어준다.

E. Forbidden Turns

예상 난이도: 골드 ?

알고리즘: Dijkstra + DP ?

- 이것도 knon0501이 풀었어요 ㅠㅠ

D. Folding Stick

예상 난이도: 플래 3

알고리즘: Dp, Segment tree

- 그리디는 안된다.

- (거꾸로 하면) 되긴 하는데, 마지막 조각은 안접어도 되기 때문에 이게 TLE 뜬다.

- 그래서 dp를 돌려야 한다.

 

- dp[i] : ~i번째 segment만 있을 때 정답

- a[i] : ~i번째 조각 까지의 길이

- dp[i]를 구할 때, 어떤 j < i 에 대하여 가장 마지막 조각이 i~j 라면 길이가 a[i] - a[j] 이므로 a[j] - a[i] >= dp[j]

- 따라서 dp[i] >= j + dp[j]

- 조각이 짧을 수록 좋기 때문에 j는 클수록 좋다.

 

- x + dp[x] 값으로 min seg 를 구성하고, dp[i]를 찾을 때는 a[i] 보다 작으면서 가장 오른쪽에 있는 index를 찾자.

-- 이를 lifting? 이라고 하던가 (루트부터 시작해서 내려가는 느낌)

- 그리고 모든 i에 대하여 정답의 후보 max(dp[i], length - a[i]) 를 갱신해주자.

C. Empty Quadrilaterals

예상 난이도: 플래 1 (~ 다야 5)

알고리즘: Dp, Sorting, Two-pointer, (무슨태그인지잘모르겠음)

- N^3 까지는 마음껏 돌려도 된다.

- A[i][j][k] : 삼각형 ijk 내부에 있는 점의 개수 를 모두 구해주자.

- 이를 위해 B[i][j]: 선분 ij 아래에 있는 점의 개수 를 모두 구해주자. (3중 for로 가능)

- 그러면 A[i][j][k]는 아래 두 가지 경우로 나눠서 구해주면 된다.

 

- 점 i, j를 잡고 평면을 반띵할 수 있다. (선분 ij 는 사각형의 대각선이 될 예정)

- 각 부분에서 A[i][j][k] == 0 인 k를 모으자.

- 각 부분에서 점을 한 개씩 골라서 사각형을 만들면 조건을 만족한다.

- 그런데 이러면 볼록사각형은 2번, 오목사각형은 1번 세진다.

- 오목사각형의 개수도 따로 세주자.

 

- 마찬가지로 점 i, j를 잡고

- 먼저 점 j를 기준으로 하여 반평면 각각에서 점들을 기울기 순서대로 정렬해주자. (그림참고)

- 기준점에 대해서 오목이 되려면 (윗쪽점, 기준점, 아랫쪽점) 이 CCW여야 한다. (그림의 1번 점)

- 이러한 점의 개수를 투포인터 느낌으로 잘 세주자.

- i 점을 기준으로 잡고 동일하게 정렬 → 투포인터 돌려주자. (이 때는 CW 여야 하므로 반대로 잘 처리)

- 위 두 개수를 합쳐서 반으로 나누면 된다.

- 시간복잡도 $\mathcal{O}(N^2 \times N\log N)=\mathcal{O}(N^3 \log N)$

L. Two Choreographies

예상 난이도: 플래 2

알고리즘: ad-hoc, DFS

- 아이디어가 무친 문제인것 같다.

- 일단 문제 자체는 무향 그래프가 주어졌을 때, 완전히 일치하지는 않으면서 크기가 같은 cycle 2개를 찾는 문제이다.

- 트리로 N-1개의 간선을 쓰면, N-2개의 간선이 back-edge로 남는다.

- back-edge가 만드는 cycle의 크기를 생각해보자. 이는 최소 3 ~ 최대 N 이다.

- 그럼 종류가 딱 N-2개 이다.

- 두 가지 경우가 있다.

1) 각 크기의 back-edge가 하나씩 모두 존재할 때

2) 비둘기집의 원리에 의해 어떤 크기의 back-edge가 2개인 경우

- 2) 는 그냥 그 back-edge 2개에 대해 print해주면 끝난다.

- 1) 의 경우 크기가 N인 back-edge가 존재하려면 그래프가 일자로 쫙 펴져야 한다. (branch가 있으면 안됨)

- 그러면 크기가 N인 back-edge, 크기가 N-1인 back-edge를 사용하면 크기가 3인 cycle을 만들 수 있다.

이해를 돕기 위한 그림

- 이것과 원래 크기가 3인 back-edge를 출력해주면 된다.

즉 무조건 정답을 찾을 수 있다.