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..
매일의 문제 풀이를 기록합니다. 여기서 문제 풀이란, 알고리즘 문제 해결을 의미합니다. 백준/코드포스/앳코더 등의 플랫폼을 이용합니다. 완성도가 높은 글이 아닙니다. 대신 생각의 흐름이 꽤 자세하게 적혀 있을 것 같네요. 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)으로 관리하면 다 커버가 되나? ..
예년 본선 후기가 별로 없길래 저라도 적어봅니다. 대회 전 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..
