문제 링크 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_k$가 최대가 되게 하..
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..
USACO 연습방에서 연습중입니다. Grass Planting BOJ 17024번 | 맞은 사람: 168 | 소요 시간: 10분 | 태그: 트리 주어진 입력은 트리 구조이다. 직접 인접하거나 중간 노드 하나를 끼고 인접하는 경우는 서로 종류가 달라야 한다. 트리의 전체 형태가 중요할까? 어떤 노드 기준으로 얼마나 많은 노드로 둘러싸였는지에 따라 종류의 개수가 달라질 것이다. (이를 차수라고 한다.) \(\max_{x\in G}\{\deg(x)\}+1\)이 답이 된다. 더보기 #include using namespace std; int main() { int n; cin >> n; int deg[n+1] = {0,}; for (int i = 1; i > a ..
