문제 링크 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 ..
문제 링크 Subtask: $M = 2, 3 ≤ N ≤ 10\,000$ (14점) 더보기 어차피 부분행렬 속 각 열 속의 등수가 전부 같은 것이 조건이므로, 행렬의 각 열의 순서는 바뀌어도 상관이 없다. 따라서 각 열을 첫번째 행의 크기 순서대로 정렬하는 것이 가능한데, 이러면 LIS 문제로 환원되어 쉽게 풀 수 있다. $O(n^2)$으로도 가능한데, $O(n\log n)$으로 풀어 Subtask #3와 함께 긁었다. Subtask: $M = 3, 3 ≤ N ≤ 10\,000$ (9점) 더보기 $O(n\log n)$의 LIS는 적용할 수 없다. 따라서 $O(n^2)$ LIS를 사용하여 풀 수 있다. 코드 Subtask: $M = 2, 3 ≤ N ≤ 2\cdot 10^5$ (15점) 더보기 세그트리를 이용..
문제 링크 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: $N ≤ 3\ 000, Q ≤ 3\ 000$ (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 $ ≤ 10^5, Z_j =0$ (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자료구조들이 있을 것이다. 그렇게 다음의 3가지 풀이가 있다: Merge sort tr..
문제 링크 재밌는 트리 DP 문제였다. 편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자. Subtask: $V_i > 0$ (17점) 더보기 그냥 최대한 많이 포함하면 이득이다. 그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다. 또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다. 필자의 코드이다. Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점) 더보기 직선형 그래프에서 문제를 풀면 된다. Kadane 알고리즘과 꽤 비슷하다. 각 노드 $i$마다 $\sum_{i\le k\le j}V..
1시간 차에 3번 풀고 2시간 차에 1번이랑 2번 섭태 풀었다. 3시간 반 차까지 2번 풀태를 고민했지만 별 진전이 없어서 승급 컷도 넘겼겠다, 버리고 튀었다. 2시간 만에 2.5문제 풀었다는 것만 봐도, 난이도가 근 3개 contest보다 쉬웠다. Visits $1\cdots N$로 이름 붙여진 Bessie의 친구들은 각자 자신의 농장을 소유하고 있다. 각 소 $i$는 소 $a_i(\neq i)$네 농장에 방문하고 싶다. $1\cdots N$의 순열 $(p_1,p_2,\cdots,p_N)$에 대해 다음을 시행한다: $a_{p_i}$가 이미 농장을 떠났다면, $p_i$는 자신의 농장에 남는다. 그렇지 않으면, $p_i$는 자신의 농장을 떠나 $a_{p_i}$의 농장에 방문한다. 이러한 방문은 즐거워서 소..
Searching for Soulmates $a_i$를 $b_i$로 바꾸기 위한 연산의 최소 횟수를 구하라. 연산에는 3가지 종류가 있다. $a_i\leftarrow a_i \times 2$ $a_i\leftarrow a_i / 2\ (\text{when}\ 2|a_i)$ $a_i\leftarrow a_i+1$ $1\le N\le 10, 1\le a_i,b_i\le 10^{18}$ #include #define REP(i,a,b) for (auto i = (a); i k) >= a) { ret = min(ret, (b>>k)-a+k+__builtin_popcountll(b)-__builtin_popcountll((b>>k)> n; REP(i,1,n) cin >> p[i].first >> p[i].seco..
