plast / 코딩공부

SUAPC summer 대회에서 1등을 했습니다!

이미 킹갓 Serendipity 형님이 준수한 필력으로 맛깔나게 잘 써주셔서, 자세한 대회후기는 해당 블로그 링크를 남겨놓습니다 :)

저는 그보다는 우리팀 PS:Endgame과 올해의 PS에 대한 저의 생각들을 좀 적어보고자 합니다.

이번 SUAPC 대회에 참여한 PS:Endgame 팀(JyJin, Serendipity__, plast)은 올해 처음으로 함께 팀 연습을 하게 되었습니다. 작년 연세대 팀은 팀원을 바꿔가며 팀 연습을 진행했기에 대부분의 사람들과 함께 팀을 해봤지만, 흥미롭게도 JyJin, Serendipity__와는 한 번도 같이 해본 적이 없었습니다. 팀별 밸런스를 맞추는 과정에서 우연히 이렇게 된 것 같습니다. 결국 올해 4월 말에야 처음으로 팀 연습을 진행하게 되었습니다.

제가 팀연습을 해보면서 느낀건 두명 모두 정말 좋은 팀원이라는 것입니다. JyJin은 팀대회에서 정말 특장점이 있는 친구입니다. 어느 상황에도 제일 침착하고 저점이 굉장히 높아서 항상 안정적인 퍼포먼스를 보여줍니다. 대회 현장에서 보면 이렇게 믿음직할수가 없습니다. 또한 문제풀이의 소통이 매우 잘돼서 개떡같이 아이디어를 제시해도 찰떡같이 알아듣고, 바로 아이디어의 정당성을 판단합니다. 동시에 더 좋은 아이디어가 되도록 굉장히 빠르게 이야기를 발전시킵니다. 어떻게보면 Serendipity__ 형님이 써주신 비유가 아주 정확한데, 저와 JyJin은 합이 많이 좋은것 같습니다. 둘이 만나서 문제를 풀면 좀 유별나게 문제가 잘 풀린다고 느껴집니다.

Serendipity__ 형님 또한 매우 뛰어난 능력을 보여줍니다. 그의 문제 풀이 스타일은 저와는 다소 차이가 있습니다. 제가 문제를 보고 단계별로 관찰하고 추론해가며 푼다면, Serendipity__ 형님은 자신의 경험과 지식을 바탕으로 유사한 문제들을 빠르게 연관 지어 접근합니다. 이러한 능력 덕분에 제가 어려워하는 문제에 대해 조언을 구하면, 오히려 즉각적인 해결책을 제시하는 경우가 많습니다. 또한, 제가 문제에 대한 접근 방식을 설명하면, 그것을 바탕으로 더 발전된 아이디어를 도출해내어 난이도 높은 문제들을 직접 해결하는 모습을 자주 보여줍니다.

Serendipity__ 형님은 우리 팀이 교집합이 많다고 설명했지만, 세 명의 팀원이 비슷한 능력을 가졌다기보다는, 각자 뚜렷한 특성과 강점을 가지고 있다고 생각합니다. 한 사람이 어려워하는 문제를 다른 사람이 잘 풀어내고, 원활한 소통을 통해 한 사람이 막힌 부분을 다른 사람이 이어받아 더 발전시키는 식의 상호보완적인 팀워크가 잘 이루어집니다. 이러한 점에서 우리 팀은 팀 대회에서의 강점이 특히 잘 드러나는 조합이라고 생각합니다.

올해 우리 팀은 매우 기대되는 강팀으로 느껴집니다. 제가 스스로 저희팀한테 너무 높은 기대를 갖는 것이 아닌가 하는 걱정도 있지만, 레드 레이팅을 가진 멤버가 두 명이나 있는 팀이니 이 정도의 기대는 자연스러운 것 같습니다. ㅋㅋ 여튼 팀소개는 여기까지 하고 마치겠습니다.

저는 현재 3년차 직장인입니다. 학교를 다니면서 직장도 다니고 PS도 병행해왔지만, 회사 생활을 하면서 다른 활동을 병행하기가 얼마나 어려운지 실감하고 있습니다. PS는 즐겁지만, 이를 평생 취미로 두고 싶지는 않습니다. 제가 PS를 시작하고 나서 제가 이루고자 했던 최종 목표는 코포 레드와 앳코더 오렌지를 달성하는 것이었습니다. 이 목표를 달성한 후에는 회사에서 더 도움이 되는 역량을 키우고 싶다는 생각을 해왔습니다.

이번에 PS에서 제가 설정한 목표를 달성했기에, 2024년 ICPC를 끝으로 PS 공부에 마침표를 찍으려고 합니다. 조금 아쉽기도 하지만, 원래는 작년에 PS를 마무리하려 했던 것이 어쩌다 보니 같은 생각을 가진 사람들과 함께 1년을 더하게 되었습니다.

올해가 정말 마지막인 만큼, 박수받는 퍼포먼스로 마무리하고 싶습니다. 말 그대로 박수칠 때 떠나는 멋진 마무리를 꿈꿔봅니다.

다음 대회 후기는 Icpc로 뵙겠습니다.

https://ktypsblog.tistory.com/21

오랜만에 글 쓰러 왔다

이번 UCPC는 ICPC팀과는 다르다! 약간의 사정이 있어 UCPC 팀은 plast, sk091204, changhw와 함께 했다. 경욱이(sk091204)는 군대 가기 전 사실상 마지막 팀대회다. 군대 잘갔다오렴... 현우형(changhw)은 다른 팀이 있었는데 어쩌다가 잡혀와서 같이 하게 됐다.

대회를 준비하면서 가장 힘들었던 것은.. 역시 팀명을 정하는 것이었다.

분명히 "Akiyama Mizuki Fan Club!" 보다 나은 팀명이 있다면 24시간 내에 알려달라고 했는데

다들 24시간동안 조용히 있었던걸 보니

너무 마음에드는 팀명이였나보다

사실 하나 있었는데 노잼이라 넘어갔다

결국에는 1주일동안 내가 팀명 팀명 거리면서 울부짖었는데

팀이름 그대로 이름이 됐다

돌이켜보면 너무 감이 없었다

팀원들 몰래 Akiyama lovelovelove 이딴걸로 신청해놓을걸 그랬나보다

UCPC 예선

헉

생각했던 것보다 지나치게 폼이 좋았어서 정말 놀랐다

