Content

제1회 GSHS x SASA 프로그래밍 경시대회 Open Contest 참가 후기

서론

복슬님이 팀연습을 같이 돌자 제안하셔서 lntanz(kolorvxl, mythofys, 6729skl) 팀으로 참여하였습니다.

제가 역대급 비틱으로 찍은 물레이팅라서 kolorvxl 원맨쇼 버스타기가 되었습니다.

부산대에서 만나서 저녁을 먹고 셋을 돌기로 약속되었는데, 저희 집이 부산대에서 지하철을 타고 한 시간 반 거리라 3시에 집에서 출발하고 11시 반에 도착하는 일정이 되어버렸습니다.

kolorvxl이 늦잠을 자는 바람에 6729skl하고 둘이 저녁을 먹었습니다. 제육 + 백반 집이었는데, 6729skl가 밥을 사셔서 맛있게 멌었습니다. 감사합니다!

그러고는 최근 들어 제가 느낀 스피드 포스가 중요한 이유에 대한 설명을 막 늘어놓고 PS 관련 얘기를 하다가 대회 시작 30분 전에 세팅을 시작했습니다. 제가 말도 많고 목소리도 큰 편이라 불쾌하게 여길만한데, 내색하지 않고 잘 받아줘서 고마울 따름입니다.

노트북과 키보드, 충전기를 대충 세팅하고 전략을 세우니 5분 정도 남아서 새 계정을 만들어서 대회에 참여하기는 늦었다고 판단하고 kolorvxl님의 lntany계정을 사용하기로 하였습니다. 또, ICPC 연습이 주 목적이었기 때문에, 인터넷 사용이나 기존 코드 참고도 하지 않았고, 3인 1컴퓨터 대회로 머신을 번갈아가면서 집으며 참여하였습니다.

대회

A가 젤 어려울거라고 생각하고 A를 보는 사람이 문제 개수를 작게 집자라고 판단했는데, 둘 다 틀려서 결과적으로는 좋은 판단이 되었습니다. 6729skl이 ABC를, kolorvxl이 DEFG를, 제가 HIJK를 집기로 하였습니다.

문제를 다 읽고 나서도 다들 풀이를 내지 못했고, 5분쯤 지난 시점에 스코어보드를 보니 A, C에 제출이 있길래 제가 C를 집었습니다.

대충 정리해보니 1 N-1 2 N-2 … 순서로 인접한 gcd가 되게 배정하는 것이 답인 것으로 보였는데, 짜다보니 스코어보드에 빨간 줄이 그이길래 그 방법이 맞는지 다시 점검할 필요가 있었습니다.

6729skl가 A 풀이를 냈다길래 머신을 넘기고 식정리를 열심히 했습니다.

6729skl가 갑자기 __int128__을 어떻게 쓰는지 물었습니다. “그거 python 쓰면 안돼요?”를 시전하고 저는 C를 계속 봤고, 노트북 세팅을 대충해서 __int__128이 로컬에 컴파일이 안 된 덕분에 제출하면서 컴파일 에러가 나는지도 체크해야 했습니다. 그러다가 C 풀이가 나와서 머신을 넘겨달라고 하고, C를 짰는데 WA를 받았습니다.

6729skl에게 A를 짜라고 머신을 다시 넘기고 kolorvxl이 DEFG가 어려워 풀이가 나오지 않는다고 하여 C를 같이 봐달라고 했습니다.

아무리 봐도 증명이 틀릴리가 없었고, kolorvxl이 assert를 짜서 검증하고 제출하라고 해서 다시 머신을 집고 검증을 assert를 돌려 통과하는지를 검증하고 냈습니다.

assert를 안 돌렸으면 아마 거진 4~5번은 더 틀렸을 것 같습니다.

그러고는 제가 슼보에서 그나마 젤 많이 풀린 K를 집었습니다. 딱봐도 자료구조를 적절히 잘 쓰는 문제 같았는데, 멀티셋 + 유니온 파인드로 관리하는 풀이가 빠르게 보여 kolorvxl에게 설명해주고 짜줘를 시전했습니다.

머신을 kolorvxl이 집고, 6729skl의 코드를 눈 디버깅하면서 문제를 읽어보는 와중 답 검증 과정이 long long 범위를 벗어나지 않는걸 발견하고 설명해줬습니다. 금방 고칠 수 있을 것 같다고 하여 머신을 6729skl이 집고 long long으로 고쳐서 냈고, 다행히 맞을 수 있었습니다.

다들 머신을 잡거나 풀이 구체화를 하는 사이 저는 H를 읽었고, 대충 N2^L개의 상태를 관리하면 되는 문제인걸 눈치채 kolorvxl에게 K를 짜고 H를 보면 짤 수 있을거니까 짜달라고 큐에 H를 추가했습니다.

제외하고는 슼보상으로는 F, G가 제일 풀만해보였고, 손으로 써봐도 모르겠어서 kolorvxl이 K짜는 걸 구경하다가 6729skl이 낸 F찍기 풀이 반례가 존재하는지 손으로 열심히 써봤습니다.

딱봐도 F가 대충 맞는 풀이 같아서 H를 짜다가 막히면 교대하기로 하였는데, H가 그냥 구현 문제인데다가 kolorvxl이 거의 다 짠 것 같아 H를 제출하고 F를 짜기로 하였습니다. H를 짰으나 WA가 나왔고, 머신을 교대하여 6729skl이 F를 짰습니다.

