본문 바로가기

전체 글

 (41)
문제 출제하기 오늘은 여태까지 출제한 문제들에 대해서 문제 출제 과정을 알아볼 것이다. 고등학생 때 플래티넘 열심히 풀던 시절에 문제를 만들고 싶었지만 문제를 하나도 만들지 못했던 과거의 나를 생각해보면 처음 문제 만드는 것이 가장 어려운 것 같다. 그래서 문제를 처음 만드는 사람들에게 조금이나마 도움이 되고자 내가 문제를 만들었을 때 어떠한 방식으로 문제를 만들게 되었는지 써보겠다! 옛날에 만들어서 조금 까먹었을지도... 최신순으로 적어보자. 카이스트 가을대회이때 4문제 냈다. 각각 어떻게 풀었는지 적어보자.1. HLD이 문제는 Heavy Light Decomposition 이라는 알고리즘에 대해서 생각하다가 나온 문제이다. HLD는 트리를 여러 개의 체인으로 쪼개서 하나의 path 최대 2logN개의 체인으로 쪼개..
[10월] 분명 9월에 글 쓸 때는 1달보다 적은 간격으로 일기를 쓸 줄 알았다. 변명을 해보자면 시험기간이라서 여유롭지 못했다! snupc 검수와 카이스트 가을 대회도 있었고 ps도 못하고 그래서 안 썼다. 이제 써야지 후후 아래에 2023 snupc와 카이스트 가을대회에 대한 스포일러가 조금 있다. 주의! div1 코드포스를 말아먹고 시작한다. 왜 말아먹었냐 잠깐 설명을 하자면 1) B번에 케이스워크 문제가 나왔는데 이런 문제에 약하다. 2) C번에 쉬운 조합 문제가 나왔는데 1)로 인해서 시간도 없고 그냥 내가 구현을 잘 못해서 구현하다가 끝났다. 참고로 다음날 일어나서 코드 조금 고치니까 맞았다. 그 다음 코드포스에서 떡상했다. D번 문제는 그냥 정리할 것을 정리하면 풀리는 문제라서 D번 위치보다 쉬운 것 ..
2023 icpc 예선 후기 평소와 같은 팀(maruii, kimjihoon)과 함께 예선 대회에 참가했다. 본선에 진출하는 팀의 수는 예선에 참가하는 팀의 수와 비례하는데, 이번에 카이스트에 참가하는 팀이 늘어나서 예선은 안정적으로 통과할 수 있을 것이라고 생각했다. 풀리는 대로 풀겠다는 마음으로 예선에 임하게 되었다. 대회가 시작하고 문제를 보기 시작했다. ICPC 예선에는 쉬운 문제 3개가 한글로 되어있다는 경험을 지난 예선때 했기 때문에 이번 예선에서는 한글 문제 3개를 풀고 시작하기로 했다. C D G가 한글 문제였다. 가장 처음 읽은 문제가 G인데, 분모가 N 이하인 기약분수 중 K번째 분수를 출력하라는 문제였다. 예전에 검수하면서 페리 수열을 사용할 일이 있어서 분모가 N 이하인 모든 기약분수를 개수에 선형으로 정렬하는..
2023 RUN 가을대회 임시 에디토리얼 풀이를 아는 문제만 적었습니다. 정확하지 않을 수 있습니다. A: 길이 5의 path는 임의로 재정렬할 수 있다. 그리고 많은 경우에 정점 6개의 트리는 일자형 트리로 변환할 수 있다. 트리의 지름을 4로 만든 후에 다양한 변환을 거치면 된다. B: 1번째 원소는 i=1인 경우로만 변경할 수 있다. p[1]을 맞춘 후에 2번째 원소, 3번째 원소도 순차적으로 맞춰보자. C: 현재 R칸에 있다고 가정하자. 오른쪽 K개의 칸을 모두 탐색하지 않고 가장 가까이 있는 오른쪽의 R까지만 탐색해도 된다. TL이 빡세다. E: heavy edge가 바뀌는 횟수가 bound된다. 이유는 hld와 같은 원리로 설명 가능하다. hld와 lazy segment tree로 적용하면 (N+Q)log^2N에 풀린다. F: 1~i..
코드포스 레드 달성 요즘 대회를 조금씩 끝에서 말아먹어서 조금 꿀꿀했다. scpc에서는 3-2 섭태도 못 긁고 2번에서 cht 구현도 말아먹는가 하면 모비스에서는 양방향 간선 조건을 못 봐서 시간을 다 날려먹었다. 코포라도 잘 쳐서 레드를 달성하면 좋겠다 생각하고 요즘 코포를 치고 있는데... 어제 운이 좋게 Div 1+2 대회에서 42등을 하게 되었다. E번에서 막혔을 때 대충 E까지 풀던가 못 풀고 무난한 라운드일 줄 알았는데 어떻게 잘 찍어서 E번을 넘기고 F를 쉽게 풀어서 올랐다. 예전에 Codeton round 1에서 120점 정도 올랐는데 이번 라운드도 Codeton인 것을 보면 Codeton 라운드는 구현이 짧은게 나랑 잘 맞는 듯하다. 반대로 말하면 구현이 길면 대회를 잘 말아먹는 편... 암튼 누텔라 퍼포도..
[9월] 첫 ps 일기 남들이 블로그 쓰는 것 보고 나도 꿀잼ps한 기억들을 저장하고 싶다는 생각이 들었다. 최근 2주~1달 동안 푼 문제에 대한 감상평을 적을것이다. 스포가 많다. 대회 치면 맛있는거 준다길래 한 번 참여해보았다. 사실 아레나로도 칠 수 있지만 레이팅 걸려있는 것 넘나 무서운 것... E번까지 슥슥 밀고 슼보 봤는데 다들 G번을 풀었다. 자료구조 문제인데 상위 K개라서 dnc opt 어쩌구저쩌구 뇌절박다가 겨우 빠져나와서 셋질함... 근데 그와중에 구현 뇌절해서 대회 맛있게 말아먹은 듯ㅋㅋ 그래도 풀었으니까 후회는 없다~ 요즘 조이슥 맛있게 먹고 있는데 옆에서 IBory님이 이거 잡고 있길래 같이 풀었다. 첨에 보자마자 세그에 그래프를 머시기저시기 풀이 냈는데 사풀이었음... 그냥 열심히 dfs하는 문제라서 ..
CCO23 day1 CCO는 캐나다 국대 선발전으로 퀄리티가 좋고 다른 국대 선발전보다 덜 매워서 재미있게 돌기에 좋은 셋이다. 1. Binaria 문제 요약: 정수 $K$가 주어진다. 길이 $N$의 binary string의 SMS(sub-message sum)을 다음과 같이 정의하자. SMS는 길이 $N-K+1$의 수열이다. SMS의 $i$번째 값은 binary string의 $i$번째부터 $i+K-1$번째 문자의 합이다. $N$, $K$, 그리고 SMS가 주어졌을 때 가능한 binary string의 가짓수를 구하라. 가능한 binary string이 존재함이 보장된다. Full task (25 points) Binary string을 A, SMS를 B라고 하자. SMS가 우리에게 주는 정보는 다음과 같다. $1 \l..
2023 ucpc 본선 후기 UCPC 본선에 "김앤장" 팀으로 출전했다. 팀원들은 나, 김지훈(etyu), 장보규(maruii)이다. 요즘 열심히 CCO도 밀고 현대 모비스 대회도 쳐서 감이 나름 살아있다고 생각해서 ucpc 전에 특별히 ps 연습을 안 했다. 팀연습은 했어야 하나 싶기도 한데 평소에도 대회 전에 특별히 연습을 안해서 그냥 안 했다. 대회 전날에 일찍 자려고 노력했지만 체스를 두느라 새벽 5시에 자버렸다. 아침 8시 반에 일어났음에도 불구하고 컨디션이 괜찮았다. 평소에도 4시에 자서 그런 듯하다. ucpc는 문제 퀄리티가 항상 좋으니까 재미있는 문제 풀 생각에 신이 났다. 대회 장소에 도착하니까 평소에 온라인으로만 보던 사람들을 볼 수 있어서 좋았다. 잠깐 돌아다니다가 세팅을 시작했다. 대회 장소가 SK 판교 사옥이..

티스토리툴바