우선 내가 말이 안됐다

A -> D -> C -> J -> H 라는 초스피드 풀코스를 탔는데 무려 B4 G2 P4 P5 G2 까지 푸는데 1시간이 걸렸다. 여기까지 풀고 나니 팀원들이 풀고 있는 문제를 빼면 B, F밖에 안남았다. 띵가띵가 놀다가 F를 잡았고 P1 을 풀어 2시간 쯔음에 10솔을 했다.

마지막으로 B가 남았는데, 사실 내가 F 슛을 하는 동안 나머지 둘이 4를 construct하다가 gg쳤다

그걸 보고 내가 훈수를 뒀지만 잘못된 훈수였고 우리는 못푸는 문제겠구나 하고 그냥 때려치고 띵가띵가 놀았다

끝나고보니 올솔이 5팀이나 됐다. 그래서 6등이 됐다. 생각보다는 쉬운 문제라던데 흠 잘 모르겠다.

지금 와서 복기를 하려 하니, 이것 외에는 잘 기억이 안난다. 아 우리팀의 G번 코드가 매우 흥미로웠다는 것도 기억난다.

보면서 한참 웃었다

무슨 문제인지는 모르겠지만 엄청 골때리는 문제를 잘 풀어준 것 같아서 고마웠다

대신 이렇게 코드짜고 틀렸다면 딱밤 세대 때렸을거다

UCPC 본선

본선은 살짝 아쉽게 됐다

본인은 D -> A -> M 순으로 풀었다. 개인적으로는 M이 많이 어려웠는데 생각보다 많은 팀들이 풀어서 놀라웠다.

그동안 팀원은 E -> C, L을 차례차례 풀어주며 2시간도 안돼서 6솔을 했다.

그다음으로 해볼만한 문제는 F, H, J였다. J는 트리 문제길래 내가 빠르게 받아서 풀이를 짜왔다.

일단 대놓고 HLD풀이가 보여서 풀이를 정리해봤다. 근데 딱봐도 복잡해서 다른 풀이를 한참 고민해봤다.

하지만 다른 풀이를 못떠올렸다.

나중에 들어보니 sparse table을 이용하는 획기적인 풀이부터, 심지어는 지름의 특징을 이용한 풀이도 있던데 다 엄청 감탄하면서 열심히 복기했다.

어쨌거나 그당시 나는 HLD풀이밖에 안보여서 열심히 열심히 짰다..

그리고 온갖 손테케 만든건 몽땅 맞는 제출하면 30초 돌아가다가 틀렸습니다 띡 뜨는 코드를 짜고 폭사했다

그사이 팀원은 각각 F, H를 보고 풀이가 나왔다. H 풀게 자리를 비켜줬고, 그동안 F는 풀이는 확실하지만 구현방법이 정리가 안돼서 구현을 어떻게 할지에 대해 대화했다

어떻게든 꾸역꾸역 H를 푼 와중에 내 J는 걍.. 아무리 봐도 맞다. 뭘 넣어도 맞다.

왜 틀림???

마지막까지 투덜거리다가 끝났다

그냥 F를 들어갔어야 했나 싶지만 J를 확정적으로 맞은 뒤에 들어가는게 맞는 판단이기는 했던 것 같다. 내가 똥을 싸서 문제지..

HLD를 다시 제대로 공부해야겠다는 생각을 했다.

그냥 여러 요소에서 배울 것들이 많은 셋이였다

이상

저희 내용은 https://ktypsblog.tistory.com/19 여기에 더 잘 올라가 있어서

자세히 적기는 귀찮습니다 ㅋㅋ 그냥 가볍게 적고 갈게용

저희는 연세대학교 Cookie(쿠키) 팀으로 Asia Pacific Championship 참여했습니다! (plast, dreami63, sk091204) 아시아 23등으로 마무리했습니다.

저희팀은 올해로 쫑내기로 했던 팀이구요 (재혁이형(drami63)은 나이 문제로, 경욱이(sk091204)는 군대 문제로 저희 팀은 올해 해산입니다! 물론 경욱이는 군대 다녀오면 코딩의 신이 되도록 제가 책임지고 만들 것 입니다 우하하)

간단히 팀에 대해 소개를 하자면, 23년 1월 SUAPC때 왠지 레이팅 높아보이는 사람들 데리고 참여했고 세 명 모두 대회장에서 처음 만나게 되었습니다. 대회때 푸는 실력을 보는데, 너무너무 잘하셔서.. "이분들 진짜 잘하시는데?" 하고 즉석으로 ICPC팀을 만들게 되었습니다.

세명 모두 문제 풀이 경험이 적은 편에 속합니다. 이 때에만 해도 백준티어 P2(저), P3(재혁이형), D5(경욱이)이였나? 그랬습니다. 하지만 문제풀이 경험에 비해 코포 레이팅도 높고, 충분히 더 잘할 수 있는 성장 가능성이 보여 1년을 죽도록 하기로 했습니다.

저희팀은 같은 연세대학교 SCC팀과 마찬가지로 많은 연습을 진행했고, 세보지는 않았지만 팀연습 횟수는 50번? 정도는 될 것 같습니다.

팀전략은 다음과 같았습니다.

코드는 80% 제가 잡았습니다. 종종 제가 구현하기 어렵거나, 문제설명이 충분하지 못한 경우에만 다른 사람이 들어갔습니다.

문제 풀이는 세명이 잘하는 영역이 각기 달랐기에 메인 영역을 나누었습니다.

저는 트리, DP, 게임이론, 자료구조,

재혁이형은 그래프, 유랑, 게임이론,

경욱이는 기하 메인으로 맡았습니다.

메인 영역들은 다이아 하위 문제도 안정적으로 잡을 수 있을만큼 공부하기로 했고 어느정도 원하는 퍼포먼스가 나왔다고 생각합니다. 메인 영역 이외의 영역은 다들 P3 까지는 안정적으로 잡을 수 있었던 것 같습니다.

그외에는 처음 열린 아시아 리저널이여서 한국팀들과 친해질 기회가 많았는데, 특히 서울대 NewTrend팀, 포스텍 Allsolvedin1557팀이랑 우연히 뷔페 옆자리, 크루즈 옆자리에 앉게 돼서 대화를 많이 나눴던 것 같고 새롭게 느끼는게 많았습니다. 두 팀 다 WF 파이팅입니다! 🥳

