[12월]

사실 시험기간이라서 ps를 조금 쉬었다. 매일매일 하던 게임도 한달간 안 했으니 ps 정도는 쉬어도 되는거로

하지만 시험기간이 끝나고 심심해서 ps를 조금 했다. 푼 문제들을 알아보자.

 

INU 코드페스티벌 검수

난이도가 쉬운 대회면 검수가 쉬울 줄 알았다. 하지만 난이도가 낮은 만큼 뽑는 검수 인원도 줄어들어서 검수날먹을 할 수 없었다. 모든 검수진이 모든 문제를 검수했다!

I번의 풀이를 새로 만들었다! 원래 문제가 조금 잘못된 면이 있어서 고쳐서 예쁜 문제로 만들었다. 다이아쯤 찍힐 줄 알았는데 내가 풀 때 문제 조건과 현재 문제 조건이 달라서 티어가 조금 내려간 것 같다. 그리고 뚫리기도 했다.

 

USACO 2022 December Gold

1달간 ps를 쉬고 재활겸 유사코 골드 한 셋 풀었다. 모든 문제가 생각보다 쉽게 풀렸다. Strongest Friendship Group 문제가 재미있다.

 

USACO 2023 January Gold

그리고 다시 심심해져서 골드 한 셋을 더 밀었다. 저 셋의 문제들은 생각보다 어려웠다. 특히 1번 문제는 그냥 슥슥하면 풀리는 줄 알았는데 생각보다 시간복잡도 보장하는 면이 쉽지 않았다. 좋은 근육 연습문제인 것 같다.

2번 문제 역시 쉬운 bit dp 문제인 줄 알았는데 생각보다 자명하지 않아서 놀랐다. 3번은 안 풀었다.

 

ICPC 2021 Asia Yokohama Regional Contest

유사코 골드 좀 밀고 다이아 밀고 싶어져서 요코하마 리저널 문제들을 좀 봤다. 2022년의 수학수학 기하기하 플로우의 정신 나갈 것 같은 구성과는 달리 나름 알찬 애드혹 / 그래프 / 수학 파티였다. 덕분에 재미있게 풀었다. 아래에 스포가 좀 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E번 문제는 거대한 그래프에서 mst를 구하는 문제였다. 덕분에 예전에 읽었지만 풀이는 모르는 문제인 2021 snupc MST 문제의 풀이를 읽고 왔다. MST 문제는 모두 크루스칼 / 프림으로 풀린다는 나의 고정관념을 깬 멋진 문제이다. 하지만 E번은 크루스칼로 풀기 위해 노력을 하면 풀린다. 

 

F번 문제는 정수론 문제이다. ahgus89가 풀었다는 것을 통해 유추할 수 있다... 하지만 나는 다 풀어놓고 FFT 부분을 생각을 못했다. 나중에 풀이 슬라이드 넘기면서 실수로 FFT라는 단어를 봤을 때 풀이를 깨달을 수 있었다. FFT 문제 좀 더 풀어야지

 

I번은 재미있는 그래프 문제이다. 나름 이번학기에 그래프이론개론을 들었기 때문에 재미있게 풀 수 있었다. 풀이를 보니까 논문이 있었다. 그렇다고 엄청 어려운 것은 아니고, 논문의 렘마를 조금 발전시킨 형태로 문제가 출제되었다. 

 

H번은 정말 새로운 문제이다. 일단 제한이 실수오차 5%인 것부터 새롭다. 나는 포함과 배제의 원리에서 적당히 작은 항들을 무시해줘도 된다는 결론에 도달할 줄 알았는데, 전혀 예상하지 못한 방식의 랜덤 알고리즘을 사용했다. 사실 랜덤 알고리즘은 잠깐 생각했지만 정답이 너무 작은 경우를 처리할 방법이 생각나지 않아서 1초만에 버린 방법이었는데, 정답이 작은 경우를 적당한 값을 곱하고 나눠서 해결하는 방법이 너무 멋졌다. 강추!

 

K번은 왜 풀리는지 모르겠는 구성적 문제이다. 작은 수부터 본다는 아이디어까지는 맞았는데 그 이후에 모든 사람에게 새로운 아이템을 배정할 수 없는 경우의 처리 방식에 대해 잘못 생각해서 못 푼 것 같다. 나는 그러한 경우가 없도록 배정하는 방법이 있을 것이라고 생각했는데, 사실 모든 사람에게 새로운 아이템을 배정할 수 없는 경우에는 적당한 조작으로 한 사람에게 아이템을 배정할 수 있게 하는 방법이 있었던 것이다. 그래프로 만들면 보인다는데 난 잘 모르겠다. 사람에게 아이템을 추가할 생각만 하고 shift할 생각을 전혀 안 한 것이 문제를 못 푼 이유가 아닐까 생각해본다. 

 

새해를 맞아 ps를 재미있게 해보자.