[9월] 첫 ps 일기

남들이 블로그 쓰는 것 보고 나도 꿀잼ps한 기억들을 저장하고 싶다는 생각이 들었다. 최근 2주~1달 동안 푼 문제에 대한 감상평을 적을것이다. 스포가 많다.

 

KSA Automata Summer Contest

대회 치면 맛있는거 준다길래 한 번 참여해보았다. 사실 아레나로도 칠 수 있지만 레이팅 걸려있는 것 넘나 무서운 것... E번까지 슥슥 밀고 슼보 봤는데 다들 G번을 풀었다. 자료구조 문제인데 상위 K개라서 dnc opt 어쩌구저쩌구 뇌절박다가 겨우 빠져나와서 셋질함... 근데 그와중에 구현 뇌절해서 대회 맛있게 말아먹은 듯ㅋㅋ 그래도 풀었으니까 후회는 없다~

 

Port Facility

요즘 조이슥 맛있게 먹고 있는데 옆에서 IBory님이 이거 잡고 있길래 같이 풀었다. 첨에 보자마자 세그에 그래프를 머시기저시기 풀이 냈는데 사풀이었음... 그냥 열심히 dfs하는 문제라서 이렇게 푸는걸텐데 왜 안 풀리지 하다가 적당히 그래프를 정렬해줘서 O(NlogN)에 풀었는데 TLE남ㅋㅋ 메모리도 O(NlogN)이어서 그런 듯. 벡터를 정적 배열로 바꾸는 커팅을 하고 겨우 맞았다!

 

Joisc Cookies

저 문제 넘 어려움... 요즘 조이슥 밀겠다고 가장 최근 셋 밀고 있는데 다이아 이하 6문제에 루비 4문제ㄷㄷ 저거 풀려고 한 이틀인가 고민한 듯. 사실 동치조건 찾고서도 증명이 안 되어서 하루쯤 더 씀 어려운 듯ㅋㅋ

근데 왜 oi에 빗셋 나옴;; 78 맞아놓고 조금 고민하다가 이게 왜 O(N^2)에 되지 하고 답지 깠는데 O(N^2logN/w) 이러길래 어이 없었다.

 

Joisc Tourism

지나가는 자구문제~ 별로 할 말 없음. 다 풀고 남들 풀이도 봤는데 DnC 쓰는 방법도 있더라 신기함. DnC는 prefix나 suffix에 대해서 뭐를 할 때 많이 쓰이는 듯.

 

내가 만든 문제!

월간 향유회라고 매달 대회내는 곳이 있는데 대회에 열정이 있는 사람들이 있다는 것에 감동먹음... 콜포태로 문제를 내봄. 저 문제는 문제를 내야겠다고 생각하고 낸 문제는 아니고 그냥 평소에 생각하던게 수학적으로 풀리길래 백준에 냄. O(n)에 풀리는데 O(n^3) 가우스 소거법 하려는 사람들 낚으려고 n범위 500으로 냄. 실행시간 보니까 좀 낚이신 듯ㅋㅋ

 

KOI 조개줍기

이 문제는 어쩌다가 풀게 되었냐면 런방에서 별의별 이야기 다 하다가 코이 이야기 하게 됨. KOI 문제 평가회 열다가 저 셋의 문제를 내가 안 풀었다는 것을 깨달음. 조개줍기 문제 재미있어보여서 풀어봤는데 넘 어려움... dp[i]=max(dp[j], dp[k])의 꼴에서 dp 전파되는 꼴을 트리로 표현해서 트리의 변화하는 정도가 bound되고 어쩌구저쩌구... 와 같은 방향으로 생각했는데 전혀 아니더라. 사실 dp 전이되는 형태가 굉장히 무작위할 것이라고 생각했는데 그 방향이 풀이었음; 다시 생각해보니까 격자에서 위 왼쪽의 dp값이 변하면 그 격자의 dp값도 변하고, 위 왼쪽 dp 값이 안 변하면 그 격자의 dp 값도 안 변하는 성질때문에 모양이 이쁘게 나온다더라. 담부터는 문제를 풀 때 'dp가 변하는 모양'에 대한 관찰도 좀 해야 할 듯.

사실 dp값이 1 변한다는 것에서 그것을 알아차려야 했을지도 모르겠지만, 1 변한다고 하니까 무슨 바운드가 있나 했다.

 

오랜만에 코포

런방 갔는데 사람들이 코포치길래 할게 없어서 같이 쳤다. E번까지 슥삭 밀리길래 신나서 F 잡았는데 2시간동안 뻘짓하다가 죽음;; 근데 개인적으로 n범위가 10000이면 n^2으로 내면 안된다고 생각함. 왜 n범위 5000으로 안 냈지. 덕분에 심리전에 말려서 O(nlog^2(max(A_i))) 이딴 풀이나 생각하다가 멸망함. 

추가적으로 왜 망했는지 생각을 해보자면 dp 전파를 생각할 때 항상 전파하는 방향과 받는 방향 두 방향 모두 생각해야 되는데 이번에는 전파하는 방향에 대해서만 생각한 듯. dp는 해도해도 어려움ㅋㅋ 그리고 상위 비트부터 했더니 가장 상위 비트가 홀수개면 답이 정해지길래 그게 답의 시작인 줄 알았어요. 그게 구렁텅이인줄은 몰랐지;; 근데 그런 방향으로 시작해서 맞춘 사람도 있다는 거 보면 그냥 제가 독덜인 듯ㅎㅎ

 

Joisc Festival in JOI Kingdom 2

루3 박혀있길래 풀태는 걍 버리고 다항시간 긁자는 마인드로 풀었는데 그냥 n^2이 나와버리네? 87점 움얌얌. 참고로 100점 풀이를 깠는데 online convolution이더라;; offline은 주변에서 많이 봐서 그러려니 할텐데 online은 선넘지~

Joisc Mizuyokan 2

이건 걍 모르겠음 관찰을 열심히 했는데 나오는게 없다. 대충 풀이를 어디선가 들었는데 어디서 튀어나오는건지 모르겠는 관찰을 하더라. 좀이따가 제대로 풀이 까야지.

 

요즘 ps 나름 재미있는 듯. 조이슥도 밀고 유사코도 밀고 조이도 밀고 코이도 밀고 꼬꼬도 밀고 다 움얌얌해서 ps 고수가 되고 싶어요.