매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 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)으로 관리하면 다 커버가 되나? ..
예년 본선 후기가 별로 없길래 저라도 적어봅니다. 대회 전 https://heejayaa.tistory.com/165 올해는 제가 옥 선생님(utilforever)께 얻어먹었습니다 😋 등심? 스테이크, 리코타 치즈? 샐러드, 뇨끼를 먹었습니다. 뇨끼를 처음 먹어봤는데 쫄깃하고 맛있었습니다. 스테이크는 두툼하니 야무졌습니다. 잘 먹고 들어가서 끝까지 잘 버틸 수 있었던 것 같네요 :) 감사합니다! 한편, NYPC의 시간대를 부분집합으로 갖는 춘배컵이 BOJ에서 진행 중이었습니다. 저는 N. 고양이 리그 문제를 출제했습니다. xiaowuc1님이 퍼솔하는 걸 확인할 수 있었으나 뭔가 스코어보드 구경이 이제는 그닥 재밌지는 않네요. 역시 문제를 만들어내는 순간이 제일 즐거운 것 같습니다. 넥슨에 도착한 뒤 드디..
문제 링크 고수들한테 교육적인 문제라고 생각한다. 부분문제 1 $W_i =0$ $(1 \le i \le N)$ 더보기 도달 불가능한 경우를 걸러내자. $H_{i-1} < D_{i}-D_{i-1}$이라면 $i-1$번 기둥에서 $i$번 기둥으로 이동하는 것이 불가능하다. 바닥에 닿기 때문이다. 그런 $i$가 존재하지 않는다면, 항상 $n$번 기둥까지 도달 가능하다. 걸러냈으니, 이제 문제에서 도달 가능함을 전제하고 풀이해 나갈 수 있다. 부분문제 4 $N \le 500$ $H_i \le 500$ $(1 \le i \le N)$ 더보기 $\mathrm{dp}(i,j):=i$번 기둥의 높이 $j$ 부분까지 이동하는데 걸리는 최소 시간 naive하게 다음과 같은 직관적인 점화식을 짤 수 있다. $\displays..
후기 보류 끝! 운영사무국의 지침에 따라, 풀이는 본선 이후에 정리하여 올리도록 하겠습니다. 더보기 운이 좋게도 NYPC Round 2-B에서 400점을 받고 본선에 진출했습니다. Round 2-A 후 기존의 전략에 반성 보통 저는 플래티넘 4 이하를 '쉽다'고 여깁니다. 그리고 플래티넘 3 ~ 2는 보통 '적당하다'고 여깁니다. 플래티넘 1 ~ 다이아 4는 유형이 나랑 잘 맞는다는 전제 하에 '해볼 만 하다'고 여기고, 그 위는 '부분 점수나 성실하게 긁어보자'는 마인드입니다. 따라서 저는 KOI 2023 2차와 Round 2-A에 '1, 2번 풀고 3, 4번 많이 긁는 전략'을 적용했습니다. Round 2-A 1, 2번은 40분 안에 풀어서 2번 난이도를 감안했을 때 뇌절 없이 잘 풀었다고 판단했습니..
대회 문제들은 여기서 확인하실 수 있습니다. 문제별로 제가 기여한 것들과 짧은 후기를 정리해보겠습니다. 전체적인 제안 검수를 딱 하려고 보니까 문제별로 tests가 150개를 넘어가던 걸로 기억합니다. 가뜩이나 Arena가 적용되어서 참가자 수가 많아질 것 같은데 tests가 이대로 많으면 안 될 것 같다고 줄여달라고 제안을 드렸습니다. 좀 늦게 제안했는데, 왜 그 전까지는 아무도 말을 안 꺼냈는지는 잘 모르겠네요.. 😅 또, 그래프 문제들의 조건에서 "$1\le i , j\le N$인 모든 $i$, $j$에 대해서 $i$번 구역에서 $j$번 구역으로 가능 경로가 항상 존재"를 " $1 \le i < j \le N$인 모든 $i$, $j$에 대해서 $i$번 구역과 $j$번 구역을 연결하는 경로가 존재"로..
