yeongminb의 PS 블로그

BOJ 2517. 달리기segment tree, coordinate compression 보자마자 세그먼트 트리가 떠올라야하는 문제이다. 어떤 선수의 최소 등수는 $($그 선수 앞에 있는 선수들 중 그 선수보다 실력이 좋은 선수들 명수$) + 1$ 등이 된다. 그래서 앞에서 부터 segment tree에 업데이트 해주며 계산해주면 된다. 또한 선수들 실력의 절대적인 값은 중요하지 않으므로 좌표 압축을 해주어야한다. 시간복잡도는 $O(N\log{}{N})$이다.더보기#include #define fastio cin.tie(0)->ios::sync_with_stdio(0);using namespace std;const int NMAX = 5e5;int N;vector skill_level, cmp;struc..

CodeForces Raif Round 1. Carrots for Rabbitspriority queue, math, greedy priority queue를 사용하는 문제 치고는 좀 까다로운 문제였다. 처음 이 문제를 접근할 때에는 당근을 잘랐을 때 자른 당근의 길이채로 배열에 저장하려고 했었는데 그냥 2개로만 나눠지는 게 아니라 $n$ 개로 나눠질 수도 있기 때문에 나중 상황을 고려하지 못하게 된다. 그래서 그냥 당근은 그 길이대로 저장해되 그 당근을 현재까지 몇 개로 나눴는지를 저장하기로 하였다. 그래서 총 나눈 개수가 K개가 될 때 종료해주면 된다. 그럼 어떤 당근을 잘라야할지를 정해야한다. 그 기준을 '현재 상태에서 1번 더 나누었을 떄 시간이 얼마나 더 줄어드는가'로 하였다. 나눠지는 횟수가 ..

KOI 2024. 이진트리dp, math 문제는 상당히 어렵고 복잡할 것 같이 만들어놓고 풀어보면 진짜 별거없는 사기 문제이다. 그냥 $S(T)$ 들 간에 관계식을 잘 세워주면 풀린다.  $T$의 왼쪽 자식의 서브트리를 $T_l$, 오른쪽 자식의 서브트리를 $T_r$이라고 하자. 또 T에 대해 T의 리프노드 개수가 $n$ 개일 때 $R(T) := \sum_{i=1}^{n}f(i,n)$, 그리고 $L(T) := \sum_{i=1}^{n}f(1,i)$로 정의하자. 일단 $S(T) = S(T_l) + S(T_r) + leafNum(T_l)\times L(T_r) + leafNum(T_r)\times R(T_l) - 1$ 임을 알 수 있다. $($설명하기에는 조금 복잡한데 대충 왼쪽만 쓸 때, 오른쪽만 쓸 때,..

학원에서 수업시간에 딴짓$($?$)$을 하다 학원 벽에 '주어진 삼각형을 유한개의 오목사각형으로 채울 수 있을까?'라는 문장이 무려 '낙서'로 써져있는 것을 봤다. 못 채울 것이라는 생각을 가지고 몇 번 그림을 그려보니 정말 채워지지 않았다. '오 이거 증명해봐야겠다!'라는 충동을 느끼고 학원에서 증명해보았다. 생각보다 잘 증명한 것 같아서 여기에 남겨보았다.   주요 아이디어는 삼각형에만 국한하지 않고 일반적인 볼록다각형에 대해서 채울 수 있는지를 확인하는 것이었다. 삼각형은 항상 볼록하므로 일반적인 볼록다각형에 대해서 불가능하다는 것을 증명하는 것으로 충분하다. 그래서 오목사각형으로 이루어진 도형이 오목할 수 밖에 없다는 것을 증명하였다.  Proposition 1) 임의의 오목다각형에 오목사각형을 ..

CodeForces Round 364 $($Div. 1$)$. Connecting Universitiesdfs, dp 구현은 아주 간단하나 아이디어가 좀 필요했던 문제이다. $N\leq 2\times 10^5$ 이라서 적어도 $O(N\log{}{N})$이하의 풀이가 필요하다.  두 점 사이에 거리를 구하는데만 해도 dfs로 $O(N)$이나 걸리는데 최대 $\frac{N}{2}$ 쌍에 대해서 거리를 구하려고 하면 $O(N^2)$이기에 다른 방법이 필요했다. 그래서 더블카운팅 형식으로 세주려고 했다. 모든 간선들에 대해서 그 간선이 쓰일 수 있는 최대 횟수를 더해주면 그게 정답이 된다. 그 어떤 간선 $E = \left\{V,U\right\}$ 쓰일 수 있는 최대 횟수는 $V$방향 서브트리에 존재하는 대학의..

