코드마스터 2023 이후로 세 문제를 출제하였다. 때는 작년 여름 방학. 정시로 늦은 탑승을 하는 것은 승산이 적다고 판단했던 시기. 특기자에 한 줄이라도 더 적을 거 만들자는 생각으로 (사실 함수컵 검수하다가 뽐뿌가 와서.. 그냥 출제가 하고 싶었다) 문제 구상을 시작했다. Sieve Game, 고양이 리그, 신촌방위본부: 지하 벙커의 비밀, 요 세 문제가 그 때 만들어졌다. 당시에 한 일주일간 한적한 카페에 가서 이것저것 생각나는대로 만들어보다가 집에 오는 걸 반복했다. 신촌방위본부: 지하 벙커의 비밀은 SNUPC Call for Tasks에 던졌다가 반려되었고, 이번 SUAPC 2024w Call for Tasks에서 간택되었다. 선발고사 & 함수컵에 출제된 투스텝을 보고 투스텝에 대한 관심이 많이..
unordered_map의 템플릿 인자에 직접 정의한 해시 함수를 넣어서 [핵 피하기] or [원하는 자료형을 key로 사용하기] 를 할 수 있습니다. key의 자료형을 바꾸자 20940번: Pingvin 문제를 깔끔하게 풀고 싶은 마음에 이상한 짓을 했습니다. 다음 코드는 Pingvin 문제에서 456ms로 AC를 받은 코드입니다. 상수 최적화 없이는 TLE가 나기 쉬우므로 주의하세요. 더보기 #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #define rep(i,a,b) for (auto i = (a); i n; rep(i,0,2) cin >> S[i]; rep(i..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 핀볼 링크 결국 어떤 선분이 더 위에 있는지를 쉽게 안다면 그것부터 차례대로 봐주면 됩니다. 겉보기에는 매우 단순해 보여서 막 정렬 조건을 짜게 됩니다. 그러면 예제에서 무한 루프가 돕니다. Strict Weak Ordering을 만족하지 않기 때문입니다. SWO에는 한 4가지 조건이 있는데 그중 '비비교성의 추이성'에서 문제가 생깁니다. 따져보면, 비교 가능한 관계를 $\sim$이라고 할 때, $(3)\not \sim (1)$이고 $(3)\not \sim (2)$인데, $(1)\sim..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 며칠간 푼 문제 중에서 기억나는 문제는 두 개 밖에 없네요. 그래서 따로 안 적었습니다. 30878번: 약속 시간 기하적 확률로 접근하는 문제입니다. 중학교 때 수학 동아리에서 비슷한 문제를 어떤 선배가 발표했던 기억이 나는데, 그때는 적분을 몰라서 대충 이해 못하고 넘어갔던 걸로 기억합니다. 유명한 문제 중에는 뷔퐁의 바늘 문제였나? 그런 고전 수학 퍼즐들이 있는데 찾아보면 좋을 것 같습니다. 저는 그래프 그리고 적분해서 어케 식을 냈는데, 안 맞길래 상수를 좀 고치니까 나와서 믿음의..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Suffix array 기본 문제 몇 개랑 상어의 저녁식사 풀었습니다. 딱히 어려운 부분은 없었습니다. Prefix와 Suffix 링크 일단 해싱으로 pfx=sfx들을 효율적으로 구할 수 있고, 이것들이 몇 번 등장하는지를 suffix array를 갖고 구할 수 있지 않을까 하는 생각이 듭니다. LCP 배열에서 RMQ를 돌리면..! 어떤 패턴이 몇 번 등장하는지를 손쉽게 확인할 수 있겠다는 신선한 생각이 들었습니다. 해보겠습니다..! 구현량에 걸맞지 않게 한 번에 예제가 나왔습니다. 제..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Special Numbers 링크 mirror 팀에서 cozyyg님의 디버깅 도움으로 AC를 볼 수 있었던 문제입니다. 당시 코드가 굉장히 난잡했어서 깔끔하게 다시 풀어볼 생각입니다. 어제(2023.11.28 - [PS 기록들] - Daily PS Comments #1) 풀었던 문제는 "자릿수 곱이 K 이하인 수의 개수"였고, 이 문제는 "자릿수 곱이 K의 배수인 수의 개수"입니다. 비슷하게 풀어보겠습니다. ㅋㅋㅋㅋ xiaowuc1님이 G1 주신 이유를 알겠네요 이제.. 어제 그 문제랑..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. Digit Products 링크 digit DP이긴 할텐데 곱을 직접 관리하기에는 $10^9$까지 커질 수 있으므로 무리가 있다 음.. 그냥 곱을 unordered_map의 인자로 관리하면 그건 되지 않을까? 어차피 소인수 분해 하고나면 대충 (2지수)×(3지수)×(5지수)×(7지수)만큼만 나오니까.. (3×18)×(2×18)×(18)×(18)의 상한을 갖는다 $6\times 18^4$면 꽤 합리적인 크기이다. 그럼 dp(자릿수 인덱스, 곱, tight)으로 관리하면 다 커버가 되나? ..
링크 문제를 요약하겠습니다. 사분원 둘레 $n$개가 주어집니다. 이들을 잘 돌리고 조합하여 하나의 폐회로를 완성해야 합니다. 단, 두 개의 사분원 둘레가 만나는 부분은 부드럽게 이어져야 합니다. $4\le n\le 100;$ $1\le r\le 10\,000$ Yes / No로 답해주세요. 접근 1 naïve한 여러 방법들이 떠오릅니다 방향 고정 등으로 중복을 획기적으로 줄일 수 있을까요? → 그다지.. DP가 계속 맴도는데.. 좌우상하 DP로 점화식을 세워 볼까요? → 역시나 역부족.. 필요한 알짜 x, 알짜 y를 상태에 포함? → 결국 좀 애매합니다.. 이동 범위를 확인할 수 있을까요? → 딱히 연속적이지 않아서 무의미해 보입니다.. 다만.. 45도로 돌려볼 수 있을까요? → x,y를 복합적으로 고려..