그외에는 1년간 죽도록 같이 연습했던 연세대학교의 SCC팀도 지금 상황에 따라 WF를 갈 수도 있는 상황에 놓여있는데 반드시 갔으면 좋겠습니다.

한국 리저널에서 3등 제한이였다면 WF는 꿈도 못 꿨을 텐데, Asia Pacific Championship 덕분에 운이 좋았다면 WF를 바라봤을 수 있었던것 같고, 해외까지 와보면서 맛있는 밥도 먹고 많은 경험을 할수 있게 되어 너무 기뻤습니다. 내년에도 할까요? ㅋㅋ 지금은 잘 모르겠습니다.

WF를 너무 나가보고 싶은 생각도 반, IQ 200을 찍어보고 싶다는 생각(=탈 알고)도 반쯤 있습니다. ㅋㅋ 1년간 모두 수고하셨습니다!

본선 4등상 수상하였습니다!

1번 문제를 보았습니다.

처음에는 살짝 어려울줄 알고 쫄았는데 홀짝성만 봐도 끝나는 문제였습니다. 바로 짜서 맞췄습니다.

(0:10) 1번 +100점

2번 문제를 보았습니다.

열심히 생각을 정리하니 로봇은 항상 가장 근거리에서 만나야지만 최선임을 이용해서 DP식이 세워지고, 이 직선의 형태가 CHT로 변형될 수 있다는것이 어렵지 않게 떠올랐습니다. 개인적인 감상으로는 문제 발상 자체는 난이도가 낮았어서 많이들 생각했지 않았을까 싶습니다.

그걸 바탕으로 우선 O(N^2)인데 CHT로 바로 변형 가능하도록 코드를 짜는데.. 어라 생각보다 쉽지 않습니다. 구현이 너무 빡셈을 느끼고 겨우겨우 짰지만 오답이 나왔습니다.

(1:20) 2번 WA

이때 살짝 멘붕이 왔습니다. 왜냐하면 코드를 개떡같이 짜놔서 디버깅 해야 할 것이 산더미인데, 제가 사전점검도 안해와서 디버깅조차 제대로 할 수 있는 상황이 아니였기 때문입니다. 그래도 제 구현능력을 어느정도 믿어보고 이것저것 훑어봤지만, 아무리 봐도 틀린게 없었습니다.

멘탈이 펑 터진채로 아니 나만 못푸는건가? 싶어서 돌아왔더니 2번 정답자수는 0명이였고 왠 4번이 많이 풀려있었습니다.

휴~ 그럼 그렇지 ㅎ 하고 4번으로 갔습니다.

그런데 4번은 더더욱 멘탈이 터졌습니다. 뭘 해야 할지 머리가 띵 해졌습니다.

가장 큰 숫자를 a라고 할 때 양쪽으로 나뉘는 특징과, 가장 작은 숫자를 a라고 할때 양쪽의 특징을 살펴보며 접근했는데, 제 문제풀이 경험으로는 이럴 때 큰 숫자를 기준으로 하는 경우를 많이 봤어서 큰 숫자일때 특징을 위주로 살펴봤습니다. 열심히 식을 정리했더니 O(N^4)짜리 DP식이 나왔습니다. 오... 심지어 공간복잡도도 O(N^4)이라 그냥 답이 없었습니다.

이게 아닌거 같은데 싶으면서도 제 문제풀이 경험으로는 이 풀이밖에 없다는걸 본능적으로 알고있었어서 더 나아가지도 못하고 빼지도 못하는 상황에서 1시간이 더 흘러갔습니다.

아 제대로 말렸구나 싶어서 조금 있다가 다시 보는편이 좋을 것 같아 다시 2-2로 넘어왔습니다.

다행히도 2-2의 오류가 여러개 보이기 시작했습니다. 제가 바보같은 전처리를 몇개 해놓은 바람에 반례 데이터를 찾을 수 있었습니다.

겨우 2:40쯔음에 눈에 보이는 오류들을 고치고 다시 제출했습니다. 하지만 오답이 나왔습니다.

(2:40) 2번 WA

이젠 진짜 멘붕이 왔습니다. 3시간째가 됐는데 제 점수는 100점이고 그냥 아무생각도 나지 않았습니다..

정말 이대로는 망한다 하면서 2-2의 반례데이터를 무지성으로 만들어봤습니다. 그러다가 운좋게 하나가 얻어 걸렸습니다. 잠깐 고민해 보니, 로봇을 정지해 두고 나중에 바꿔치기 하는것이 이득인 경우가 추가로 있었습니다. 이에 대한 처리를 해 주었고, 이번에는 141점이 나왔습니다.

(3:00) 2번 +141점

그래도 141점을 맞으니 희망이 보였습니다. 이 상태에서 4번만 맞아도 5등상은 받겠다는 생각이 들었습니다. 그래서 4번 문제를 아얘 처음부터 차분히 접근을 했습니다.

그런데 왠걸, 처음에 생각했던 큰수 작은수 중에서 작은수를 기준으로 점화식을 고민해보니 엄청 쉽게 식이 나왔습니다. 울부짖으며 코드를 작성했고 바로 만점이 나왔습니다.

(3:20) 4번 +200점

이 문제는 후에도 복기를 정말 많이 했습니다. 제가 왜 말렸는지도 좀 고민을 해 보았고.. 다시는 말리지 않도록 점검을 많이 했습니다.

아무튼 시간이 30분이나 주어졌습니다. 저는 이제 두 가지 선택지가 있었습니다.

이미 풀이를 아는 2-3을 긁기 vs 3번을 파기

둘다 유효한 선택지였다고 판단했습니다. 왜냐하면 저는 2-3에도 자신이 있었고 3번은 트리문제인데 저는 트리문제에 한해 슈퍼 무적이기 때문에 30분따리여도 다 긁어버릴 수 있을거라는 자신이 있었습니다.

먼저 2-3을 해보자는 결론을 내렸고, 잠깐 고민해보니 생각보다 만만치 않음을 느꼈습니다. 왜냐하면 로봇이 멈추는 쿼리가 추가되면서 컨벡스헐이 기울기가 감소하는 방향으로만 주어지지 않았기 때문입니다. 잠깐 이것저것 끄적여 봤는데 유의미한 결과를 얻지 못했고 아쉽게도 15분정도를 버리게 되었습니다.

