본문 바로가기

분류 전체보기

 (38)
ICPC 2021 Seoul Regional I번 Postman 문제 링크: https://www.acmicpc.net/problem/23573 23573번: Postman There is a straight road on which two types trams run. One is an east-to-west tram which moves from east to west, and the other is a west-to-east tram. For each type, several trams run regularly, so anyone can ride the tram in any direction at any time. To www.acmicpc.net $t=2$일 때 풀어보자. 시작점($x=0$)과 끝점이 정해진다. 각각 $s$, $e$라고 하자. 편의상 $s1$,..
[1, 2, 3월] 군대에 간 덕분에 시간이 남아돌았다. 남는 모든 시간을 ps에 쏟아부었더니 루비 5와 다이아 1을 엄청 풀게 되었다. 푼 문제도 많으니 기억나는 문제들만 간략하게 정리해보자. 아직 코딩을 한 문제도 안 했다. 경찰과 도둑은 SCPC 2022 2번에서 했던 이분탐색을 비슷하게 트리에서 하면 되는 것 같은데 D2가 박혔다. 들려오는 소문으로는 구현이 어려워서 그렇다고 하더라. 과일 게임의 토픽은 이미 usaco에서 99번 우려져서 난이도를 보기 전에는 쉬운 문제일 줄 알았는데 생각보다 안 풀려서 쩔쩔맸다. 평균 최대화는 적당한 비빔밥인 것 같다. 아직 코딩을 안해서 내 풀이가 맞는지 잘 모르겠다. 뚫기는 timeismoney와 같은 아이디어로 접근하면 쉽게 풀렸다. 몇몇 루비들은 풀이를 까는 것이 도움되는 ..
[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 이하인 모든 기약분수를 개수에 선형으로 정렬하는..

티스토리툴바