본문 바로가기

분류 전체보기

 (36)
[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 판교 사옥이..
2023 ucpc 예선 후기 작년에는 대회를 많이 쳤는데 (ucpc, scpc, icpc, 모비스, 코드잼, RUN spring/fall contest, 등등) 올해에는 아직까지는 참가한 코딩대회가 별로 없었다(코드잼 멸망, RUN spring contest 출제, scpc 미뤄짐). 오랜만에 큰 대회를 하니까 신났다. ucpc 예선이라고 전날에 딱히 공부를 하지는 않았다. 전날에 플로우를 열심히 외웠던 모비스와는 ucpc는 내 취약분야인 문자열 / 기하 / 플로우 문제를 잘 안 내고 내더라도 안 풀어도 될만큼 어렵게 내기 때문에 걱정이 안 됐다. 그리고 만약 낸다고 하더라도 팀원들한테 던져주면 슥삭하고 풀어줄 수 있기 때문에 덜 걱정되었다. 나름 오랜만에 cp를 해서 그런지 대회 1시간 전에는 조금 긴장하기는 했다. 다른 팀들은 ..
2023 모비스 예선 후기 2022 모비스는 흥미로운 대회였다. 예선때는 채점이 안 되고, 본선 3번에서는 지문이 이상해서 답이 대충 이거겠지~ 하고 찍는 경우가 좀 있었다. 그리고 작년 모비스 대회는 테스트케이스별 점수 시스템이었다. yes no 문제에 답이 no인 테스트케이스를 절반 가량 넣어서 no를 출력하면 문제의 절반 점수를 받는 경우도 생겼다. 이렇듯이 2022 모비스가 흥미로운 대회였으니 이번 대회 역시 어떤 기행을 보여줄지 궁금했다. 이번 모비스 시험은 프로그래머스에서 진행한다. 예선 전날에 프로그래머스 사전 체험을 통해서 테스트 환경을 체험해보았다. 우선 코딩창이 너무 작았다. 한번에 대략 10줄 밖에 못 보는 것 같은데 for문 여러개를 중첩하면 헷갈릴 것 같았다. 대충 문제를 읽고 제출해보니까 정확성 영역이랑 ..
JOI 2023 final open contest 후기 어제 JOI 2023 final open contest를 쳤다. JOI 대회들은 항상 퀄리티가 높아서 재미있는 문제도 볼 겸 대회를 쳤다. 주의: 아래 후기에는 대회 스포일러가 있다. 타임라인 ~0:00 오랜만에 cms를 들어가니까 기분이 좋았다. 옛날에 cms로 싸이컴 입부 시험도 치고, 선발고사도 치고 했었는데 대학생이 되니까 cms를 한동안 접할 일이 없었던 것이다. cms는 모든 테스트케이스의 실행시간을 보여줘서 좋고 무엇보다도 초록색으로 100/100을 띄워줘서 기분이 좋다. 0:00~0:07 JOI는 항상 문제가 난이도 순으로 배치되어있기 때문에 1번부터 읽었다. 읽으니까 스택으로 슥삭슥삭하면 되는 것처럼 생긴 문제가 있어서 머릿속에 있는 사전지식으로 호다닥 풀었다. 1번에 100을 초록 글씨..
코드포스 라운드 개최 후기 우선 후기에 앞서서 대회가 진행될 수 있게 도와준 많은 분들에게 감사를 표하고 싶다. 코디네이터 Arpa와 head coordinator KAN이 대회 세팅을 정말 많이 도와줬다. YeongTree는 나랑 문제 출제하면서 같이 문제에 대해서 고민했다. (풀렸는데 아직 출제 안 된 문제도 있다!) tlsdydaud1님은 예전에 코드포스 라운드를 개최했던 사람으로서 여러 팁들과 피드백을 열심히 해주셨다. 테스터들은 (상당히 많아서 못 적겠다…) 문제의 난이도, 지문, TL/ML 세팅 등 문제를 예쁘게 만드는데 도와줬다. 처음에 코드포스 대회를 처음에 열 때에는 div1을 열고자 했다. 그래서 서울과고 친구들을 모두 모아서 문제들을 냈는데, div1E 문제를 못 내겠어서 포기했다. 그래서 그냥 혼자 생각나는 ..
백준 21607 polynomial and easy queries 문제 링크: https://www.acmicpc.net/problem/21607 21607번: Polynomial and Easy Queries 모든 3번 쿼리에 대해, 그 답을 한 줄에 하나씩 출력합니다. www.acmicpc.net 싸이컴 입부시험에 낼 킬러문제를 생각하다가 교환이 성립하는 두 가지 연산에 대해서 레이지를 사용하는 문제를 내면 어떨까 해서 만든 문제다. 거의 처음이자 마지막으로 내는 역추적으로 만들어진 문제가 아닐까 싶다. 풀이: $f(g(x))=g(f(x))$이다. 따라서 각 위치마다 $f$와 $g$를 몇 번 연산했는지만 알고 있으면 된다. 이는 레이지 세그먼트 트리로 관리할 수 있다. 이제 각 3번 쿼리에 대해서 위치마다 $f$와 $g$가 몇 번 연산되었는지를 $O(logN)$만에..

티스토리툴바