문제 링크 질문은 언제나 환영입니다. 이 문제는 두 가지 풀이법이 존재합니다. 우선 대표적인 관찰을 확인하고 각 풀이로 전개해 보겠습니다. 편의상 주어진 배열은 $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$에 도달했을 때, 나머..

문제 링크 질문은 언제나 환영입니다. 3가지 풀이법이 나오네요. 글에는 없는 자신만의 풀이법이 존재하신다면 알려주세요! 두 가지 풀이법은 $O(n^3)$짜리 풀이이고, 한 가지 풀이법은 $O(n^2)$짜리입니다. 풀이 더보기 문제에서 구해야 하는 것은 조건을 만족하는 배치의 수입니다. 세세한 배치의 성질들에 대해 알아볼 방법은 떠오르지 않고, 작은 케이스부터 풀다 보면 패턴이 보이기 때문에 동적 계획법을 시도해볼 수 있습니다. 3차원 동적 계획법 $B(x,y,z):=x$개의 빌딩 중 왼쪽에서 $y$개, 오른쪽에서 $z$개만 보이는 경우의 수 위와 같이 정의하는 것은 아주 자연스럽습니다. 점화식을 도출할 때는 $B(x-1,\cdots )$와의 관계를 우선 생각 해봅시다. 새로 생긴 가장 긴 막대기를 어디다..

문제 링크 질문은 언제나 환영입니다. 풀이 더보기 딱히 발상이 어려운 문제라고 보기는 힘들다. 특별한 알고리즘이 있는 문제도 아니다. 그냥 열심히 풀면 풀리는 문제다. 중요한 관찰은 하나뿐이다. 동적계획법처럼 귀납적으로 무-팰린드롬을 확장시키려는 시도를 해야 한다. 이 때, 확장하는 경계로부터 2칸 정도만 고려해도 충분하다. 왜냐하면 길이가 4 이상인 팰린드롬은 이미 길이가 2 이상인 팰린드롬을 포함하고 있기 때문이다. 예를 들어, $2$와 무-팰린드롬인지 알고 있는 $432$를 이어 붙이는 상황에서는 $2432$를 확인할 필요가 없는 것이다. 왜냐하면 $43$이 애초에 팰린드롬이 아니기 때문이다. 따라서 $24$와 $243$을 확인하는 것으로 충분하다. 이 관찰을 통해서 풀이를 이끌어 낼 수 있다. 무..

지문 링크 / 문제 링크 더보기 이거 풀면서 lazy propagation를 짜는 방식도 바꿨다. 속도가 2배가량 향상되고, 훨씬 직관적으로 변했다. 풀이 더보기 dynamic segment tree + lazy propagation. UPD - 구조체 내부 포인터도 0으로 같이 초기화하지 않으면 컴파일 환경에 따라 UB가 발생할 수 있다! 무조건 다 초기화시키자. 그리고 인덱스로 음수가 들어갈 수 있는 경우 단순한 (s+e)/2는 예상한 대로 동작하지 않는다. 따라서 이 블로그에 있는 "코드 조각들" 글에 있는 floor 함수를 이용해서 나눗셈을 처리하자. #include using namespace std; using ii = pair; using ll = long long; #define rep(i..

문제 링크 플4치고 쉬운? 문제 풀이 더보기 2 3→2 4→3→2 5→2 6→4→3→2 7→2 8→3→2 9→2 10→3→2 주어진 수를 나누지 않는 최솟값 → 어떤 수보다 미만의 모든 수가 주어진 수를 나누게 하는 최솟값 따라서 $$|\{k|(2\nmid k)\}|\times (strength(2)+1)\\+\\ |\{k|(2\mid k)\wedge(3\nmid k)\}|\times (strength(3)+1)\\+\\ |\{k|(2\mid k)\wedge (3\mid k)\wedge (4\nmid k)\}|\times (strength(4)+1)\\+\\ \vdots$$ 를 구해주면 된다. $\mathrm{lcm}$ 단위로 커지기 때문에, 전처리할 $strength(k)$의 종류가 그리 많지 않다는 ..

문제 링크 이 문제를 풀기 전에 BOI의 굉장한 학생을 먼저 풀어보시는 것을 추천드립니다. 풀이 더보기 다익스트라로 $A$로부터의 거리, $B$로부터의 거리, $C$로부터의 거리를 구한 뒤, $A$로부터의 거리의 오름차순으로 $B$로부터의 거리를 좌표압축한 인덱스에 $C$로부터의 거리를 업데이트해주면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr c >> m; rep(i,1,m) { int x, y, z; cin >> x >> y >> z; adj[x].emplace_back(y,z); adj[y].emplace_back(x,z); } vector v(n); vector bs; ll da[N..