그 사이 kolorvxl이 H를 눈디버깅해서 틀린 곳을 찾았고, F도 WA를 받아 다시 교대했습니다. 다행히 틀린 곳을 고치니 맞았고, F도 6729skl이 문제를 다시 읽어보니 3대신 0을 출력하여 문제 조건에 위배되는 것을 확인했고, 해당 부분을 고쳐 내니 맞았습니다.

제가 스코어보드를 훑으니 스코어보드 아래쪽의 몇 팀도 B를 푼 것을 발견하고 B를 보았습니다. M제한이 매우 작기 때문에 그냥 A, B를 번갈아가며 bfs를 수행하되, A부터 시작하는 방법과 B부터 시작하는 방법 중 최소가 되는 방법으로 수행하면 될 것이라는 풀이를 냈고, 정당해보였습니다. bfs를 그냥 짜면 N^3으로 시간초과가 날 것 같은데, 어떻게 해결할지 몰라 kolorvxl에게 설명해주니 짤 수 있겠다고 하더니 200줄짜리 코드를 짜러 갔습니다.

그동안 6729skl과 저는 나머지 문제 중 하나 이상의 풀이를 내보려고 하였으나 만만한 문제는 남아있지 않았고, 30분에서 1시간 가량 고민했으나 결론이 나오지 않았습니다.

그 사이 kolorvxl이 코드를 다 짜고 예제가 나온다길래 풀이 스케치 중 나왔던 데이터를 넣어 돌리고 맞으면 내보라고 하였고, 이가 답이 올바로 나오지 않아 디버깅을 거친 후 맞았습니다.

30분 밖에 남지 않아서 한 문제 이상만 풀면 성공이라는 마인드로 찍는 풀이라고 있으면 좋으니 짤 풀이가 있으면 풀이가 있는 사람이 짜기로 하였습니다. kolorvxl이 몇 분 고민하더니 G 풀이를 찾은 것 같다면서 짜왔고 AC를 받았습니다. 레드는 다르긴 한가봅니다.

15분 정도 남았길래 풀이를 찾아도 못 짤 것 같아 저와 kolorvxl은 자리 정리를 시작했고, 6729skl은 I가 재미있어 보인다며 I를 쭉 집다가 대회가 종료되었습니다.

다른 모든 팀의 프리즈 이후 제출이 맞아도 순위가 3등인 것이 확정되었기 때문에 스코어보드가 풀리기 전부터 순위를 아는 상태로 구경하였습니다.

돌아볼 점

3시간 대회여서 확실히 시간이 짧다는 것이 느껴졌습니다. kolorvxl이 문제 풀이를 내는데 힘 쓸 시간이 없었던 것 같은데, 제가 키보드를 쓰는 것보다 익숙한 사람이 쓰는게 빠르다고 키보드를 핵심 전략에게 토스한게 잘못된 판단이었나 봅니다. 이변이 없다면 UCPC를 kolorvxl과 나갈 예정이라 합을 맞추는게 상당히 중요한데, 웰노운 골드 ~ 플하위급 문제를 10 ~ 15분 정도 보면 풀이를 낼 수 있는 저와 30분 정도의 시간이 있으면 플 중 ~ 상위를 풀어낼 수 있는 괴물 같은 능력을 지닌 kolorvxl의 조합이 상당히 잘 맞는 것 같아 다행입니다.

특히, H와 K를 토스하지 말고, 제가 그냥 풀이를 내자 마자 집고 풀었다면 kolorvxl이 구현만 하다가 끝나 문제 풀이를 낼 시간이 부족하게 대회가 끝나지는 않았을 것 같은데 그게 아쉽습니다.

B번이 비교적 쉬운 문제인데 스코어보드를 보고 확인해서 핵심 관찰을 해서 kolorvxl에게 넘겨 준 점이나, 스코어보드를 따라 적당히 쉬운 골드 ~ 플 하위급 문제들을 빠르게 풀어낸 점은 성공적었습니다. C번 assert 검증을 하고 내라고 했던 kolorvxl의 판단도 상당히 좋았습니다. 아마 ICPC 본선을 겪고 최대한 검증하고 제출하려고 하는 것 같은데, 결과적으로 ICPC 아시아 챔피언십도 진출하고 발전할 수 있는 계기도 된 것 같아 좋게 작용한 것 같습니다.

여담

kolorvxl이 내년 연세대로 가는게 확정 된 것 같은데, 내년 연세대 팀이 우승 후보 중 하나로 꼽힐 것 같습니다. 이번 대회에서도 아무것도 안 했는데 버스를 탄 것 같아 상당히 좋았습니다.

검수진, 출제진 난이도를 대충 보니 셋이 5시간이면 나았을 것 같다는 생각은 듭니다. 물론 5시간 셋이라면 지하철 막차가 문제로 제가 참여하지는 못했겠지만요.

풀이