USACO 2024 December. 2D Conveyor Beltdfs, bfs, offline query $N \leq 10^3, Q\leq 10^5$일 때 $N\times N$ 격자에서 처리해야하므로 처음에 $O(N^2)$이하로 unusable한 conveyor belt들을 모두 계산해두고 $Q$개의 쿼리동안 $O(1)$안에 답을 계산해 출력하는 $O(N^2 + Q)$를 목표로 생각했다. 그래서 먼저 dfs를 잘 이용해 최종상태에서 unusable여부를 미리 계산을 해두었다. 계산을 해두고 보니 처음 상태에서 추가를 하는 것보다 최종상태에서 하나씩 빼는 것이 더 쉬울 것이라고 생각했다. 하나를 뺄 때 그 칸이 unusable->usable로 바뀐다면 그와 인접한 칸들만 탐색해주면 되고 수정한 칸들은..

문제 링크 문제 풀이 어떤 정점 $n\leq 21$개, 간선 $m$개의 그래프 위에 원숭이가 살고 있고, 매 턴마다 인접한 정점으로 항상 움직인다. 이때 매턴마다 그래프 위에 정점 하나를 골랐을 때 최악의 경우에도 언젠가는 원숭이를 잡을 수 있는지를 묻는 문제이다. 또 잡을 때까지의 최소 몇 번의 턴이 필요한지와 가능한 실례도 제시해야한다.   일단 문제를 보자마자 생각할 수 있는 것은 가능하기 위해서는 당연하게 이 그래프가 사이클이 없는 트리여야한다는 것이다. 만약 사이클이 있다면 그 사이클 위에 있는 원숭이는 매턴마다 두 가지의 선택지가 반드시 존재하므로 원숭이를 유인할 수 없다. 이는 직관적으로도 자명하다. 따라서 $m$이 $n-1$이 아닐 경우에는 볼 필요가 없어진다.  처음에는 트리인 경우는 모..

CSES. Stick Divisionspriority queue, greedy 입력으로 최종 상태의 분할 방법이 주어져있어서 분할하는 것보다 합치는 것으로 생각하는게 훨씬 편함. 길이 $l_1,l_2$인 두 막대를 합친다고 생각할 때 비용은 $l_1+l_2$이며 결과적으로 모든 막대를 합쳐야함. 이때 $N\leq 2\times 10^5$라서 $O(N\log_{}{N})$ 풀이가 필요함. 조금만 생각해보면 매순간마다 가장 작은 길이의 두 막대를 합치는 것이 비용적으로 최소임. 합치는 턴마다 막대가 1개씩 줄어드므로 $N$번 반복하면 되고 이때 최소인 두개를 찾는 것은 priority queue를 이용하면 $O(\log{}{N})$만에 할 수 있음. 더보기#include #define fastio cin.t..

CSES. Bit Inversions  set by hasing, data structure  $x_1$부터 $x_n$까지 중에 $x_i \neq x_{i-1}$인 $i$들을 저장해서 $i_{0}, ... , i_{k}$라고 하자 $($단, $i$중에는 0과 $n$은 반드시 포함해서 $i_{0} = 0, i_{k} = n$임$)$. 그럼 우리가 구하고자 하는 정답은 아래처럼 표현됨. $$\max_{1\leq j \leq k}{(i_j -i_{j-1})}$$ 이걸 $log$시간 안에 처리할 수 있기만 하면 $O(m\log{n})$에 가능. 이를 위해 set을 이용할 수 있음. 각 쿼리마다 업데이트 할 때 자신의 인덱스나 자신 - 1의 인덱스가 이미 set 안에 들어 있다면 제거 후 인덱스 끼리의 차를 업데..

Codeforces Round 179 Div. 1.  Greg And Array  prefix sum 아무 생각없이 각 쿼리마다 게속 업데이트 해주려고 하면 $O(mk + mn)$이 걸려서 $m,n,k \leq 10^5$인 범위에서 시간초과가 남. 따라서 연산이 사용되는 개수를 구하는 것과 연산을 통해 숫자를 변화시키는 것  각각 $O(m+k), O(m+n)$과 같이 바꿔줘야함. 이때 먼저 구간의 시작과 $($끝+1$)$에 각각 원하는 값을 미리 더해주고 나중에 누적 합을 해주어 처리하면 가능해짐.더보기#include using namespace std;typedef long long ll;typedef pair pii;const int nmax = 1e5, mmax = 1e5; struct operat..

