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

오랜만에 ARC를 쳤는데, 개인 최고 퍼포먼스를 내서 기쁜 마음에 풀이를 작성한다. 유의: 궁금하신 점은 댓글로 남겨주세요! Max Mod Min 요약: multiset에서 최소원으로 최대원에 modular를 취해주는 과정을 반복한다. 만약 0이 되면 multiset에서 빠지면 된다. 이 때 연산의 횟수를 구하면 된다. 풀이: modular 취하고 나면 최대원의 값이 최소원보다도 작아지므로 새로운 최소원이 된다. 이는 덱을 이용하면 구현할 수 있다. 시간 복잡도는 modular을 취할 때 항상 크기가 절반 미만으로 감소한다는 사실을 고려하면 $O(N\log \max A)$가 된다는 것을 알 수 있다. 더보기 한국 참가자들 중에 가장 늦게 제출해서 망했다고 생각했다. 10분 정도 걸렸나? 항상 보면 나는 ..

냠 수열과 쿼리 1 문제 링크 풀이 더보기 펜윅트리에서 각각이 구간을 정렬한 상태로 갖게 하면 된다. 거기에 이진탐색. 플3 날먹..!! AtCoder Beginner Contest 250 대회 링크 거의 한 5개월 만의 앳코더다. 그동안 코포 연습한게 있어서 민트 퍼포는 나오더라. Adjacent Squares 걍 Enlarged Checker Board 걍 Adjacent Swaps 걍 250-like Number $p\times q^3\le 10^{18}$ $p^4