• A : 자기장에 관한 지문은 훼이크고 그냥 경로와 점이 주어지면 해당 경로 위에서 점과 가장 가까운 점을 찾는 문제입니다. 경로가 무조건 x좌표축이나 y좌표축에 평행하기 때문에 경로 선분의 시작점, 끝점, x좌표나 y좌표가 주어지는 점의 좌표와 같아지는 순간 3가지 경우만 잘 체크해주면 됩니다.
• B : ABAB…, BABA… 순서로 bfs하기 두 가지 경우만 고려해주면 최악의 경우에도 O(N)번만 bfs를 수행하여 풀 수 있습니다. 이미 방문한 칸을 방문하지 않게 잘 처리해주면 O(N)번의 bfs동안 최대 O(N^2)개의 칸만 방문하게 할 수 있습니다.
• C : 1 * 1, (n-1) * 1, (n-1) * 2, (n-2) * 2, …으로 구성해주면 인접한 gcd가 각각 (1, n-1, 2, n-2, … )이 되게 할 수 있습니다. 인접한 수의 gcd가 1이기 때문에 무조건 정확히 저 gcd값을 가진다는 것을 쉽게 증명할 수 있습니다. 제한이 살짝 타이트하여 잘못하면 a_i가 10^8을 넘을 수 있다는 것에 유의하여야 합니다.
• F : 1 0 2 1 0 2 …로 배치하되, N을 3으로 나눈 나머지가 1, 2, 0일 때 각각 수를 어떻게 더 붙이는게 최악으로 만들 수 있는지를 고민한 다음 이게 최악일 것이라고 믿고 제출했습니다.
• G : 행, 열들 중 가장 최솟값이 최대인 행, 열들부터 순차적으로 연산해주면 그게 최대한 수를 줄이는 방법입니다.
• H : N * 2^L개의 상태 전부에 대해 머신 실행 중 중복되는 상태에 도착하면 머신이 종료되지 않고, 그 전에 종료된다면 멈춥니다.
• K : 각 좌표의 절댓값이 최종적으로 무엇이 되는지만 알면 충분합니다. map에 abs(x) + abs(y)를 기준으로 저장한 다음, 파라메트릭 서치를 합시다. 해당 하는 원소를 1 감소시켰을 때, 이미 맵에 존재하는 원소라면 두 원소는 앞으로 계속 함께 감소할 것이고, 같은 값을 가지므로 유니온 파인드를 이용해서 묶어줍시다. 최종적으로 유니온 파인드로 묶은 자료구조의 루트들의 값만으로 이루어진 map이 남고, 유니온 파인드의 루트 찾기 연산을 이용해서 각 좌표의 최종 절댓값의 합을 알 수 있습니다. 이를 안다면 좌표 절댓값이 그렇게 되게 구성하는 것은 쉬운 문제입니다. 초기에 abs(x) + abs(y)가 같은 값들을 유니온 파인드로 묶어야 한다는 것에 유의하여야 합니다.

긴 글 읽어주셔셔 감사합니다!

CF Master(오렌지) 달성 후기 + PS 회고록 + Educational Codeforces Round 186 (Rated for Div. 2) 후기

서론

연말 코드포스 라운드 몇 개를 잘 쳐서 운 좋게 오렌지를 달성하게 되었습니다. 여태까지 살아오면서 이렇게 cp를 열심히 한 적이 없었던 것 같은데, 성과가 안 나와서 초조했었는데 운 좋게 성과가 나오게 되었습니다.

PS 회고

저는 중학교 1학년 때 c++과 ps를 학원에 다니면서 처음 접하게 되면서 학원 OJ 사이트에서 문제를 풀고 공부하면서부터 ps를 시작하게 되었습니다. 중학교 2학년 때 KOI에서는 1차에서도 상을 받지 못하는 고배를 마셨지만, 운 좋게 중학교 3학년 때 중등부 1차 동상, 2차 은상이라는 제 실력을 넘어서는 상을 받게 되었습니다. 영재학교 원서 접수 일주일 전까지도 영재학교의 존재도 몰랐다가 학원에 같이 다니는 친구가 KSA에 정말 가고 싶다고 지원해본다고 하였는데, 저도 당시 과학고등학교에 진학하는 것을 지망하고 있었고, 그래서 함께 지원하게 되었습니다.

Ps 지식과 자신감으로 가득하던 저는 2차 문제들을 ps적 관점에서 접근해서 풀어내며 운 좋게 2차 시험을 잘 치게 되어 KSA에 최종 합격하게 되었습니다. 막상 가서는 ps를 열심히 하지는 않았던 것 같습니다. IOI 계절학교도 지원해서 붙었었는데, 하필 학교 성적이 저조해서 계절학기를 들어야 했던 바람에 좀 고생을 많이 했습니다. IOI 처음반에서는 zoom 수업을 통해서 조교님들이 과제를 내주고, 그걸 5시간 정도 푼 다음, 서로 풀이를 토의하는 시간을 가졌는데, 여름학교까지만 해도 그래도 꽤 되는 친구들이 문제를 풀려고 노력은 했었는데 겨울학교에 가니 맨날 푸는 친구들만 문제를 풀고 나머지 친구들은 zoom을 틀어만 놓고 놀았습니다.