나중에 돌이켜 보면 그냥 두개의 컨벡스헐을 만드는게 유효한 전략이였고, 정말 최근 코드포스에서도 한참 심화된 버전이 나온적이 있었는데 (https://codeforces.com/contest/1866/problem/K) 시간에 쫓겨 빠르게 포기한게 살짝 후회됐습니다.

3번으로 걱정없이 가게 된 것은, 제가 트리에 무한한 자신감이 있던 것도 한몫했어서.. 뭐 다시 돌이켜도 같은 선택을 하고 있었을것 같기는 합니다.

3번을 읽어봤습니다. 그런데 생각보다 심상치 않았습니다. 각 서브트리에서의 최선의 전략을 찾아내야 할것 같았는데 잘 정리되지 않았습니다. 10분정도 더 고민해봤는데 안떠올라서, 너무 아쉽지만 3-1이라도 긁어보겠다고 열심히 코드를 짰습니다. 그런데 틀렸습니다.

후에 보니 급히 짜다가 테케가 여러개인 것을 고려하지 않고 입력을 받는 바람에 메모리 초과가 났던 것으로 정리됐습니다.

총점 441점을 받았고, 복기를 해보면서 너무 초기접근을 이상하게 했거나, 시간에 쫓겨 허투른 판단을 했던 것들이 많이 보여 아쉬움이 많이 남았습니다.

무엇보다 총점이 너무 애매했어서 (4등상 - 5등상 사이 어딘가) 5등상을 받으면 슬플 것 같았습니다.

하지만 대회 끝, 수상식! 다행히도 4등상 턱걸이를 했네요... 정말 다행입니다. 좀 말렸으면 어때요 4등상 받았으면 그만이야~! 이제 저는 다시 행복해졌습니다.

조금 늦은 감이 있지만 그래도 올려놓는게 맞는거같아서 후기 올립니다

본선 14등으로 아이패드 수상하였습니다!

1번 문제를 보았고, 잠깐 고민해 보았더니 아주 좋은 그리디 풀이가 떠올랐습니다. 바로 짜서 10.2점을 받았습니다.

만점이 아니길래 반례를 잠깐 고민을 했었는데, 다른 사람들도 다 10.2점을 받았길래 테케가 틀렸겠거니 하고 바로 2번으로 넘어갔습니다.

(0:10) 1번 +10.2점

2번 문제를 잘 기억은 안나는데 뻘짓을 엄청 열심히 했습니다. 문제 상황도 똑바로 이해 못했고, 최단 경로 내부 / 외부 각각에서 처리해줘야 하는 것들이 있는데 둘다 잘못 생각해서 엄청 여러번 고치고 나서야 겨우 돌아가는 코드를 작성했습니다.

한참을 디버깅한 뒤 겨우 20점 만점을 받았습니다.

(1:30) 2번 +20점

이제 다음 문제를 볼까 1번 문제를 볼까 잠깐 고민을 했는데, 구사과님조차 1번을 10.2박고 2, 3번을 풀러 가셨길래 아하 1번은 거들떠도 안봐야겠구나 하고 넘어갔습니다. 이 뒤로 1번문제는 제 머릿속에 지워져서 끝까지 다시 안돌아갔습니다.

3번을 봤습니다. 근데 딱봐도 SCC를 일단 해야될것 처럼 생겼습니다. 문제는 제가 SCC를 짜본지 3년이 돼가서 기억이 하나도 안났습니다. 개념만 알고있는데 뭔가 dfs를 하고 역방향 순으로 뭘 했던거 같은데... 머리가 아파왔습니다. 4번을 읽으러 갔습니다.

4번은 O(QN^2)은 구현하기 어렵지 않은 문제였습니다. 그 이상을 풀기 위해서는 45도를 돌려줘서 뭔가를 더 해야 할 것 같았는데, 대회중에는 시간 여유가 없었어서 깊게 생각해보지는 않고 아 마지막 문젠데 어렵겠지 하고 빨리 포기했습니다.

아무튼 O(QN^2)으로 짜서 4.9점을 받았습니다.

(2:00) 4번 +4.9점

번외로 이문제 4.0점이신분들도 많던데 믿음의 N 5000덕분에 테케 하나를 더 맞췄던 것 같습니다. 그 외에도 ans = N * M - 1로 하나를 더 긁을 수 있었다고 하니 억지로 긁으려고 했다면 5.9점까지는 해볼만 했다고 합니다.

다시 3번으로 돌아왔습니다. SCC를 구현해야 아이패드를 받을수 있다 하고 머리 꽁꽁 싸매면서 생각해봤는데.. 생각보다 잘 안떠올랐습니다.

그러다가.. 다행히도 N = 500임에 착안해서 플로이드-와셜로 SCC를 짜보자! 라는 생각을 했습니다. O(N^3)짜리 SCC를 짜는 기행(...)을 선보이니 실제로 잘 돌아갔습니다.

근데 SCC를 구현했는데 딱히 문제를 보면서 아무 생각도 안 떠올랐습니다. 아 망했구나. 하고 에라 모르겠다 식으로 outdegree가 0인 점을 세줬더니 12.6점이 나왔습니다.

(2:30) 3번 +12.6점

이제 저는 못풀줄 알았던 SCC도 짰고 12.6점도 긁어서 너무 행복해져서 뒤에는 제대로 집중을 못했습니다.

후에 복기해보니, 12.6점에서 살짝의 휴리스틱만 섞어도 20점까지 금방 올랐고 조금 잘 다룰 경우 26점까지도 받을 수 있었다고 합니다.

제가 그래프 영역에는 익숙하지 않은 것도 있고, 기하와 더불어 가장 못하는 영역이기도 하다 보니 부족함이 유독 드러났던 지점이였지 않았나 싶습니다. 더 많이 공부해야겠다는 생각을 했습니다.

최종적으로 10.2 + 20 + 12.6 + 4.9 = 47.7점으로 14등 마무리했습니다.

대회 끝나고 나서는 아이패드 못받을까봐 살짝 불안했는데 생각했던 것보단 안정권이여서 다행이였습니다.

3~4월 첫 복기는 풀었던 문제 중 기억나는 DP류 문제만 복기한다.

개인적인 복기용이므로 가독성이나 남들이 이해할수 있는가 등등은 아예 신경 안썼다. 아마 나만 알아볼듯.

풀이가 대놓고 적혀있기 때문에 스포를 주의한다.

21343. Great Expectation (D4 / nwerc 2020 G) ★★

리셋이라는 기능을 DP식에 잘 녹일 수 있을까? 를 묻는 문제.

DP임을 눈치채기는 쉬우나 점화식을 만드는 것이 상당히 까다롭다.

1) 기대값을 DP에 어떻게 담는가?

