2023 ICPC 예선에 ktw020406, munhwas1140과 Mid Yummi팀으로 참가해 6솔 16등으로 마무리했고 저는 DGJ를 풀었습니다
16등이라고 보고 별 느낌이 없었는데 인접한 팀들을 보니 가슴이 웅장해지네요
+ 예선을 잘치니까 욕심이 생겨서 본선 20등을 목표로 PS를 다시 열심히 하기로 했어요
스코어보드
작년 icpc 참가 경험이 있는 두 선배와 같이하게되었다
연습은 예선을 앞두고 딱 한번 했는데 뭔 인터렉티브 2개, 실수쓰는거 3개, 3차원 기하 1개 이런셋이 걸려서 처참한 결과를 확인하고 유의미한 전략 설정이나 피드백을 전혀 하지 못한채로 대회를 치게돼버렸다
예선에서 학교 컴퓨터에 C++ 세팅을 직접 해야됐는데 환경변수고 뭐고 아오
편한 세팅 맞춰둘 생각하니까 머리가 깨질것 같았다
그래서 그냥 embacadero dev c++ 깔고 -std=c++17만 걸어뒀다
예선이 시작됐는데 지문 출력이 한참 걸려서 다같이 쪼그만 모니터로 한 문제를 쳐다봐야했다 (프린터 한대로 10팀 분량을 출력했나봄)
CD는 브실이라 모든 팀이 순식간에 푼 것 같다
팀원이 K 풀이를 짜냈는데 N=3000에서 \(O(N^2logn)\)이 터져버렸다
조금만 줄이면 될 것 같아서 셋 모두 코드를 보기 시작했다
보니까 정수로 바꾸고 map을 쓰지말자 그냥 벡터에 넣고 정렬 ㄱㄱ했고
66분에 AC를 받았다
일단 나는 영어 실력에 하자가 있기 때문에 나머지 한글 문제를 읽기 시작했는데 먼저 G가 만만해보였다
서로소 쌍 비율은 \(\frac{6}{\pi^2}\)에 수렴하니까 대충 \(O(0.6NC2logN) = O(0.3N^2logN)\)이면
상수작은 나이브 짜볼만하네!!가자!!
N = 5000이라 분명히 이렇게 풀라고 낸게 아닐텐데 "안되면 fastio박아보고 런하지"라는 마음으로 구현을 하고 TLE를 받았다
충격적이게도 fastio를 박으려고 하는데 인터넷에서 주워온 팀노트에는 fastio도 없을 뿐더러 입력이 정수 한개였다
입력 한갠데 뭔 fastio야 이놈아....
잠깐 생각을 했는데 결론은 nth element를 박아보고 안되면 아름다운 수학 풀이를 찾아보자였다
nth element 쓰고 커서 올리니까 파라미터 이름이 의미를 알아볼 수 없게 뜨길래(아오 데브시치) 레퍼런스에서
열심히 예제코드를 읽고 박아보니까 결국 돌더라 (81분)
옆자리 kookbab팀은 끝나고 들어보니 대칭성으로 절반만 찾고 자명한거 커팅도 좀 했던 것 같은데 gcd 최악을 \(N^2\)번 돌리도록 데이터를 만들 수도 없는 문제고 결국 제곱개에서 서로소인거 뽑는거보다 정렬 코스트의 비중이 커서 못 뚫은 것 같다
끝나고 제곱 미만의 풀이를 여러개 들어보니 멋지더라
+ gcd 메모이제이션하면 총 제곱이고, 데이터 순서를 강제하지 못하니 nth_element까지쓰면 이거도 제곱 풀이가 된다
후에 J를 읽기 시작했다. 제한과 그림을 먼저 봤는데 첫인상이 비트디피하게 생겼네? 덤벼
읽어보니 비트디피도 아니고 세제곱 커팅은 어림도 없을 것 같았다 (이때 그냥 세제곱 짰어야지 상놈아)
convex해보이는데 K개를 배치하는 최대 => 이거 에일리언 아니냐?
이분탐색 범위 설정 이슈로 패널티를 한번 받고 AC를 냈다 (120분)
K가 \(N^2/3\)보다 많이 작은게 상수가 작은 세제곱을 짜라는 의도였을까....
I는 팀원이 제곱디피를 열심히 짜서 디버깅을 마치고 155분에 AC를 받아줬다
6솔을 만들고 나서 프리즈 스코어보드를 보니 남은 것 중에는 A, E가 그나마 풀린 것들이었는데
AH는 팀원 셋 모두 번역을 실패하고 E는 다이아이길 기도하기로 했다
그렇게 예선 대회가 종료됐는데 프리즈 이전에 19등이었고 한문제 더 풀었으니 등수가 꽤 괜찮을 것 같았다
괜찮은 풀이가 있는 문제에 제한을 애매하게 잡은게 좀 있던데 이게 의도된 것인지 모르겠다
'대회' 카테고리의 다른 글
| 2023 UCPC 예선 후기 (5) | 2023.07.03 |
|---|---|
| 선린 가을맞이 알고리즘 챌린지 Solution (0) | 2021.10.15 |
