dong_gas

추하게 본선? Hello BOJ에 가게 되었다. 컷이 4솔이었다. A. 그냥 하란대로 구현했다. B. 잘 안보여서 C부터 풀고 다시 와서 풀었다. 난 이게 왜 골드5인지 아직 잘 모르겠다... 실버 기여도 많던데 ㅠㅠ C. 읽으면서 풀이가 보여서 바로 짰다. 위상정렬로 풀었다. N이 3000밖에 안되어서 별 생각없이 짜서 냈다가 시간초과를 받았다. O(N^3)풀이었다. 뭐 그냥 아주 쉽게 O(N^2)으로 바꿀 수 있었기에 한 2분 안에 다시 제출해서 맞았다. D. 이 문제가 참 어려웠다. 읽자마자 파라메트릭으로 풀어야 할 것 같이 생겨서 그렇게 풀려고 노력했다. 근데 판정하는 것을 한참동안 감도 잡지 못했었다. 그러다가 뒤늦게 X의 범위를 발견하고 점점 풀이를 구체화할 수 있었다. BFS도는 풀이를 짰는..

읽는 사람이 순열 사이클 분할(이하 순싸분)이 뭔지에 대해서는 안다는 가정 하에 글을 작성한다. '순열 사이클 분할'이라는 키워드로 검색하면 순싸분이 무엇인지 쉽게 알 수 있을 것이다. Codeforces에 순싸분이 자주 나오는 것 같다. 예전부터 순싸분이 나오면 탈탈 털렸었다... 근데 뭐 순싸분 자체가 어려운 개념은 아니니까... 가만히 있었는데 며칠 전에 또 털렸다. https://codeforces.com/contest/1768/problem/D 이 문제인데, 본 대회에서 80분동안 못풀었다.... 본 대회때 고민 + 오늘 다시 업솔빙하다가 알게 된 성질에 대해 한 번 정리를 해보려고 한다. 이를 대충 아시는 분들은 글을 읽을 필요없이 맨 아래의 결론과 생각이 일치했는지만 비교해보면 좋을 것 같다..

후기 글이 길어져 여러 편으로 나누어 작성할 것 같습니다. (상) - 대회 준비 과정 (중) - 출제 및 검수 과정 (하) - 미정 2022 Sogang Programming Contest가 성공적으로 마무리되었습니다. 제가 올 한 해 가장 열심히 준비했던 대회입니다. 특히 대회 직전 2주 간은 올 한 해가 아니라 평생 가장 열심히 살았던 2주가 아닐까 싶습니다. raararaara 선배의 2020 Sogang Programming Contest 개최 후기를 참고하여 작성하였습니다. 후기가 참 맛있으니 시간이 된다면 한 번 읽어보시길.. 감사하게도 저 말고도 다양한 분들이 이번 대회 후기를 작성해 주셨습니다. 운영진 입장에서 이런 후기글은 참 고마운 것 같습니다. Master 1등 후기 - shandy5..

ICPC가 끝났다. 예선 18위, 본선 20위다. 수상컷은 8솔이었다. 무섭다. 뭐 풀이는 koosaga님 같은 :god:들의 블로그를 보면 되기 때문에 딱히 적지 않겠다. 뭐 딱히 적을 문제도 없고... 오래되어서 기억도 안 난다. 대회 후기를 쓰려 했지만, 내 시점에서 쓰고 싶은 얘기가 딱히 없다. 별로 한 게 없기 때문. ICPC는 굉장히 어렵고, 잘하는 사람들이 굉장히 많다는 걸 느끼고 왔다. 그냥 뭐 팀 얘기나 미래에 대한 얘기나 써보자. DPS 6월 즈음에 학회 Slack에 semteo04선배가 팀원 한 명을 구한다고 올리셨다. 나는 그 당시 팀이 없었기 때문에 바로 DM을 보냈고, 뭐 며칠 뒤에 팀이 되었다. 솔직히 semteo04가 팀원 구한다는데 어케 참음 ㅎ; 근데 뭐 그 당시에 학회에..

https://codeforces.com/contest/1754/problem/B https://www.acmicpc.net/problem/25184 내가 만든 문제랑 매우 유사한 문제가 코포에 나와서 신기해서...ㅋㅋㅋ 풀이 코드도 동일하다 예제도 나랑 똑같이 만들어져 있다 ㅋㅋ 기념용 뻘글

