BOJ
-
[14653] 너의 이름은BOJ 2023. 3. 2. 01:38
메시지를 보낸 시점 Q 이후에 메시지를 보낸 사람, 조건상 모든 메시지를 읽는 A와 메시지를 보낸 본인이 정답의 가능성이 없음은 쉽게 보이는데, 이것만으론 불충분하다. 6 3 3 3 A 3 B 3 C 따라서, 아래의 조건을 추가한다. -> i < Q 이며 R_i == R_Q인 모든 P_i도 정답의 가능성이 없다. 만약 위 조건을 만족하는 P_i가 시점 Q의 메시지를 읽지 않았다면, R_i < R_Q이어야만 한다. 결론적으로 R_i는 오름차순 정렬되어 있는 상태이므로, 1
-
[11493] 동전 교환BOJ 2022. 11. 23. 22:10
https://www.acmicpc.net/problem/11493 11493번: 동전 교환 입력의 첫줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫줄에는 정수 n과 m (1 ≤ n ≤ 500, n-1 ≤ m ≤ n(n-1)/2 )이 주어진다. 여기서 n은 정점의 개수, m은 간선의 개수를 나타낸다. www.acmicpc.net #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; constexpr int MAX_V = 1005; // 최대 정점 개수 co..
-
[12971] 숫자 놀이BOJ 2022. 8. 11. 00:21
https://www.acmicpc.net/problem/12971 12971번: 숫자 놀이 공백으로 구분된 6개의 정수 P1, P2, P3, X1, X2, X3가 순서대로 주어진다. 모든 숫자는 1과 300사이의 정수다. www.acmicpc.net 중국인의 나머지 정리 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; ll minv(ll a, ll b) { if (a == 0 && b == 1) return 0; if (a == 1) return 1; return b..
-
[10775] 공항BOJ 2022. 8. 2. 09:42
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 사용할 수 있는 게이트중 번호가 큰 것 부터 도킹하는것이 유리하다. 유니온 파인드에서 정점 번호가 작은쪽으로 합쳐주면 남아있는 게이트중 가장 번호가 큰 것을 쉽게 찾을 수 있다. #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool loc..
-
lazy 세그 - 비재귀BOJ 2022. 7. 26. 19:58
template struct LazySegTree { // 1-indexed public: using A = NodeType; using B = LazyType; LazySegTree() : LazySegTree(0, A(), B()) {} explicit LazySegTree(int n, const A& e, const B& id) : n(n), e(e), id(id), lg(Log2(n)), sz(1 > i i); if (r + 1 >> i i); } for (int L = l, R = r; L >= 1, R >>= 1) { if (L & 1) Apply(L++, f); if (~R & 1) Apply(R--, f); } for (int i = 1; i > i i); if (r + 1 >> i i);..
-
[10999] 구간 합 구하기 2BOJ 2022. 7. 26. 19:56
https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else constexpr bool local = true; #endif using ll = long long; using pi = pair; template struct LazySegTr..
-
[13306] 트리BOJ 2022. 7. 20. 12:56
https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net #include using namespace std; class UF { public: vector p; UF(int n) { p = vector(n + 1, -1); } int find(int cur) { if (p[cur] n >> Q; v.resize(n + 1); auto uf = UF(n); int i; v[1] = 1; // root for (i = 2; i > ..
-
[1688] 지민이의 테러BOJ 2022. 7. 16. 16:42
https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있 www.acmicpc.net 다각형 밖의 임의의 점 하나를 잡고, 다각형 내에 존재하는지 판단 대상이 되는 점과의 선분을 만든다. 다각형을 구성하는 n개의 선분과 교차하는 횟수가 홀수번이라면 다각형 내의 점이 된다. 다각형의 경계 위에 있는 경우를 위 방식으로 잡아내지 못하므로 별도로 체크하고, 다각형 밖의 임의의 점과 그은 선분이 기존 다각형을 구성하던 선분과 평행하지 않도록 잡았다. #include using n..
-
[14907] 프로젝트 스케줄링BOJ 2022. 7. 4. 05:01
https://www.acmicpc.net/problem/14907 14907번: 프로젝트 스케줄링 입력은 1줄에서 26줄까지 입력될 수 있으며, 각각은 다른 작업 (위 예제에서 말하자면 A, B, C, …) 을 포함한다. 각 줄에는 다음과 같은 내용이 포함된다. 작업 이름을 나타내는 영문 대문자 하나, www.acmicpc.net 입력이 귀찮은 구현(?)문제, 알파벳은 숫자로 바꿔주거나, 배열 크기를 100정도로 잡거나.. 한줄 입력받고 파싱할때, 작업 전 완료해야하는 작업이 0개인 경우에 ' '(공백)이 한줄에 한번만 들어올 수 있음에 유의 #include using namespace std; #ifdef ONLINE_JUDGE constexpr bool local = false; #else cons..