저는 필수문제 1~2문제 정도만 풀고 노는편이었고, 생각해보면 그런 좋은 교육을 무상으로 받을 수 있는 기회였는데 어느 정도 날리기도 했던 것 같습니다. 당연히 선발고사 날에는 밤낮까지 바뀌어서 고생을 했는데, 첫째 날에는 AC코드라고 생각했던 코드가 섭테 20번대 후반에서 터져버려서 대체 어디서 틀린건지 디버깅만 하다 찾지 못해서 망했고, 둘째 날에는 그냥 자버려서 시험 응시조차 안 하는.. 멋진 경험을 했습니다.

APIO도 나갔었는데, 그냥 저냥 제 실력에 비해서는 꽤 잘 본 것 같습니다. B번 30점 섭테가 굉장히 쉬운 골드 하위급 구현이어서 짰고, C번도 플 하위급 관찰을 하면 91점 정도를 받을 수 있어 그걸 긁은 다음 A번이 뭔 소린지 이해를 못해서 못 짰던 기억이 납니다. 선발고사를 망친 덕분에 당연히 계속반에는 못 갔고, 나중에 보니 처음반에서 맨날 문제 다 풀고 토의하던 고수분들은 국대가 되어 계시더군요.

학교 수업을 안 듣고 딴 짓하거나 백준하거나 둘 중 하나를 해서 티어를 꽤 올렸습니다. 아마 codeforces에 본격적으로 입문하기 전인 2학년쯤에도 다이아 정도의 티어를 찍었던 걸로 기억합니다. 그러다가 flakepowders 가 꼬셔서.. codeforces에 입문하게 되었습니다. 몇 판 정도를 잘 쳐서 블루 상위를 한 번 기록한 이후, 블루에서 쭉 진동했던 걸로 기억합니다. PS보다는 시험기간에는 벼락치기하고, 평소에는 놀고를 반복했던 것 같습니다.

Nypc도 몇 번 참여했었는데, 1학년 때에는 2-A에서 남들 다 푸는 검은 점 하얀 점 연결 dp를 당연히 알 리가 없었기 때문에 그걸 부분점수도 못 긁었고, 1번은 상당히 쉬운 골드급 문제여서 풀었던 걸로 기억합니다. 3번이 드론이었던 걸로 기억하는데, 답과 경로 역추적에 반반 점수가 걸려있는 문제였습니다. 시간이 모자라서 미쳐 코드를 다 못 짜서 역추적 코드를 못 짜고, 답 점수만 받아 50점을 받았는데, 좀 더 열심히 했으면 구현도 다 마치고, 2번 문제에서 부분 점수를 받아 본선에 한 번 더 가지 않았을까 싶습니다. 2, 3학년 때에는 그래도 짬이 있어서인지 어떻게든 추합권 안에 들어 본선에 갔다왔습니다. 2023년에 참가상으로 키보드를 안 줘서 상당히 실망했었는데, 다행히 2024에는 키보드를 줘서 아직까지 잘 쓰고 있습니다.

Codeforces를 안 해서 대회 출제 조건을 만족 못 하는 바람에 KSAAC 출제도 계속 유기했었는데, 블루를 몇 판 해서 찍어서 마지막 학기에는 참여할 수 있게 되었습니다. 지금 생각해보면 너무 자료구조 위주의 문제만을 내서 셋이 특정 사람들에게 유리한 셋이 된 것 같아 아쉽습니다. 그 사이에 cenix820 이 카이스트 프로그래밍 기초 과목 학점 인정 시험을 준비한다길래 jakekim0105, loreips, davidkim0 이랑 열심히 갈궜습니다. 다들 열심히 ps, cp를 안 접고 어느 정도 성과를 이루어 상당히 뿌듯합니다.

대학 입시도 열심히 놀았기 때문에 성공할 수 없었고, 한양대학교에 진학하게 되었습니다. 학기 초에 mathtw1030, lion0625 랑 팀을 짜서 UCPC, ICPC 팀을 미리 확정 짓고, 팀연습은 제가 유기를 많이 했습니다. UCPC는 거의 막차를 타서 본선을 나가는데 성공한 덕분에 본선에서 꽤 많은 것들 것 받아오고, 재밌게 칠 수 있었습니다. 이때까지만 해도 자신만만했는데, 열심히 하게 된 계기는 SCPC 본선을 못간게 컸습니다. 하루종일 문제를 풀었는데 남들이 다 긁는 5번 부분점수를 flush를 너무 많이 하는 바람에… 시간 초과를 받아서 못 긁게 되었고, 이로 인해서 본선 커트라인에 아슬아슬하게 걸려서 갔다 올 수 있었던 것을 못 가게 되었습니다.

CF 입문

그 이후로 제 실력에 부족함을 많이 느꼈고, 어떻게 연습할까 고민하던 와중 cywohoy님의 버추얼 같이 도는 방이 보였고, 버추얼을 함께 많이 돌게 되었습니다. 이때부터 그래도 0.75일에 버추얼 셋 하나 정도는 돌았던 것 같습니다. 방학 동안 버추얼 함께 돌아주셨던 cywohoy, kenn3n, hakuaa_2, 0917ba, meow_love, tjrn3712, kcits970, kolorvxl, lumitt, justin8021, jkrt2, aerae, Arpia님께 감사드립니다. 누구 빼먹지는 않았겠지? 저랑 같이 버추얼 돌았는데 빠져있어서 화나신다면 dm을 보내주세요.

그 덕분에 올해 codeforces에서만 400문제를 채웠습니다.

