문제 링크 문제 요약 prefix와 suffix를 잡는데, prefix length + suffix length s) return true; Mp = max(Mp,p[i]); } return false; } int main() ..

문제 링크 적당히 타격감있는 기댓값 DP 문제다. divide by zero 예외를 놓치면 틀릴 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define all(x) begin(x), end(x) #define siz(x) int((x).size()) #define Mup(x,y) x = max(x,y) #define mup(x,y) x = min(x,y) #define fi first #define se second #define dbg(...) fprintf(stderr,__VA_ARGS__) using ld = lon..

문제 링크 백설공주와 난쟁이와 비슷한 것도 같다. 물론 안 풀어봤다. 아무튼 이 문제는 랜덤 알고리즘으로 푸는 문제이다. 처음 접하는 컨셉이라 신선하고 좋다. 문제 요약 길이 $N$의 정수 sequence $A$가 주어진다. 이 때 $A$의 각 원소는 distinct하다. 자연수 $M\in [3,10^9]$을 골라 모든 $A_i$에 대해 $\mathrm{mod\ } M$을 취해줬을 때, $A$의 majority가 존재하게 하는 $M$을 찾아라. 제한 $1\le N\le 5\ 000$ $1\le A_i\le 10^9$ 문제 풀이 Monte Carlo algorithm은 적당한 시간 내에 동작하지만, 확률적으로 정답을 구하지 못할 수 있는 알고리즘을 말한다. 시간이 충분히 빠르다면 여러 번 수행함으로서 정답..

문제 링크 으... 어려워... 여태 풀었던 앳코더 문제들 중에 레이팅이 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}..

문제 링크 질문은 언제나 환영입니다. 이 문제는 두 가지 풀이법이 존재합니다. 우선 대표적인 관찰을 확인하고 각 풀이로 전개해 보겠습니다. 편의상 주어진 배열은 $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의 원리를 이해했다. 이것으로 이산 로그를 구할 수 있다..

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 지그재그의 조건을 생각해보자. 지그재그는 인접합 2~3개 정도의 원소만 보면 된다. 지그 다음에는 재그 그 다음에는 지그... 따라서 지그 또는 재그의 상태끼리 다 묶어서 관리하면 계산량이 $10^{500}$ 가까이에서 훅 줄어서 reasonable해 질 것이다. 그리고 지그와 재그를 표현함에 있어서 그 자리의 숫자들도 당연히 관리해야 할 것이다. 지그/재그 상태와 자리 숫자가 같아도 몇 자릿수인지에 따라 달라질 것이다. 그래서 자릿수도 관리하고... $M$의 배수라고 하니까, 좀 고민하다가 보면 $M$으로 나눈 나머지를 잘 써주면 좋겠다 싶은데, 이 정보도 함께 관리하면 되겠다. $U(i,j,k):=i$자리에서 증가세로 숫자 $j$에 도달했을 때, 나머..