후기를 쓰려고 했는데, 벌써 예선이 끝난지 일주일이 되었다... 교내 대회 준비와 과제에 치여 후기글을 쓸 겨를이 없었다. 정수론 과제를 하다가 하기가 싫어진 김에 간단하게 글을 써본다. 먼저, 이번 예선은 부득이하게 2인 팀으로 참가하게 되었다. 우리 팀은 매주 목요일 팀연습을 했었다. 대회 이틀 전 목요일에도 팀연습을 하기로 했었는데, 갑자기 Picasso 선배가 코로나에 걸렸다고 하셨다. 그래서 팀연습 못하겠네...라는 생각을 했는데 생각해보니까 대회도 못나갈 상황이었다. 바로 대회 본부에 문의 넣어서 2인팀으로 참가가능하냐고 물어봤더니, 가능하다하셔서 semteo04선배와 나 둘이서 참가하게 되었다....ㅋㅋ 본선에 못갈까봐 많이 무서웠는데 다행히 좋은 결과를 받았다. 운이 좋게도 전체 18위, ..

최근 대회(SUAPC)에서 SA, LCP를 몰라서 2등 했다. 그래서 Suffix Array와 Longest Common Prefix를 공부하였다. 삼소멤의 Suffix Array and LCP Array 글을 보며 공부했다. 공부하다가 알았는데 gumgood님 글이더라 ㄷ! 뭔가 반가웠다 ㅋㅋ 13264 접미사 배열 2 suffix array를 구해보자. 9248 Suffix Array suffix array와 lcp를 구해보자. 1786 찾기 KMP기본문제로 유명한 문제인데, 어디선가 SA로 풀 수 있다고 해서 SA로 풀어보았다. 문자열 S에 문자열 T가 몇 번 나타나는지, 그 위치는 어디인지 찾으면 된다. 더보기 부분문자열은 접미사의 접두사임을 생각하면 풀이를 떠올릴 수 있다. SA에 접미사가 정렬..

간만에 쓰는 코포 글 요즘 코포가 좀 이상했다... 맨날 말려서 C도 못 풀고... 끝나고 보면 왜 못풀었지라는 생각이 드는 문제들밖에 없었다. 블루 아이디가 2개라 그런지 간절함도 없었고... 그냥 안 풀리니까 하기 싫고. 하기 싫으니까 더 안 풀리고 뭐 반복이었던 것 같다. 많이 억울했다 ㅠ div3 날먹으로 일단 다시 블루 복귀는 성공했다... A. 그냥 브론즈 5 구현 B. 10보다 큰 것만 뒤에 0이 붙는다. 즉, 0이 나오면 0 앞 두 개가 알파벳을 나타내는 숫자이다. 이를 잘 구현하면 된다. 뒤에서부터 보면 편하다. C. 최소 비용으로 가려면 시작과 끝 사이 알파벳으로만 움직여야 한다. 또, 최대한 많이 밟아야 하니까 그 사이 알파벳들은 다 밟는 게 이득이다. 구현실수로 패널티를 쌓았다. 1..

이번 방학에도 어김없이 SUAPC에 참가하였다. 문제는 (여기)에서 확인할 수 있고, 에디토리얼은 아직 올라오지 않은 것 같다. ICPC에 같이 나가기로 한 팀원들과 나갔다. 우리 팀은 dong_gas, semteo04, Picasso로 이루어져 있다. 여름방학 전에 두 분께서 팀원 구한다고 학회 슬랙에 올리셨었는데, 둘 다 나보다 잘하시니까 재빨리 DM을 보내서 합류했다 ㅎㅎ; 당시에 팀이 없기도 했었고... 팀 명은 대충 앞글자를 따서 DSP로 지었는데 스코어보드 보니까 좀 구린 것 같다. 재미도 없고... ㅋㅋ 기회가 되면 ICPC는 바꿔서 나가자고 해볼 생각이다. 우리 팀은 2위로 대회를 마무리 하였다. 상금 50만 원과 현대에서 주는 상품(?)을 받는다. 뭐 사실 대회 나가기 전부터 다른 강한 ..

오랜만에 문제풀이 글 지난 주, 학회 연습셋에 쓸 문제가 마땅치 않아 USACO 문제를 두 개 넣었었고, 그 중 하나이다. 나는 이 문제가 굉장히 까다롭다고 생각했다. 그리고 풀이 세션할 때 질문이 많이 들어올 줄 알고, 연습셋 때 풀이를 열심히 준비했었다. 근데, 다들 잘 풀더라... 질문도 없었다. 아쉬워서 글로 남겨본다. boj.kr/24979 문제를 요약하면 다음과 같다. C는 OW 혹은 WO로 바꿀 수 있다. O는 CW 혹은 WC로 바꿀 수 있다. W는 CO 혹은 OC로 바꿀 수 있다. 인접한 두 문자가 같으면 두 문자를 삭제할 수 있다. 이제 쿼리 [l, r]이 들어온다. 구간 [l, r]에 위 연산을 원하는만큼 적용해서 s[l..r]을 "C"로 만들 수 있는지 묻는 문제이다. 코드포스 같은 ..