방학 내내 셋을 돈 덕분에 버추얼 기준으로는 퍼플을 찍었습니다. 이후 ICPC 인터넷 예선이랑 lgcpc를 시원하게 말아먹으면서 HCPC라도 잘 쳐서 상금을 쌀먹하려고 중간고사가 끝나자마자 버추얼을 신나게 돌렸습니다. 운 좋게 스피드 포스 셋을 빠르게 풀거나, div2E 정도의 문제가 저에게 잘 맞게 나와 비록 virtual이지만 오렌지를 달성할 수 있었습니다. 이때 기준으로 실제 rating으로도 퍼플은 금방 갈 거라고 생각했는데… 저점이 한도 끝도 없이 낮아서 블루에서 진동하는 그래프가 만들어졌습니다.

멘탈이 완전 나가있던 와중 방학이 찾아왔고, 기어이 버추얼 오렌지를 다시 찍었습니다. 이제 퍼플에 도달하는 건 시간 문제라는 생각이 많이 들었습니다. 결국 기어이 잘 치는 날이 찾아와버립니다.

(12/11 23:35 ~ 12/12 01:35), Codeforces Round 1070 (Div. 2)

• A : 우선순위를 잘 정해서 없애면 자신보다 앞에 큰 수가 있다면 그 수는 무조건 없앨 수 있습니다. 이를 이용해서 체크해주면 간단히 풀 수 있습니다.
• B : 연속한 0 집합의 길이의 max값이 답입니다.
• C : 가장 큰 홀수 코인, 짝수 코인 개수 순으로 내림차순으로 두는 것이 최적이고, 위 동전들을 다 채웠다면 앞에 홀수 코인을 2개씩 추가해주면 됩니다.
• D : ai가 0일 수 없기 때문에 ai가 작은 정점부터 이 정점이 가능한 경로의 마지막 항일 때, 이전 항으로 가능한 값을 가진 map이나 unordered_map을 정점마다 관리해주면서 dp를 해주면 됩니다.
• E : 0으로 만드는 연산을 안 할 때는 각 값마다 자신의 왼쪽에서 자신보다 큰 값, 오른쪽에서 자신보다 큰 값 중 작은 값과 합쳐 없어지는게 이득입니다. 이를 거꾸로 생각하여 작은 값부터 각 값을 기준으로 이전 값들로 없애지 않은 값들 중 자신의 왼쪽에서 자신보다 큰 값, 오른쪽에서 자신보다 큰 값 사이에 있는 값들은 이 값으로 없애는게 가능하고, 가장 최적입니다. 이를 이용해서 각 값을 없애는데에 필요한 비용을 세그먼트 트리의 lazy propagation을 이용해서 구할 수 있고, 이 합이 답이 됩니다. 0으로 바꾸는 연산도 해당 범위의 모든 값을 0으로 바꾸어 주는 것으로 처리할 수 있습니다. 따라서 이를 이용하면 문제를 해결할 수 있습니다.

(12/19 23:35 ~ 12/20 02:05) Codeforces Global Round 31 (Div. 1 + Div. 2)

• A : 아무리봐도 성질이 안 보이는데 브루트 포스를 짜는데 오래 걸릴 것 같지 않아 나이브를 짰습니다.
• B : 그리디하게 합친 현재 문자열이 앞에 붙는게 이득인지 아닌지를 판별해주면 됩니다. 바보 같이 이상한 걸 짜서 2번 틀리고 패널티를 잔득 먹고 AC를 받았습니다.
• C : k가 홀수일 때는 n을 k번 출력하는 것이 자명한 답입니다. 짝수일 때가 중요한데, 짝수일 때는 큰 비트부터 보되, 하나 이상의 값에서 해당 비트를 비워야 합니다. 첫 비트에서는 하나의 값을 비우는 것밖에 할 수 없고, 이후 그 값 자리에는 나머지 비트를 전부 포함하더라도 n을 넘지 않으므로 해당 자리는 자유롭게 비트를 채울 수 있는 자리가 됩니다. 이 관찰을 이용하면 맞을 수 있습니다.
• D : 그리디하게 현재 원의 가능한 r의 최솟값, 최댓값을 관리하면서 답을 구해나가면 맞을 수 있습니다.
• 전체적으로 무려 7번이나 틀려 패널티를 크게 받았지만, 패널티를 다들 많이 받는 셋이었는데다가, CD를 동시에 푼 사람이 몇 없어 퍼포먼스가 생각보다 잘 나왔습니다. 이 셋을 통해서 퍼플을 찍었습니다.

(12/27 23:35 ~ 12/28 02:35) Good Bye 2025

