문제 링크질문은 언제나 환영입니다.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..

문제 링크 usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요... 풀 때 사진 참고하세요. 문제 번역 \(1\)부터 \(N\)까지 높이에 대한 내림차순으로 번호가 매겨진 \(N\)개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) \(M\)개의 운하는 서로 다른 마을을 단방향으로 연결합니다. \(i\)번째 운하(\(1\le i\le M\))은 높은 \(S_i\)에서 낮은 \(E_i\)로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다. 비버 Bitaro의 \(N\)명의 친구들은 \(N\)개의 마을에 살고 있습니다. Bitaro는 \(Q\)번의 파티를 열며, 친구들을 초대할 것입니다. \(j\)번째 파티에는 \(Y_j..

문제 링크 꾸준히 다이아를 풀고 있어서 기쁘다. Subtask: $N≤5\,000$ (40점) 더보기 단순히 $O(n^2)$ LIS를 돌리면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr > t[i].se.se; } sort(t+1,t+n+1); rep(i,1,n) { lis[i] = 1, cnt[i] = 1; rep(j,1,n-1) { if (t[j].se.fi < t[i].fi.fi and t[j].se.se < t[i].fi.se) { if (lis[i] < lis[j]+1) { lis[i] = lis[j]+1; cnt[i] = cnt[j]; } else if (lis[i] == lis..

문제 링크 예전 IOI라서 서브태스크가 없다. 플1... 까지는 아닌 것 같다. 풀이 더보기 겹치지 않는 두 직사각형을 선택한다는 조건을 잘 고민해보면, 수직선 하나를 두고 양쪽에서 선택한다는 의미가 된다. 그래서 아래의 색칠된 직사각형이 좌상단 영역에서 둘레가 최소가 되는 조건 만족 직사각형이라면, 저기 여러가지 나머지 직사각형들 중 최소가 되는 것과 함께 고려해주면 된다는 것을 알 수 있다. 따라서, $a(i,j):=(i,j)$를 우하단 점으로 하는 직사각형들 중 최소, $b(i,j)=i\le i',\, j\le j'$일 때, $(i',j')$을 좌상단 점으로 하는 직사각형들 중 최소로 잡고 $\min$ 2D 누적합을 진행해주면 된다. #include using namespace std; using ..