매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 핀볼 링크 결국 어떤 선분이 더 위에 있는지를 쉽게 안다면 그것부터 차례대로 봐주면 됩니다. 겉보기에는 매우 단순해 보여서 막 정렬 조건을 짜게 됩니다. 그러면 예제에서 무한 루프가 돕니다. 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를 복합적으로 고려..
예년 본선 후기가 별로 없길래 저라도 적어봅니다. 대회 전 https://heejayaa.tistory.com/165 올해는 제가 옥 선생님(utilforever)께 얻어먹었습니다 😋 등심? 스테이크, 리코타 치즈? 샐러드, 뇨끼를 먹었습니다. 뇨끼를 처음 먹어봤는데 쫄깃하고 맛있었습니다. 스테이크는 두툼하니 야무졌습니다. 잘 먹고 들어가서 끝까지 잘 버틸 수 있었던 것 같네요 :) 감사합니다! 한편, NYPC의 시간대를 부분집합으로 갖는 춘배컵이 BOJ에서 진행 중이었습니다. 저는 N. 고양이 리그 문제를 출제했습니다. xiaowuc1님이 퍼솔하는 걸 확인할 수 있었으나 뭔가 스코어보드 구경이 이제는 그닥 재밌지는 않네요. 역시 문제를 만들어내는 순간이 제일 즐거운 것 같습니다. 넥슨에 도착한 뒤 드디..
