2022 ICPC Seoul Regional 예선 후기

9등!! 느낌있다

 

그냥 재미로 어느정도 할수 있을까? + 학교 더미팀 만들어주기 용으로 참가한 대회에서 예상외로 좋은 성적을 받았다.

 

올해 나는 전역 후 휴학생이기 때문에 본선에 갈 수 있는 사람들에게 민폐를 끼치지 않기 위해서 휴학생들로만 팀을 구성했다. 그냥 친한 사람들 중에 PS는 간간히 하지만 대회 경력은 많지는 않은.. 그런 사람들과 경험을 위해 참가했다.

나의 팀원들 : 나(ystaeyoon113), 김준형(jun990111), 박준열(bokdolcpp)

 

 

C. Container Rearrangement (00:09) 

 

처음에 그냥 음 ? sum/N이거나 sum/N +1이어야 하는데 (sum%N개만큼)

이걸 경우를 따져가면서 그리디하게 할까 생각을 하다가

sort하면 쉽게 할수 있다는 걸 떠올리고 통과했다.

 

 

 

A. Balance Scale (00:14)

 

사실 대회가 시작하고 문제를 한장씩 인쇄해 주길래 종이로 보긴 글렀구나.. 싶어서 처음엔 셋 다 컴퓨터 앞에 앉아서 A부터 보다가 쉽다고 판단해서 넘기고, 혹시 더 쉬운 문제 있나 보다가 C번 풀고 돌아온 문제다. 그냥 하라는 대로 하고 dp박으면 된다. 1000만 * 동전 몇개 안된다.

 

 

 

E. Gift Discount (00:23)

 

sort한 이후에는 i개 사는 경우를 모두 다 따져볼 수 있고, prefix sum으로 최적화 가능하다. 풀이는 금방 나왔는데 긴장해서 손이 꼬여서 좀 걸린 문제

 

여기까지는 빠르게 풀고, 각자 문제를 하나씩 잡고 쉬운거/어려운거 판별을 했는데 B번 이런 길고 어려운 문제들에 함정이 좀 있었다.

 

 

 

 

F. Islands Tour (00:48)

 

모든 vertex에서 outgoing edge가 1이하니까 functional graph이고.. 그러면 사이클이 생기는 순간 그 Connected Component의 종착지가 된다. 또 outgoing edge가 1 이하니까 한 점에서 두 갈래로 나눠지는 경우 따위는 없어서.. 그냥 dp로 모든 점으로부터 닿을수 있는 점의 개수를 셀 수 있게 된다. 중간 구현하는 데 시간을 좀 썼지만 스무스하게 넘겼다고 생각한다.

 

이러고 K번이 쉽다는 jun990111의 제보가 들어와서 문제를 봤는데, 문제 생긴 건 어려워 보이는데 생각보다 쉬워 보였다.

 

 

 

K. Temporal Graph (00:58)

 

edge가 바뀌고.. 없어지고..생기고 난잡한데 결국 t초 graph에서 edge를 하나 이상 쓰지 못한다. 그래서 t초에 존재하는 edge 각각에 대해 이전 그래프에서 relaxation하면 된다. (u,v) relaxation을 하면 dis(새로운 v) = dis(이전 u) + c(u,v) // dis(새로운 u) = dis(이전 v) + c(u,v). 아예 안쓰는 경우도 있는데 dis(새로운 u) = dis(이전 u) 이렇게 처음에 초기화하면 된다. t초에서 edge를 2개이상 쓸 수 없음.

 

여기까지 풀었을 때 생각보다 등수가 높았고, G번이 game dp같다는 bokdolcpp의 정보를 듣고 G번으로 갔다. G번까지 풀면 사실 우리는 이미 대만족이라고 생각해서 셋이서 G번 얘기를 좀 하면서 같이 생각했다.

 

 

 

G. Jar Game (01:17)

그냥 조건을 보아하니 어떻게 봐도 game dp를 하라는 말이고, 게임 move 자체가 생각보다 작을 것이기 때문에 dp(a,b,c,t)로 짜면 무조건 풀린다는 확신은 있었다. 여기서 move의 상한은 안전하게 30으로 잡았다. 대략 1..t의 합을 구해서 300 이상이면 되는데 1...t 합보다는 실제로 조금 작기 때문이다. 그래서 안전하게 30정도는 잡아 주기로 했다.

 