• A : Y가 2개 이상 있으면 불가능하고, 아니면 가능합니다.
• B : U를 기준으로 왼쪽, 오른쪽에 S가 무조건 존재하여야 하고, 가장 가까운 왼쪽의 S와 가장 가까운 오른쪽의 S와의 거리가 같아야 합니다. 이러기 위해서는 U가 두 개 이상 연속하면 안 됩니다. 두 개 이상 연속하는 U를 적절히 S로 바꿔주면 맞출 수 있습니다.
• C : 각 인덱스 i를 기준으로 초기에 i번째에 위치하는 값이 마지막에 남는 값일 때 최적이 무엇일지 계산합시다. i 뒤의 모든 값들은 무조건 부호를 바꾸는 것만 고를 수 있고, 이전의 값들은 1을 제외하고는 절댓값 값으로 고를 수 있습니다. 1은 무조건 기존 부호대로 적용하여야 합니다.
• D : m = 0, m > n/2, 0 < m <= n/2인 세 가지 경우를 잘 나눠서 각 경우에 해를 구성하면 풀 수 있습니다.
• E : 17번 이분 탐색을 하되, 매번 prefix와 suffix의 값이 같도록 쪼개는 방법을 이분탐색을 해서 구합니다. 여기서 쪼개는 방법이 존재하지 않으면 현재 array의 길이와 쪼개진 횟수에 답이 비례하고, 아니면 쪼개진 두 array 중 작은 array에 최댓값이 존재하므로 해당 array에서 이분탐색을 해주면 됩니다. 17 * 17 + 1 = 289 + 1 = 290으로 쿼리 수 제한에 들어옵니다.
• F : 전체 트리를 모든 흰 정점을 기준으로 해당 정점을 루트로 하는 서브트리이되, 해당 서브트리에서 흰색 정점이 존재한다면 해당 정점을 루트로 하는 서브트리를 뺀 트리 여러 개로 나눕시다. 루트는 실제 색과 상관없이 흰색 정점으로 취급합시다. 그렇다면 흰색 정점의 개수만큼의 트리 개수로 나뉘게 됩니다. 조합론적으로 접근하면 이 서브트리들을 순서대로 나열하여 결합하는 경우의 수가 답임을 알 수 있습니다. 이를 적절히 잘 구해주면 됩니다.

( 12/29 11:35 ~ 12/30 01:35 ) Educational Codeforces Round 186 (Rated for Div. 2)

• A : 2025가 존재하거나, 2026이 존재하지 않으면 0, 아니면 2026에서 6을 5로 바꾸면 되므로 1입니다.
• B : 어짜피 초콜릿을 번갈아 가면서 사용하여야 하므로 각 초콜릿을 먼저 사용하는 경우 답 중 최댓값입니다.
• C : 각 j에 대해 조건을 만족시키는 k의 개수 * n을 저장합시다. i에 대해 for문을 돌면서 가능한 j에 대해 해당 개수를 더해주면 됩니다.
• D : sum(ai) / n과 같은 값들은 같은 값들끼리, sum(ai) / n + 1과 같은 값들은 같은 값들끼리 서로 순서를 바꿔도 됩니다. sum(ai) / n + 1이 될 수 있는 값 개수를 세서 위를 수식을 잘 짜서 계산하자. 이때, 답이 0인 경우에 대해 예외처리를 잘 해주어야 합니다.
• E : 그리디하게 각 상자에 대해 이 상자에 선물을 담으면 만족하는 친구 중, zi – yi가 가장 큰 친구를 만족시키기 힘드므로 그 친구에게 줄 선물을 상자에 담읍시다. 상자를 전부 사용했다면 남은 친구들 중 zi – yi가 작은 순서대로 친구의 선물에 동전을 쓰면 됩니다.
• F1 : 힘이 더 낮은 순록을 아무리 많이 가지고 와도 힘이 높은 순록보다 썰매를 더 세게 당길 수 없고, 순록 61마리째부터는 있으나마나라는 관찰을 할 수 있습니다. 따라서 이를 기반으로 마지노선 순록 수를 구할 수 있습니다. 각 ci에 대해 최소한 썰매를 당기기 위한 충분한 힘을 가지기 위해 필요한 ci힘의 순록 수를 bi로 정의합시다. 어떤 순록 그룹에 대해 높은 힘을 가진 순록 수부터 비교했을 때 순록 수가 bi보다 많으면 무조건 가능한 조합이고, 적으면 무조건 불가능한 조합이며, 같으면 더 작은 힘을 가진 순록도 비교해야 합니다. 이를 수학 식을 잘 써서 경우의 수를 구할 수 있고, O(60nm)에 문제를 해결할 수 있습니다.

이렇게 연말에 갑자기 행운이 찾아와서 오렌지를 점수를 딱 맞추어 달성하게 되었습니다. 올해 마지막 라운드인데다가 여태까지 한 번도 잘 친적이 없는 에듀이고, 저번 퍼플 승급전 때 2문제가 핵 당해서 가지 못했던 것 극복한 것 같아 상당히 의미 깊습니다.

아직은 제가 ps, cp를 놓지 않아도 되는 것 같아 안심입니다… 새해가 밝았습니다. 이렇게 성취할 수 있게 여태껏 도와주신 분들께 감사드립니다. 이 글을 읽어주신 여러분들도 새해 복 많이 받으셨으면 좋겠습니다. 긴 글 읽어주셔서 감사합니다.

스택(Stack)

이론적 배경

먼저 이론적으로 스택이 무엇이고, 왜 배우는지 알아봅시다.

스택은 영어로 Stack이고, Stack은 ‘쌓다’라는 뜻이 존재합니다. 스택은 이름처럼 각 값을 블럭처럼 생각하여 순서대로 쌓아서 저장하고, 무너지지 않게 위에서 부터 꺼내여 활용하는 자료구조입니다. 재귀함수가 동작하는 과정에서 앞선 함수들의 변수 값을 저장하는 call stack, 괄호의 짝이 맞는지 체크해주는 code editor 등에서 Stack 자료구조가 활용됩니다. 이런 상황에서 Stack을 활용하기 위해 Stack을 배워야 합니다.