2) 리셋을 DP에 어떻게 담는가?

3) DP 갱신을 파라매트릭 서치로 할 수 있는가?

세가지의 중요한 관찰포인트가 있고 셋 다 처음 봤다. 너무 의미있는 문제였음. 여기 적혀있는 하나씩만 해도 굉장한데 그 많은걸 한 문제에 다 녹여냈기 때문에 더 좋았다. 강추

25994. Crashing Competition Computer (P5 / bapc 2022 C)

윗 문제의 3단 열화 버전.

1) 기대값을 DP에 어떻게 담는가?

위에서의 요지 중 가장 쉬운 관찰포인트에 해당한다. 그조차도 힌트가 많아서 더 찾기 쉬운편. 이전 문제를 푼 뒤에 이 문제를 풀게 돼서 그런가 더 쉽게 느껴졌다. 복습용으로 굿이였다

26969. Bribing Friends (P2 / usaco 2022 dec gold 1) ★★

매우 흥미로운 정통 DP 문제.

1) DP에 greedy한 전략이 있을 때 무엇을 할 수 있는가?

2) DP식의 시간복잡도를 줄이기 위해서는 무엇을 해야 하는가?

여러 의미로 아주 도움이 많이 된 문제다. 이것도 강추

24488. Drought (P3 / usaco 2022 jan gold 1) ★

이것도 무난무난한 DP문제이다. 근데 못풀었다..

1) 총 가짓수를 구하라고 했을 때 뭘 할수 있을까?

2) DP 갱신의 시간복잡도를 어떻게 줄일 수 있을까?

기본적인 문제인 것 같은데 아직 경험이 부족한 것 같다. 꼭 완벽히 다지고 넘어가야 할 문제 중 하나라고 생각한다.

27556. Lights Off (P2 / usaco 2023 jan gold 2) ★

관찰을 기반으로 한 전처리 DP 문제.

1) 여러 쿼리가 주어지는데 모든 쿼리에 똑같은 공통점이 있을때, 어떻게 활용해야 할까?

2) 기존의 값이 지속적으로 진행될 경우 이를 수식적으로 어떻게 표현할 수 있을까?

관찰이 메인인 코포틱한 문제. 2400급에 나올법한 문제였다. 구현도 생각보다 까다롭고 문제가 되게 좋다.

12013. 248 game (G5 / usaco 2016 open gold 3)

전형적인 구간 쿼리 문제.

1) 합친다는 개념을 어떻게 정의하는 것이 좋을까?

풀이 단박에 떠오르지는 않았다. 그래서 한번 더 복기하려고 들고왔다. 좋은 dp문제라고 생각한다.

23872. Paired Up (P2 / usaco 2021 dec gold 1) ★

1차원 좌표계에서의 DP 문제.

1) 1차원 좌표만이 가지는 특징은 무엇이 있을까?

2) pair가 있을 때의 최선의 전략과 그를 기반으로 할 수 있는 것은 무엇이 있을까?

3) 식의 관리는 어떻게 하는게 좋을까?

대부분의 관찰들이 매우 의미있다고 생각한다. 좋은 문제. 아직 못맞춰서 꼭 풀어봐야 한다.

20645. Bovine Genetics (P1 / usaco 2020 dec gold 2) ★★

아주 좋은 정통 DP문제.

1) ? 연산자를 DP에서 어떻게 이용할 수 있을까?

2) DP식은 어떻게 세우는 것이 올바른가?

정통 문제인데 아직도 못풀었다. 꼭 풀어볼 생각임.

21230. Moder Art 3 (P2 / usaco 2021 feb gold 2) ★

매우 신기한 구간 DP문제.

1) base를 어떻게 관리하는 것이 좋을까?

2) 어떤 원리로 구간DP의 식을 정의할 수 있을까?

여러번 다시 읽어보고 다시 곱씹어볼 필요가 있는 문제라고 생각한다.

15759. Talent Show (P3 / usaco 2018 open gold 3)

무난무난한 DP문제.

1) DP 내에서 그리디한 전략이 존재할 때, 어떻게 활용하는 것이 좋을까?

2) 여러 가지 경우의 수로 분기되어 있을 경우 어떻게 접근하는 것이 좋을까?

무난한 DP 기본형 문제라고 생각한다. 기본을 다지자!

27234. 컵 쌓기 (P2 / hello boj 2023 D) ★

구간 DP 경우의수 문제.

1) 구간 DP를 통해 경우의 수를 셀 때, 중복되어 세지 않도록 어떻게 관리해야 할까?

경우의 수를 구하는 구간DP의 가장 일반적인 문제라고 생각한다. 한번쯤은 풀어봐야 한다고 생각함.

div1 850-D. Wooden Spoon (2400) ★★

토너먼트 상에서의 DP문제.

꼭 풀어볼 생각이다.

div1+2 844-F. Bracket Insertion (2700) ★

괄호 속에서의 DP문제.

꼭 풀어볼 생각이다.

25998. Grinding Gravel (D5 / bapc 2022 G) ★★

전혀 DP로 보이지 않았던 np처럼 생긴 문제.

1) n = 100 내외일때, 다항시간에 문제를 풀기 위해 어떤 접근을 하는 것이 좋을까?

2) DP로 변환하기 위해서는 어떤 조건이 필요한가?

개인적으로 되게 신기했다. 아주 좋은 문제라고 생각한다.

SUAPC 2등!!

사실 팀 목표는 1등이였고, 가능성도 꽤 높았다고 생각했는데 이런저런 아쉽게 됐다. 이 셋 기준으로는 아무리 잘했어도 10솔 하기는 힘들었을 것 같다. 1등팀이 굉장히 잘했다. ㄷㄷ

피드백 할만 한 문제들만 몇개 정리한다.

C. 점수 내기