거기서 생각을 해보다가 잠깐 멈칫한 게, 최대의 차이를 내는게 목적인지 ? 혹은 좀 덜 가져가도 이기는 게임을 하는건지?에 대한 생각이다. 두 문제의 답이 다른 경우를 생각해보다가, 이 문제는 두 경우가 동치임을 깨달았다.

이 게임은 최종적으로 가장 많이 가져가는게 이득인 게임이다. 두 플레이어의 승리 목표 또한 똑같고.. 이런 dp는 하나의 식으로 해결할 수 있다. 현재 상황 (a,b,c,t) 에서 내가 행동을 해서 y만큼 가져갔을 때, 상대방이 최대로 가져갈수 있는 양을 x라고 하면 x 또한 똑같은 dp문제로 표현할 수 있고, 내가 가져가게 되는 양은 y+ (a+b+c-y - x). 이는 상대방도 최선의 전략으로 임하기 때문이다. 

 

 

 

여기까지 풀었을 때 이미 사실 대만족이였고, 하나 더 풀수 있을까 해서 남은 문제들을 하나하나 다 까보면서 혹시 운좋게 아는 문제 있나 찾아보다가, J가 그나마 해볼만 하다는 생각에 J에 올인을 박았다.

 

J. Rectangles (02:42) (+2)

 

아무리 생각해도 최적화 할 방법을 찾지 못했고, 그나마 O(N^2) 풀이로 찾은 것이 X순으로 정렬 -> Y순으로 정렬 이후 스위핑 하듯이 .. Y값 같은점 세고...등등.. N^2 풀이밖에 떠올리지 못했고, N 제한이 상당히 커서 이 풀이는 안되겠다 싶었다. 그래서 난 이건 무조건 안된다는 생각이였는데 그래도 팀원들이 그거라도 내 보자는 말에 짜서 내봤는데 맞아서 그냥 운좋게 하나 얻어걸렸다고 생각했다. 당연히 정해는 아니겠지만.. 끝나고 나서 lky7674 선배 풀이를 들어보니 거~의 비슷한데 X값마다 원소가 sqrt(N)개 이상/이하에 따라 따로 처리함으로써 N*logN*sqrt(N) 풀이가 있다고 한다. 아마 내 풀이가 싼 연산들 위주로 구성되어 있었고, N*logN*sqrt(N)을 통과시키는 과정에서 운좋게 N*N도 통과된 것 같다.

중간에 인덱스가 너무 헷갈려서 배열 사이즈를 좀 줄이고 디버깅한 후에 그걸 그대로 내서 런타임 에러가 떴다. +2를 먹었다. 멍청

 

 

 

 

사실 여기까지 풀었을 때 이미 풀건 다 풀었다고 생각했고.. 시간도 얼마 없었기에 그냥 재미삼아 D를 봤다. 처음에 D를 봤을때 이건 답이 단조적인 형태는 아니기 때문에 브루트포스적인 방법으로 접근해야 되지 않나.. 이런식으로 생각했고 생각보다 답이 작을 수도 있다고 생각했다. 어차피 시간도 없었기에 답=d로 정해놓고 d=0부터 키워나가면서 각 점에서 d만큼 갔을 때 red에 있는지/아닌지로 판별하는 방법으로 했고 당연하게 TLE!

 

 

 

 

프리징 이후 9등이였고 우리가 모두 재학생이였다면 아마 본선진출을 했겠지만 휴학생팀 .. 이기 때문에 아마 올해는 여기까지인듯 하다. 올해 ICPC는 유난히 쉬웠다고 한다. 어쩐지 내가 그렇게 잘 풀리가 없는데 문제가 훅훅 풀린다 싶었다. 6솔 스피드포스라는 의견이 많았던 것 같고 본선에는 당연하게 더 어려울 예정이겠지? 내년에는 재학생 신분으로 참여할 수 있으니까 내년 월파 출전을 목표로 달릴 예정이다.