본문 바로가기

분류 전체보기

 (36)
[12월] 사실 시험기간이라서 ps를 조금 쉬었다. 매일매일 하던 게임도 한달간 안 했으니 ps 정도는 쉬어도 되는거로 하지만 시험기간이 끝나고 심심해서 ps를 조금 했다. 푼 문제들을 알아보자. 난이도가 쉬운 대회면 검수가 쉬울 줄 알았다. 하지만 난이도가 낮은 만큼 뽑는 검수 인원도 줄어들어서 검수날먹을 할 수 없었다. 모든 검수진이 모든 문제를 검수했다! I번의 풀이를 새로 만들었다! 원래 문제가 조금 잘못된 면이 있어서 고쳐서 예쁜 문제로 만들었다. 다이아쯤 찍힐 줄 알았는데 내가 풀 때 문제 조건과 현재 문제 조건이 달라서 티어가 조금 내려간 것 같다. 그리고 뚫리기도 했다. 1달간 ps를 쉬고 재활겸 유사코 골드 한 셋 풀었다. 모든 문제가 생각보다 쉽게 풀렸다. Strongest Friendship G..
2023 icpc 본선 후기 I를 잡고 호다닥 짜서 맞았다. J가 스코어보드에서 풀리길래 팀원에게 풀어보라고 넘기려고 했는데 문제 설명해주다가 풀이가 떠올라서 짰다. 그리고 2시간 반동안 맞왜틀을 했다. 맞왜틀하면서 코드를 간결하게 하기 위해서 110줄의 코드를 80줄의 코드로 줄였다. 줄이는 과정에서 혹시 모르기 때문에 계속 제출을 했고, 8틀을 적립했다. K가 11 이상의 소인수를 가질 때에 답이 0이 아니라는 것을 너무 늦게 깨달았다. 맞고 나니까 시간이 30분 남았다. 올해 대회장에서 맞왜틀하는 경우가 너무 많다.그래도 맞왜틀하는 동안 팀원들이 문제를 잘 밀어줘서 덕분에 풀 문제들은 다 푼 것 같다. 팀원들 고마워요~ 시간이 좀 남았으면 C, K, L 보는 거였는데 아쉽다.
[11월] 일본 문제들 덕분에 조금이나마 ps를 하고 사는 것 같다... 무슨 문제를 풀었는지 알아보자. 쉽지 않다. P2이고 OI 문제인데 꽤 시간이 오래 걸렸다. 3차원 뇌가 안 돌아가나보다. 예전에 stock prediction이라는 icpc 문제도 못 풀었는데, 3차원에 약하다. 아마 3차원 문제라면 스위핑을 사용할 것이라고 생각했기 때문에 오래 걸리지 않았나 싶다. 이 문제에 대해서 한 가지 더 말할 것이 있는데, 자료구조 근육으로도 풀린다. 나 역시 약간의 자료구조 근육으로 이상하게 돌아가서 풀었다. 역시 근육은 있으면 좋은 것 같다... 내가 출제한 문제인 HLD랑 같은 아이디어를 사용한다. 날먹했다. 쉽지 않다. 풀이 떠올리기는 나름 쉬운데, 구현을 조금 돌아가서 했기 때문에 TL이 좀 빡빡했다. 직..
문제 출제하기 오늘은 여태까지 출제한 문제들에 대해서 문제 출제 과정을 알아볼 것이다. 고등학생 때 플래티넘 열심히 풀던 시절에 문제를 만들고 싶었지만 문제를 하나도 만들지 못했던 과거의 나를 생각해보면 처음 문제 만드는 것이 가장 어려운 것 같다. 그래서 문제를 처음 만드는 사람들에게 조금이나마 도움이 되고자 내가 문제를 만들었을 때 어떠한 방식으로 문제를 만들게 되었는지 써보겠다! 옛날에 만들어서 조금 까먹었을지도... 최신순으로 적어보자. 카이스트 가을대회이때 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 라운드는 구현이 짧은게 나랑 잘 맞는 듯하다. 반대로 말하면 구현이 길면 대회를 잘 말아먹는 편... 암튼 누텔라 퍼포도..

티스토리툴바