A와 B가 게임을 합니다. A는 조건을 만족하는 최대 점수 문자열을, B는 조건을 만족하는 최소 점수 문자열을 만들려고 합니다. 다음 조건에서 A와 B가 최선을 다했을 때 받을 수 있는 점수를 출력해주세요. (A와 B가 만드는 문자열은 알파벳 소문자와 숫자를 이용할 수 있습니다.)
조건 : 만든 문자열 S에 대해, '접두사 목록'에 존재하는 문자열 S의 접두사들의 점수를 모두 더합니다. '접미사 목록'에 존재하는 문자열S의 접미사들의 점수를 모두 더합니다.
총 q(3e5)개의 쿼리에 대해, 다음 4 종류의 쿼리가 주어집니다. 주어지는 쿼리의 문자열 길이의 총합은 1e6을 넘지 않습니다.
쿼리 1 : 접두사 목록에 문자열 T와 점수 x를 추가합니다. (T는 알파벳 소문자만으로 이루어져 있습니다.)
쿼리 2 : 접미사 목록에 문자열 T와 점수 x를 추가합니다. (T는 알파벳 소문자만으로 이루어져 있습니다.)
쿼리 3 : A가 만들수 있는 최대 점수를 출력합니다.
쿼리 4 : B가 만들수 있는 최소 점수를 출력합니다.

풀이는 다음과 같다.

1. 접두사 목록과 접미사 목록을 분리해서 생각할 수 있다. 예를 들어 접두사 목록 abc와 접미사 목록 ba를 쓴다고 할 때, 반드시 abc0ba와 같이 가운데에 숫자로 벽을 칠 경우 모든 예외를 막을 수 있다.

2. 접두사 목록에서 최대 점수/최소 점수 접두사를 판단하기 위해 트라이 + lazy로 관리할 수 있다. 자세한 관리방법은 다음과 같다.

2 - a. 트라이에 꼭 필요한 정보 : max, min, num, lazy

2 - a. 트라이에 새로운 노드가 입력된다. -> 그냥 큰 문제 없이 이전 노드의 num을 가져와 갱신해주면 된다.

2 - b. 트라이에 기존의 노드가 입력된다. -> max, min, num에 모두 x만큼 갱신한다. lazy를 이용해 자신의 아랫 노드에 전부 뿌려주며, 동시에 자신의 parent들의 max, min을 갱신한다.

10틀... 10틀.......

이 문제에 한이 엄청 쌓였다....

풀이는 거의 바로 찾았지만, 트라이도 처음 써봤고 거기에 익숙치 않은 lazy비빔밥이 얹혀지면서 제대로 폭망했다. 처음 코드에서 고칠게 이중 삼중 사중으로 있었다.(...) 마지막까지 틀렸지만 사실 마지막에 제출한 코드에서 한 줄만 고쳤다면 정답코드였다. 그것은 바로 lazy를 갱신해줄때 lazy값을 0으로 비워주는것... 실화냐..

디버깅에 대해서도 고민을 많이 하게 됐다. 예전에는 반례를 무지성으로 찾아내면서 디버깅하는것을 선호했는데, 그냥 코드를 열심히 읽는 편이 훨 나을 것 같다. 코드 읽는 실력도 예전보다 훨씬훨씬 늘었고 걍 코드만 3번 읽었으면 오류를 다 찾았을 것 같다. 2시간동안 뭘 한건지 모르겠다..

E. 슬라이딩 퍼즐 마스터

N * M (N * M ≤ 9) 보드판이 있습니다. 여기에는 1 ~ (N * M - 1)까지의 숫자와, 빈 칸 하나가 주어집니다. 다음 두 가지 연산중 하나만을 이용해, 모든 상태를 중복 없이 전부 나타내세요.
연산 1) 빈 칸에 인접한 숫자를 이동시킵니다.
연산 2) 인접한 숫자 두개를 서로 바꿔치기합니다.

풀이는 다음과 같다.

1. 사실 빈 칸은 숫자와 동일시 해도 상관 없다.

2. 2차원 배열처럼 보이지만, 사실 스네이크 형식으로 본다면 1차원 배열과 똑같다. 즉, 1차원 배열 9개의 9! 상태를 바로 인접한 숫자와 swap해서 모든 상태를 한번씩 이동하는 문제가 된다.

3. 길이가 n인 순열을 관찰해보면, 가장 앞 숫자 a를 골라 a를 가장 오른쪽으로 보내보자. 그러면 a를 제외한 (n - 1)길이의 순열에 대해 길이가 n인 순열에서 나올 수 있는 모든 상황이 기록된다. 이를 바탕으로 a를 계속 좌우 끝과 끝으로 이동시켜 가며 (n - 1)길이의 순열에 대해 재귀적으로 반복하는 방식으로 풀 수 있다. (Steinhaus–Johnson–Trotter Algorithm)

이 문제는 다음 두 가지 이유로 난이도가 굉장히 높다.

1) 풀이 2, 3번의 관찰이 어렵다. (특히 3번)

2) 풀이 3번에 해당하는 재귀함수가 구현이 상당히 까다롭다. (본인은 역순으로 구현을 했는데, 정답자 코드를 읽어보니 vector<int>를 인자로 받아 n = 9에서 재귀로 구현하던데 그 편이 한참은 쉬울 것 같다..)

이 문제는 돌아가도 풀기 어려웠을 것 같다. 풀이 2 관찰까지는 금방 했던 편이였는데, 풀이 3 관찰은 아무리 생각해봐도 난이도가 너무 너무 높다.. 이 문제는 구현 난이도도 상당하다.

이런 유형의 문제를 풀기 위해서는 순열의 특징에 관해 깊게 공부해봐야 할 것 같다. 최근 AGC 61 A에서도 비슷한 문제가 나와 크게 데였다. 그 문제는 짝수 길이의 순열에서만 생기는 인접한 원소끼리의 특징을 바탕으로 했다. 이 문제는 원소를 하나 쭉 돌아갈 때 나머지 순열의 위치를 관찰하라는데.. 솔직히 발상 난이도가 지나칠 정도로 높다. 어떻게 발상하는건지 아직도 이해가 안간다.

I. UFO in Sinchon

N(1e9) * M(1e9) 짜리 격자에서 K(2e5)명의 사람이 있고 Q(2e5)번 순서대로 UFO가 나타납니다.
K명의 사람은 UFO가 나타날 때마다 매 턴 택시거리로 가장 가까워지도록 가로, 세로, 대각선 8방향 중 한 방향으로 이동합니다. UFO와 같은 위치에 있다면 이동하지 않습니다.
UFO는 (x, y, t) 형태로 나타나며 (x, y)위치에 나타나 t(1e9)턴 후 사라집니다.
K명의 최종 위치를 모두 구해주세요.