와닿지 않는다면 그림을 통해서 알아봅시다.

▲ 초기 스택은 비어있습니다.

▲ 1이라는 값을 스택에 넣어줍시다.

▲ 이 스택에 5이라는 값을 또 넣어줍시다.

▲ 스택에서 맨 위의 값을 빼줍시다. 이때, 빠진 값은 스택에 먼저 넣은 1이 아닌, 나중에 넣은 5입니다. 스택은 Last in First Out, LIFO 구조로 나중에 넣은 값이 먼저 빠져나가게 됩니다.

▲ 스택이 비어있는데 값을 빼려고 하면 문제가 발생합니다.

그러면 스택이 어떤 것인지 대략적으로 감은 잡았는데, 아직 구체적으로 구현하기는 어려워 보입니다. 그림에서 values, tail의 2가지 변수를 생각해서 관리해봅시다. 각 변수의 역할은 아래와 같습니다.

• values: 스택의 값들을 저장하는 공간입니다. 배열이나 벡터 등으로 구현할 수 있습니다.
• tail: 다음에 스택에 값을 넣을 때, 어디에 넣을지를 가리키는 변수입니다. 인덱스를 저장하는 변수로 사용하거나 포인터로 사용할 수 있습니다.

스택에 값 x를 넣는 연산을 push(x), 스택 맨 위의 값을 빼고, 그 값을 반환하는 연산을 pop()연산으로 정의합시다. 이제 push(x) 연산은 values[tail++] = x로 수행할 수 있고, pop() 연산은 return values[--tail]을 통해 수행할 수 있습니다.

시간복잡도

• push(x) : O(1)
• pop() : O(1)
• top() : O(1)
• size() : O(1)
• isempty() : O(1)

아래는 스택을 C++ class로 짠 코드입니다.

#include <iostream>
#include <assert.h>
using namespace std;

class Stack {
    private:
    int tail;
    int *values;
    int _size;

    public:
    void init(int initial_size) {
        tail = 0;
        _size = initial_size;
        values = new int[initial_size];
    }

    void push(int value) {
        assert(tail != _size); // Stack Overflow
        values[tail++] = value;
    }

    int pop() {
        assert(tail != 0); // Stack Underflow
        return values[--tail];
    }

    int top() {
        assert(tail != 0); // Stack is empty
        return values[tail - 1];
    }

    int __size() {
        return tail;
    }

    bool isEmpty() {
        return tail == 0;
    }

    bool isFull() {
        return tail == _size;
    }

    int* getValues() {
        return values;
    }
};

int main() {
    Stack* stack = new Stack();
    int initial_size;
    cout << "Enter initial stack size: ";
    cin >> initial_size;
    stack->init(initial_size);
    while (true) {
        int choice;
        cout << "1. Push\n2. Pop\n3. Top\n4. Size\n5. Is Empty\n6. Is Full\n7. Print Stack\n8. Exit\nEnter your choice: ";
        cin >> choice;
        if (choice == 1) {
            int value;
            cout << "Enter value to push: ";
            cin >> value;
            stack->push(value);
            cout << value << " pushed to stack\n";
        } else if (choice == 2) {
            cout << "Top element " << stack->pop() << " popped from stack\n";
        } else if (choice == 3) {
            cout << "Top element is " << stack->top() << "\n";
        } else if (choice == 4) {
            cout << "Stack size is " << stack->__size() << "\n";
        } else if (choice == 5) {
            cout << "Stack is " << (stack->isEmpty() ? "empty" : "not empty") << "\n";
        } else if (choice == 6) {
            cout << "Stack is " << (stack->isFull() ? "full" : "not full") << "\n";
        } else if (choice == 7) {
            int* vals = stack->getValues();
            cout << "Stack elements: ";
            for (int i = 0; i < stack->__size(); i++) {
                cout << vals[i] << " ";
            }
            cout << "\n";
        } else if (choice == 8) {
            break;
        } else {
            cout << "Invalid choice, please try again.\n";
        }
    }
    delete stack;
    return 0;
}

각 함수를 어떻게 구현할 수 있는지 살펴봅시다.

