문제 링크 으... 어려워... 여태 풀었던 앳코더 문제들 중에 레이팅이 kenkooo 기준으로 제일 높다. (거의 꽉 찬 옐로우) 내가 보기에는 다이아도 줄 만한 것 같다. 발상이 너무 어렵다... 짜증나는 점이 하나 있는데, ABC 공식 풀이가 뭐가 많이 부족하다는 것이다. 잘못된 점도 많고 설명도 친절하지 않다. 문제 요약 웹 페이지에 웹 카운터는 접속 횟수를 측정한다. $i=0,1,2,\ldots,23$에 대해서, 매일 $i$시마다 다음의 접속 가능성이 존재한다. 만약 $c_i=$'T'라면 철수는 $X$%의 확률로 웹 페이지에 접속한다. 만약 $c_i=$'A'라면 영희는 $Y$%의 확률로 웹 페이지에 접속한다. $N$번째 접속이 영희에 의한 것일 확률을 $\mathrm{mod }\ 99824435..

문제 링크 Suffix array를 이용하여 "문자열 $S$의 회전 $\le$ 문자열 $T$의 회전"을 만족하는 쌍의 개수를 세는 문제이다. (단, $N=|S|=|T|$) 회전(rotate)을 관리할 때는 원래 문자열을 두 번 연속해서 붙여주는 것이 경험적으로 유용하다. 왜냐하면 붙여 만든 새 문자열의 길이가 $N$인 각 부분 문자열들이 원래 문자열의 회전이기 때문이다. 붙여서 관리하겠다는 것까지는 알겠다. 이제는 효율적으로 $S$의 회전들과 $T$의 회전들을 비교해야 한다. $S$의 회전마다 $T$의 SA에다가 이진 탐색으로 패턴 매칭을 시켜주는 것은 어떨까? 괜찮은 생각이지만 아직은 제한에 못 미친다. $S$와 $T$를 전부 때려넣고 SA를 돌릴 수는 없을까? 이게 핵심이다. $\color {red}..

좋다. 여우 신탁 오랫동안 고민한 뒤에야 맞췄다. 다양한 관찰과 접근을 시도했지만 전부 애매했다. sparse table을 이용하고 싶다는 생각도 했는데, 매번 함수가 다르기 때문에 무용지물이었다. 거꾸로 마지막 나머지들로부터 추적을 해볼까 하는 생각도 했는데, 크게 달라지는 점은 없었다. 기댓값의 선형성을 적극적으로 이용할 수 있는가도 고민해봤는데, 티어 상 그럴 것 같지도 않았고 써먹기 좋은 상황이 없었다. 사실 초반에 제수가 감소한다는 관찰을 했었는데, 이를 다시 생각해보니 쓸 만했다. 뭔가 로그 시간으로의 단축을 원했던지라 효과가 없다고 넘겼었는데, 분할 상환적으로 봤을 때 효과적이었다. 결국 풀이는 제수가 감소하는 만큼만 새 나머지로 이동시켜주면 되는 것이었다. 그러면 시간 복잡도가 분할 상환적..

교수님은 기다리지 않는다 문제 링크 쉽다. DSU를 잘 변형해서 풀면 된다. 'JOI 국가의 행사'를 풀어본게 도움이 된 것 같다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i size(b)) swap(a,b), w = -w; // b에다가 a 붙여버리고 a의 값들 전부 apply for (int x : sub[a]) val[x] += w, sub[b].push_back(x); sub[a].clear(); par[a] = b; return true; } bool same(int a, int b) { return find(a) == find(b); }..

문제 링크 질문은 언제나 환영입니다. 이 문제는 두 가지 풀이법이 존재합니다. 우선 대표적인 관찰을 확인하고 각 풀이로 전개해 보겠습니다. 편의상 주어진 배열은 $A$라고 합시다. 관찰. max와 단조성 min의 단조성 배열의 임의의 위치 $k$에 대해 $\max A[i\cdots k]$는 $i$에 대해 단조 감소를 띱니다. 왜냐하면 $i_1

문제 링크 버추얼을 돌면서 만난 문제이다. 처음에는 함수형 그래프에서 사이클을 다루는 알고리즘 floyd cycle finding을 떠올렸는데, 이내 입력을 보아하니 안 될 것 같아서 접고 수식을 정리해봤다. $G=A^nS+B\cdot \frac {A^n-1}{A-1}$이 나왔는데, $n$을 결정하는 것이 난관이였다. 식을 $n$에 대해서 정리하고 이산 로그로 구할 수 있을까라는 생각을 했고, 딱히 발전이 없던 차에 시간이 끝났다. 알고 보니 이산 로그도 풀이가 될 수 있고, 혹은 baby-step giant-step이라는 알고리즘을 사용할 수도 있었다. 사실 이산 로그를 구할 때 이 알고리즘이 들어간다. 아무튼 baby step giant step의 원리를 이해했다. 이것으로 이산 로그를 구할 수 있다..

카카오 코딩 테스트 풀이를 작성했다. 마지막 문제 빼고는 전반적으로 내가 들었던 예전 카카오 난이도보다 낮은 것 같았다. 마지막 문제는 그래도 골드 상위는 될 것 같았다. 아니면 플래 하위까지도 가능할지도 모르겠다. 암튼... 작성하기 귀찮다. 골드 6문제 세트를 200분으로 잡고 돌았다. 35분 남기고 전부 풀어서 다행이다. 사실 점점 시간이 늦어져서 마지막 두 문제는 졸면서 푼 것 같다. 벽 부수고 이동하기 단순히 BFS 두 번 돌리고 고려하면 된다. 17분 정도 걸렸다. 더보기 #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i x or x > n or 1 ..

KAKAO BLIND RECRUITMENT는 문제의 지문 / 테스트케이스 / 풀이를 비상업적, 비영리적 용도로 게시할 수 있다. 광고가 노출되지 않는 블로그에 문제 풀이를 게시하는 것은 비상업적, 비영리적 용도이다. 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges 2022년 09월 24일 14:00 ~ 09월 24일 19:00동안 테스트가 진행되었습니다. 이 글에 나와있는 문제 제목들은 실제 제목이 없어서, 제가 문제가 요구하는 요점에 맞춰 지은 제목입니다. 질문은 언제나 환영입니다. 그... 좀 귀찮아서 마지막 두 문제만 풀었습니다. UPD - 마지막 두 개만 풀었는데도 통과했네요.. 미로 탈출(300점) 예상 난이도: 골..