풀이는 다음과 같다.

1. x와 y는 분리해서 생각해도 된다. 즉, 1차원에서 현재 위치가 a, 우주선이 (x, t)형태로 주어질 때 q번의 ufo가 나타나고 갈 위치를 잘 관리하는 문제로 변한다.

2. 우주선이 (x, t)로 나타나면, (x - t)보다 작은 경우 a + t, (x - t ~ x + t)의 경우 x, (x + t)보다 큰 경우 a - t의 위치로 최종 이동한다.

3. 이 정보를 바탕으로 lazy segment tree에 y = ax + b(순서대로 (a = 1, b = t), (a = 0, b = x), (a = 1, b = -t))를 잘 관리해 갱신한다.

이건 접근 1은 내가 했지만 2, 3번은 다른 팀원이 했다. 사실 2~3은 처음 보는 유형이였어서 시간을 들였어도 쉽게 풀지는 못했을 것 같다.

추가 예정

L. 따로 걸어가기

N(2e5)행 M(2e5)열의 2차원 격자가 있습니다. 두 행인 A, B에 대해, 다음 경우의 수를 구하세요.
- A, B가 1행 1열에서 N행 M열까지 오른쪽, 혹은 아랫쪽 방향으로 한칸씩으로만 이동해 도착할 때, 둘이 시작점과 끝점을 제외한 모든 점에서 마주치지 않는 가짓수 

풀이는 다음과 같다.

1. 두명의 이동은 결국 오른쪽과 아래중 하나의 경로를 동시에 택하는 선택과정의 연속이라고 볼 수 있다. (두 명의 경로를 따로 보지 않고, 두명이 동시에 이동한다고 보자.)

2. 이동방식은 4가지밖에 없고, 특징을 잘 살펴보면 그 안에서도 규칙이 발생한다. 규칙은 다음과 같다.

2 - 1. 이동 방식은 (D, D), (D, R), (R, D), (R, R) 밖에 없다. ( (R, D)는 1번 사람이 오른쪽으로, 2번 사람이 아래로 이동한다는 뜻이다.) 이 이동방식을 순서대로 이동1, 이동2, 이동3, 이동4라고 하자.

2 - 2. 1, 2번 사람은 둘 다 D를 총 n번, R을 총 m번씩 이동해야 하기 때문에 이동횟수 간의 연립식이 생긴다. 정리하면 이동1이 k회 이동했을 때, 이동2 = 이동3 = n - k번, 이동4 = m - n + k번 이동하게 된다.

2 - 3. 일반성을 잃지 않고 n ≥ m이며 1번 사람은 처음에 D로, 2번 사람은 처음에 R로 이동했다고 치자. (n < m인 경우에는 n, m을 바꿔주면 되고, 1번 사람과 2번 사람이 반대로 이동한 경우는 정확히 횟수가 똑같기 때문에 최종 답에서 2배 해주면 된다.) 그러면 항상 이동2 횟수 ≥ 이동3 횟수를 유지해야 하기 때문에 (이동2, 이동3)은 올바른 괄호쌍을 만드는 카탈란 수로 표현해줄 수 있다.

2 - 4. 1번 이동 각 가능한 k에 대해, 전체 이동에서 이동1의 위치, 이동4의 위치, (이동 2 + 이동 3)의 위치를 선정하는 가짓수 * 이동2와 이동3을 적절히 배치하는 카탈란수 가짓수를 정리하면 O(n)에 총 가짓수가 나온다.

나는 대회때 한 10분정도 보고 포기한 문제인데, 나중에 풀어보고 난 후 난이도는 생각했던 것보다는 쉬웠다. 접근 1이 생소한 것 같고, 접근 1을 올바르게 했다면 뒷부분은 대회때 풀었을 것 같다.

접근 1은 완전히 처음 보는 유형인데, '두 명이 서로 다르게 이동한 경로' 라는 키워드에서 생각해볼 수 있을법한 좋은 접근인 것 같다. 항상 총 가짓수 구하는 유형에 약하다. 이쪽 유형도 많이 공부해야겠다는 생각이 자주 든다.

C. Complementary XOR

0과 1만으로 이루어진 n(2 ≤ n ≤ 2e5)자리 문자열 a, b가 있습니다. 다음과 같은 연산을 최대 n + 5번까지 했을 때 모든 문자열을 0으로 만들 수 있는지 판단하세요.
연산 (l, r) : i = l ~ r까지의 문자열 a의 0과 1을 전부 반전시킵니다. 그리고 1 ~ l - 1, r + 1 ~ n까지의 문자열 b의 0과 1을 전부 반전시킵니다.

이 연산 (l, r)은 문자열 a는 i = l ~ r까지는 반전시키고 문자열 b는 i = l ~ r까지를 제외한 전부를 반전시킨다. c라는 것을 정의해 c[i] = (a[i]와 b[i]가 같다면 1, 다르다면 0) 이라고 할 때, 연산은 어떤 구간을 잡아도 항상 c를 1 ~ n 까지 전부 반전시킴을 알 수 있다. 즉 처음부터 c[i]가 모두 같지 않다면 이 연산만으로는 a와 b를 전부 0으로 만들수가 없다.

그 뒤에는 평범하게 a의 연속된 1 무리들을 전부 0으로 변환해주면 된다. 그러면 b는 전부 0이거나 전부 1이 되는데, 전부 1이 될 때에는 (1, n), (1, 1), (2, n) 순으로 3번의 연산을 더 거치면 b까지 전부 0으로 바꿔주는 것이 가능하다.

이 문제를 풀 때 생각을 잘못해서 몇번 삐끗했다. a를 전부 0으로 만들어도 b가 전부 1이되면 방법이 없을 거라는 생각에 좀처럼 답을 찾지 못했다. 그런데 생각해보면 예제에서 친절하게 '111 111' 을 보여줬기 때문에 이 예제의 해결법을 연관지어서 생각했다면 더 빠르게 풀이를 찾아냈을 것 같다.

D. Count GCD (1800)

n(1 ≤ n ≤ 2e5)개의 숫자로 이루어진 수열 a가 있습니다. 다음과 같은 조건을 만족하도록 b배열을 만들 때, 가능한 가짓수를 구하세요.
- 모든 i에 대해, gcd(b[1], b[2], ... , b[i]) = a[i] 를 만족한다.
- b의 원소는 전부 1 이상 m(1 ≤ m ≤ 1e9) 이하이다.