• init(): 초기 스택의 최대 크기를 설정하고 tail = 0으로 설정하여 스택에 값을 넣고 뺄 수 있게 한 함수입니다.
• push(x): values[tail++] = x를 수행하여 스택에 값을 넣습니다. 이때, 스택에 할당한 메모리 이상에 접근하면 문제가 발생하므로 assert문으로 예외처리하여 줍시다.
• pop(): return value[--tail]을 수행하여 스택의 가장 위 값을 return해주면서 stack의 크기를 1 줄여줍니다. 마찬가지로 tail == 0인 경우 음수 인덱스에 접근하여 문제가 발생하므로 assert문으로 예외처리하여 줍시다.
• top(): return value[tail-1]을 수행하여 스택의 가장 위 값을 return해줍니다. pop()과 같이 tail == 0인 경우 음수 인덱스에 접근하여 문제가 발생하므로 assert문으로 예외처리하여 줍시다.
• __size(): 스택의 크기를 반환합니다. 이때, 스택에는 0부터 tail-1까지의 인덱스에 값이 채워져 있고, 이때 크기는 tail이므로 return tail을 수행합니다.
• isEmpty(): 스택이 비어있는지 체크합니다. tail == 0이면 비어있는 것이고, 아니면 비어있지 않은 것이므로 return tail == 0을 수행합니다.
• isFull(): 스택의 크기와 할당된 메모리의 크기가 같은지 체크합니다. 초기에 할당한 메모리의 크기를 _size에 저장하고 return tail == _size를 수행합니다. tail == _size이면 최대 크기이므로 이를 return하여 줍시다.
• getValues(): 스택 전체의 값을 출력하는 함수입니다. 원래는 존재하지도 않고, 스택의 연산에도 속하지 않지만, 스택의 값을 실시간으로 파악할 수 있도록 출력해주는 함수입니다.

이제 어떻게 구현할 수 있는지까지 다 알아보았으니 문제를 풀어봅시다.

백준 10828번: 스택 https://www.acmicpc.net/problem/10828

그냥 위 템플릿과 유사하게 문제의 입출력 형식에 맞추어 스택의 연산을 수행해주면 문제를 해결할 수 있습니다. 이때, 스택의 메모리에 최대 10000개의 정수가 입력될 수 있으므로 최대 크기를 유의해서 잡아줍시다.

소스코드

#include <iostream>
#include <assert.h>
using namespace std;

class Stack {
    private:
    int tail;
    int *values;
    int _size;

    public:
    void init(int initial_size) {
        tail = 0;
        _size = initial_size;
        values = new int[initial_size];
    }

    void push(int value) {
        assert(tail != _size); // Stack Overflow
        values[tail++] = value;
    }

    int pop() {
        assert(tail != 0); // Stack Underflow
        return values[--tail];
    }

    int top() {
        assert(tail != 0); // Stack is empty
        return values[tail - 1];
    }

    int __size() {
        return tail;
    }

    bool isEmpty() {
        return tail == 0;
    }

    bool isFull() {
        return tail == _size;
    }

    int* getValues() {
        return values;
    }
};

int main() {
    Stack* stack = new Stack();
    int initial_size;
    cin >> initial_size;
    stack->init(initial_size + 1);
    while (initial_size--) {
        string option;
        cin >> option;
        if (option == "push") {
            int value;
            cin >> value;
            stack->push(value);
        } else if (option == "pop") {
            if (stack->isEmpty())cout << -1 << "\n";
            else cout << stack->pop() << "\n";
        } else if (option == "top") {
            if (stack->isEmpty())cout << -1 << "\n";
            else cout << stack->top() << "\n";
        } else if (option == "size") {
            cout << stack->__size() << "\n";
        } else if (option == "empty") {
            cout << (stack->isEmpty() ? "1" : "0") << "\n";
        }
    }
    delete stack;
    return 0;
}

꼭 매번 이렇게 코드를 길게 작성하여야 할까요? 그렇지는 않습니다. 코드를 구현하기 위한 간단한 구현체도 존재하고, 편리하게 사용하게 해주는 라이브러리도 존재합니다.

보통 저는 아래처럼 class를 정의하지 않고 간단하게 구현하여 문제를 해결합니다.

소스코드

#include <iostream>
#include <assert.h>
using namespace std;

int stack[10005],tail;

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        string option;
        cin >> option;
        if (option == "push") {
            int v;
            cin >> v;
            stack[tail++] = v;
        } else if (option == "pop") {
            if (tail == 0)cout << -1 << "\n";
            else cout << stack[--tail] << "\n";
        } else if (option == "top") {
            if (tail == 0)cout << -1 << "\n";
            else cout << stack[tail-1] << "\n";
        } else if (option == "size") {
            cout << tail << "\n";
        } else if (option == "empty") {
            cout << (tail ? "0" : "1") << "\n";
        }
    }
    return 0;
}

또, <stack> 라이브러리에 stack 구현체가 존재합니다. (deque를 안다면 실제로는 deque로 구현되어 있다는 것을 참고하면 좋습니다.) 해당 라이브러리에서도 구현해놓은 stack의 연산들을 사용할 수 있습니다.

연습문제

백준 28278번: 스택 2
백준 9012번: 괄호
백준 1874번: 스택 수열
백준 2493번: 탑
백준 6549번: 히스토그램에서 가장 큰 직사각형
백준 11873번: 최대 직사각형

AtCoder ABC420-A 문제 풀이

문제 링크

https://atcoder.jp/contests/abc420/tasks/abc420_a

알고리즘

수학

시간복잡도

$O(1)$

풀이

$X + Y$가 $12$보다 작거나 같으면 $X + Y$월이 되므로 쉽게 문제를 해결할 수 있습니다.

ABC420-B 문제 풀이

문제 링크

https://atcoder.jp/contests/abc420/tasks/abc420_b

알고리즘

구현, 문자열

시간복잡도

$O(NM)$

풀이

최대 점수를 직접 구할 필요는 없으므로 상대 점수만 고려합시다.

Atcoder 문제 모음

김강민님 팬이에요

진짜 사람이 어떻게 김강민이지 개고수