kaggle 사이트에서 competitions 카테고리를 보다가 "House Prices - Advanced Regression Techniques" 이라는 제목을 봤는데 뭔가 재미있어 보여서 연습도 할겸 시도해보았다. 문제는 train set로 여러 집들의 세부사항과  그 판매 가격이 주어질 때 적절한 모델을 통해 이를 학습 시켜 test set에 있는 집들의 세부사항으로 그 가격들을 모두 예측하는 것이다. 이때 집들의 세부사항은 무려 80개나 주어진다. 주어지는 세부 사항들의 예시는 아래와 같다.○ MSSubClass: The building class○ MSZoning: The general zoning classification○ LotFrontage: Linear feet of street co..

경기과학고등학교 수학 브릿지 프로그램으로 수리창의문제해결 프로젝트라는 것을 하길래 문제를 풀어보았다. 1차 문제로 2개가 있었는데 하나는 사고력$(?)$을 요하는 증명 문제였고 나머지 하나는 경우의 수를 세는 기하문제였다. 이 기간동안 몸이 좀 아파서 집에만 있었는데 친구들 풀이 읽고 문제 풀고 하는게 재미있어서 이것만 했었다 ㅎㅎ  P1.  이 문제에는 어떤 한 열쇠 구멍을 돌릴 때, 그 열쇠 구명과 같은 열, 같은 행에 있는 모든 열쇠 구멍도 똑같이 돌아가지는 이상한 금고가 나온다. 이 금고에서 모든 구멍이 바닥과 수평인 방향의 모양으로 바꾸어 금고를 열 수 있는지 증명하는 문제이다.    처음에 친구들이 불가능하다고 증명을 해놨었는데 친구들의 풀이를 다 읽어보니까 공통적인 오류가 보였다. 그래서 열..

KMO 2차에 수열 관련해서 수학적 귀납법으로 증명하는 문제가 많이 보이는 것 같아서 가장 대표적인 수열인 피보나치 수열에 대해 정리해보려고 한다. PS에서도 자주 나오니까 도움이 될 것 같다.   2023 중캠 2차 3번 (AOPS링크) Math Message Boards FAQ & Community Help | AoPSSomething appears to not have loaded correctly.artofproblemsolving.com  피보나치 수열 관련된 문제로 이런 문제가 있는데, $a_{n} = 4{F_{2n-1}}^2 + {F_{2n}}^2$임을 증명하는 (더러운)문제이다. (솔직히 사람이 이걸 어떻게 생각하는지 모르겠다)  정의피보나치 수열은 자연수 $n$에 대해 아래와 같이 정의된..

문제 링크  문제 풀이  이 문제는 수직선 위에서 가로등의 위치들이 주어질 때 각 수직선 상의 위치마다 밝기를 작은 것부터 $K \leqslant 3\times 10^5$개 출력하는 문제이다.   일단 $ L \leqslant 10^{18} $ 이므로 배열에 각 위치들을 배열에 저장하거나, 완전탐색을 할 경우 MLE나 TLE가 날 수밖에 없다. 그래서 필요한 위치들의 밝기만 저장하거나 다른 방법이 필요하다.  가장 처음에 생각했던 것은 인접한 가로등 사이의 구간 길이를 저장하는 것이다. 구간의 길이의 개수는 항상 $N+1$개이고, $N \leqslant 3\times 10^{5} $ 이기 때문에 완전탐색을 해도 별 문제가 없고, 구간의 길이가 각 위치들의 밝기를 특정해주기 때문이다. 예를 들어서 구간의 ..

몬즈의 정리(Monge's Theorem)는 KMO 2차에 자주 나오는 정리로 근축에 대해 배울 때 꼭 배워야히는 정리 중 하나이다. 여기서는 몬즈의 정리와 이와 관련된 재미있는 문제 몇 개를 풀어볼 것이다.몬즈의 정리 : 세 원 A,B,C가 두 점에서 서로 교차할 때, 세 공통현은 한 점에서 만난다. ( 세 원의 근축들은 공점선이다.) 참고하면 좋은  사이트 : https://en.wikipedia.org/wiki/Power_center_(geometry) Power center (geometry) - WikipediaFrom Wikipedia, the free encyclopedia For 3 circles, the intersection of the radical axes of each pair D..