전체 글 썸네일형 리스트형 BOJ 32070 - 색깔 모으기 (P5) 24년 KOI 2차 초등부 3번, 중등부 2번이다.체감상 중등부는 2번, 3번, 4번 난이도가 다 똑같은데 이게 맞나?그건 그렇고 이 문제 풀이가 정말 재밌어서 풀이를 써보겠다. 먼저 Ai -> Bi을 간선으로 하는 그래프를 생각해보자. 만약 A가 순열이라면(위에 놓여 있는 공의 색이 모두 다름) 이 그래프는 여러 개의 사이클로 이루어져 있을 것이다. 그리고 이 사이클대로 따라가면서 공을 옮기다 보면 그 사이클의 공을 모두 같은 색끼리 모을 수 있으며, 이 때 옮기는 횟수는 (사이클 크기) + 1이다. (사이클 크기가 1인 경우는 예외로 옮길 필요가 없다.) 따라서 답은 저 (사이클 크기) + 1을 모든 사이클에 대해서 더해준 값이 된다.그럼 A가 .. 더보기 문제를 별해로 푸는 능력 가만보면 P2 이상 되는 문제를 풀었을 때 정해랑 일치한 경우가 거의 없는 것 같다. 당연한 것 같기도 하고..https://www.acmicpc.net/problem/16901https://www.acmicpc.net/problem/31232https://www.acmicpc.net/problem/28220https://www.acmicpc.net/problem/32007https://www.acmicpc.net/problem/18798지금 바로 생각나는 것만 적어봐도 이정도다. 딱히 별 의미는 없고 신기해서 글을 써봤다. 더보기 와 이걸 왜 대회 때 못풀었지 KOI'24 이진 트리 (중등부 3번, 고등부 2번)#include using namespace std;#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")#pragma optimize("unroll-loops")#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)#define all(x) x.begin(), x.end()#define rll(x) x.rbegin(), x.rend()#define comp(x) x.erase(unique(all(x)), x.end())#define MOD 1000000007#define debug(x) cout P;typedef pair PP;ll n;ll .. 더보기 루비를 풀었다 첫 루비는 꼭 자력솔을 하고 싶어서 하루종일(정확히는 이틀) 잡았다.6모 직전에 이게 맞는 선택인지는 모르겠다..총 126번 제출했는데 대부분 별 의미 없는 제출이고 버킷 사이즈 잡았던 게 대부분이다.Traveling Saga Problem보다 더한 시간 억까를 당해서 fastio랑 비재귀 레이지를 복붙해왔는데 그래서 사실 진짜 자력솔이라 할 수 있는지는 모르겠지만 아무튼 맞았다. 풀이를 간단하게만 적자면, 쿼리를 버킷으로 쪼개서, 그 버킷 전체를 포함하는 갱신 쿼리와 포함하지 않는 갱신 쿼리를 나누고 포함하는 경우는 일단 세그로 갱신한 다음 또 홀짝성으로 xor할지 말지를 결정하고, 포함하지 않는 경우는 레이지로 하나하나 업데이트해주면 된다.위 풀이를 미친듯이 최적화하면 풀린다. 이제 시험공부랑 cp나.. 더보기 KOI 2024 일기 망했다.내신 챙긴다고 PS만 하고 CP를 안 했더니 대회 때 그대로 멸망했다.본선도 못 가게 생겼다.내신이랑 PS 분배를 잘 해야될 것 같다. 열심히 해야겠다 더보기 BOJ 16182 - Dumae (D5) 사용 알고리즘Greedy(pq) + Topological Sorting 풀이일단 자명하게 DAG가 아니면 -1이다.그래프의 순서 관계도 있고 [L,R] 조건도 있어서 까다로울 수 있다. 결론부터 말하면 이 둘을 합치면 된다.대충 이런 그래프가 있다고 하자. 여기서 1번 노드는 자기만 보면 1번째 순서가 될 수도 있고 2번째 순서가 될 수도 있다. 하지만 바로 아래 노드(2번)를 고려하면 반드시 1번째 순서가 되어야 함을 알 수 있다. 이 조건을 [L,R]로 표현하려면 어떻게 해야 할까?위 상황에서 R2=2이다. 그 말은 2번 노드는 2번째 순서 안에 선택되어야 한다. 그리고 2번 노드가 선택되려면 1번 노드를 먼저 골랐어야 하므로 적어도 1번 노드는 2번째 순서보다 한칸 앞선 1번째.. 더보기 BOJ 31232 삼국지, BOJ 31750 Split the GSHS 3 (P2,P1) 두 문제는 다음과 같다. 트리에서 간선을 두 개 끊어서 세 컴포넌트로 나눌 때 각각 컴포넌트의 가중치 합을 a,b,c(a 더보기 BOJ 10014 - Traveling Saga Problem (D1) 사용 알고리즘 Centroid Decomposition 풀이 일단 기본 아이디어는 트리와 쿼리 5와 비슷하지만 반대의 기능을 가진 쿼리를 이용한다. 트리와 쿼리 5는 다음과 같은 두 가지 쿼리를 구현해야 한다. 1. 정점 집합에 i번 정점을 추가/삭제한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 가까운 정점과의 거리를 구한다. 여기서 2번 쿼리를 다음과 같이 수정해서 이용한다. 2. 집합에 포함된 정점들 중 임의의 정점 v와 가장 먼 정점을 구한다. 비슷해 보이지만 가장 가까운 거리와는 다르게, 가장 먼 거리는 centroid tree 상에서 조상들을 보면서 올라갈 때 같은 서브트리에 속한 정점을 고려하면 거리를 제대로 구하지 못하기 때문에, 자신이 속한 서브트리를 제외하고 가장 먼 거리를.. 더보기 이전 1 2 3 4 5 6 7 ··· 13 다음 목록 더보기
