joseph0528 코딩 블로그

이 문제는 설명자체는 간단한데, 트리가 주어지고 1번 쿼리는 트리의 노드를 바꾸는 거고, 2번 쿼리는 현재 만들어진 트리에서 1번 노드에서 v 노드로 가는 길에 1번 노드와 가장 가까운 검정 노드의 번호를 출력하는 문제이다. 이 문제도 여러 가지 풀이 방법이 있는 걸로 알고 있고 가장 대표적인 풀이가 HLD(Heavy heavy Light Decomposition)으로 알고 있는데, 그 풀이가 아닌 ETT(오일러 투어 테크닉) 와 lazy 세그 (느리게 갱신되는 세그먼트 트리), sparse table(희소 배열)을 이용한 풀이를 작성하겠다. 이 문제의 핵심은 2번 쿼리니 1번 쿼리는 2번쿼리의 구조 내에서 구현해 줘야 된다. 그러므로 2번 쿼리부터 설명하겠다. 1부터 v 로 가는 길에서 1에 가장 가까..

https://www.acmicpc.net/problem/17163 17163번: 가희의 수열놀이 (Large) 첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 106, 1 ≤ mod ≤ 2×109) 이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어 www.acmicpc.net 문제에 쿼리가 있어 세그라는 생각을 할 수 있지만 1

보이는 거 그대로 망했다 1214라면 사실상 본선 확정이지만 이번 연도부턴 1519라 이 정도 점수론 절대 갈 수 없다. 일단 풀이는 전부터 작성하고 있었으니 이어서 작성했다. 1. 계단 더보기 nypc의 첫 문제다 처음에 잡았을 때 뇌절이 좀 있어서 나중에 풀었는데 예제 설명에 쓰여있는 방법이 최적해다.(사실 그냥 준 문제) 현재 위치에서 내려간다음 끝까지 올라갔다 내려갔다 하면서 마지막에는 현재 위치로 다시 돌아와야 하니 1층에서 지금 층으로 오는 횟수를 빼주고 뺀값들로 왔다 갔다 해주면 되는데 이때 현재 위치가 1일 때는 올라가는 거부터 해도 되지만 아닐 경우 한번 내려가 줘야 되는데 이때 위로 올라가서 횟수를 줄일 수 있을 경우 올라가 줘서 줄인 다음 내려오면 더 짧은 횟수를 구할 수 있다. 시복..

https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만 간단한 세그로 풀수 있다. 일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자 2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다 마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데 1번 쿼리에서 b번째 사탕..

https://www.acmicpc.net/problem/6164 6164번: Hotel The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacatio www.acmicpc.net 이문제는 일자로 나열된 방들이 있고 1번 쿼리는 소들은 n개가 연속되게 비어있는 방을 쓸려고 하는데 이때 그런 방이 있다면 연속된 n개..

solved.ac 티어 : 플5 https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다 이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다. k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b..

solved.ac 티어 : 골드 1 www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 문제를 보면 바로 구간 곱이라는 것을 알 수 있다 하지만 구간 곱을 구현한 뒤 제출하면 시간 초과를 받는다. 이유는 값이 너무 커져서 그런것인데 어차피 값을 원하는 게 아니라 부호만 알면 되는 거기 때문에 음수일 경우 -1을 곱하고 양수일 경우 1, 0일 경우 0을 곱해주면 된다. 출력에서도 구간 곱이 양수면 +, 음수면 -,0이면 0을 출력해주면 된다. #include ..