b[i]로 가능한 숫자가 몇개인지 생각해보자. gcd(b[1], b[2], ..., b[i]) = a[i]의 식에서 시작해, 공약수의 성질을 바탕으로 gcd(a[i - 1], b[i]) = a[i]로 나타낼 수 있다. 이 조건을 만족하기 위해서는 b[i]는 a[i]의 배수이면서 (a[i - 1] / a[i])와 (b[i] / a[i])는 서로소여야 한다. a[i]의 배수인 수의 개수는 m / a[i]로 바로 판단이 가능하고, 서로소인 수의 개수는 포함배제의 원리를 이용해 각 약수를 바탕으로 판단이 가능하다.

안그래도 포함배제의 원리에 대해 공부하고 있었는데 연습 도중 바로 볼 수 있어서 좋았다. 포함배제의 원리를 이용하는 수학문제는 코드포스에서 가장 전형적인 문제 중 하나라고 생각한다.

E. Bracket Cost (2400)

n(1 ≤ n ≤ 2e5)개의 소괄호 "(", ")"만으로 구성된 문자열 a가 있습니다. 해당 문자열의 모든 연속부분문자열에 대해, cost의 합을 구하고 싶습니다. cost는 다음 연산을 최소로 이용해 올바른 문자열로 만들 때, 필요한 최소 연산 수를 의미합니다.
- 연산 1 : 해당 문자열의 아무 연속부분문자열을 선택해, 한 칸씩 왼쪽으로 밉니다. 예를 들어, ")()("을 선택하면 이 부분은 "()()"이 됩니다.
- 연산 2 : 아무 위치에 ")" 혹은 "("을 하나 추가합니다.

연산 1이 무엇인지부터 자세히 관찰해 보자. 예를 들어 연산 1을 할 때 문자열 ")(())("을 선택했다고 치자. 해당 문자열은 "(())()"이 된다. 즉 문자열 S를 선택했을 때 S의 가장 앞 문자를 S의 가장 뒤로 옮기는 행위라고 생각할 수 있다. 따라서 S의 가장 앞 문자만이 영향을 받는다.

이를 바탕으로 아무 문자열의 cost를 구해보자. ")))(("를 생각해 보자. 이 경우 연산1을 적극적으로 활용하는 것이 좋다. 왜냐하면 쌍이 맞지 않은 ")"와 "("를 동시에 쌍을 맞출 수 있기 때문에 연산2를 2번 해야 하는 것을 1번으로 줄일 수 있기 때문이다. 따라서 연산1을 2번 써서 앞쪽의 ")"를 뒤로 적절히 옮겨주고 하나 남은 ")"의 앞에 "("를 연산2로 붙여주는것이 최선임을 알 수 있다. 이를 조금 더 고민해보면 일반적인 cost를 정의할 수 있다. 문자열에서 쌍이 맞지 않은 ")"의 개수를 p, "("의 개수를 q라고 할 때 max(p, q)가 된다.

따라서 이 문제는 p와 q를 빠른 시간에 관리하고 cost의 총합을 한번에 구하는 문제로 바뀐다. 여기서 O(n^2)의 풀이는 쉽게 찾아낼 수 있다. stack을 활용하면 (1, 1)에서 시작해 (1, n)까지의 p, q를 각 차례마다 O(1)에 갱신해줄 수 있어서 총 O(n)이 걸리며, 이를 반복해 (2, 2)에서 시작, (3, 3)에서 시작, ... , 을 반복하면 된다.

하지만 이 방법으로는 O(n^2)에서 더 낮추기 쉽지 않다. O(nlgn)혹은 그 이하로 줄이기 위해서는 반드시 모든 쌍을 전부 돌지 않고 한번에 연산하는 과정이 필요하다. 여기서 p의 특징을 이용할 수 있다. "("을 +1, ")"을 -1이라고 정리한 순열 a가 있을때, 순열 b를 b[i] = a[1] + ... + a[i], 즉 a의 prefix sum이라고 하자. [l, r] 구간에 대해 p는 b[l - 1] - min(b[l - 1], b[l], b[l + 1], ... , b[r])이 된다. 그리고 q는 b[r] - b[l - 1] + p가 된다. (b[r] - b[l - 1]은 "("이 몇개 더 있는지를 알려주므로, 쌍이 맞지 않는 "("은 전체 "("의 개수에서 전체 ")"의 개수를 빼고 쌍이 맞지 않는 ")"의 개수를 더해줘야 한다.) 따라서 cost를 max(b[l - 1], b[r]) - min(b[l - 1] ~ b[r]) 으로 변형할수 있다.

이 값의 총합을 구하는 것은 max(b[l - 1], b[r])항과 min(b[l - 1] ~ b[r])을 나눠서 생각해 볼 수 있다. max(b[l - 1], b[r])의 총합은 펜윅 트리를 이용하거나 정렬을 통해 가장 큰 수부터 순서대로 n, n - 1, n - 2, ... , 0회 나올 것임을 바탕으로 구해줄 수 있다. min(b[l - 1] ~ b[r]) 항의 경우 펜윅 트리 / 스택 / 분할정복 등으로 히스토그램의 최대 넓이 구하는것과 비슷한 방식으로 처리할 수 있다.

필자는 쌍이 맞지 않는 ")"의 개수 = b[l - 1] - min(b[l - 1], b[l], b[l + 1], ... , b[r]) 이라는 접근을 처음 봤는데, 자주 나오는 성질인 것으로 보인다. 꼭 알아둬야 할 것 같다. 그리고 필자가 모든 경우의 총합을 구하라는 유형에 상당히 약한 것 같은데, 연습을 많이 해야 할 것 같다.

F. Majority (2700)

0과 1로 이루어진 수열이 있습니다. 다음 작업을 통해 수열의 모든 부분을 1로 만들 수 있는지 알고 싶습니다:
- 작업 (i, j) (단, i < j) : s[i] = s[j] = 1이고, 2 * (s[i] + s[i + 1] + ... + s[j]) ≥ (j - i + 1) 을 만족할 때, s[i], s[i + 1], ... , s[j]를 모두 1로 바꿉니다.
수열의 길이가 n(1 ≤ n ≤ 5e3)일 때, 만들 수 있는 모든 수열 중에서 모든 부분을 1로 만들수 있는 수열의 개수를 구하세요. 

추가예정