chw0501

이번에도 역시 시간이 없어서 virtual contest로 시험쳤다. 아쉽게 D번에 막혀서 3솔을 했다. D번을 틀린 이유는 트리의 필요충분 조건을 잘 몰랐기 때문이었다. 정점 개수 $n$의 그래프가 트리이면 $edge$개수가 $n-1$임은 참인 명제이다 하지만 그 역은 성립하지 않는다. 트리가 되기 위한 필요충분 조건은 다음과 같다. 모든 정점이 연결되어 있고, $edge$개수가 $n-1$ 이면 트리이다. 이 점을 놓쳐서 계속 D번 반례가 생겼다. D.Segment Tree 처음에는 당연히 edge개수만 세서 $n-1$과 비교하려고 했다. 펜윅트리와 $pair(l,r)$의 오름차순으로 정렬한 segment를 이용한 풀이였다. 여기서 더 나아가서 연결된 정점 쌍은 저장해놓았다가 dfs를 통해 모든 정점이..

#CONTEST 1 BOJ 2923. 숫자게임 잘 생각해보면 지금까지 입력받은 A와 B를 하나는 오름차순 다른 하나는 내림차순으로 정렬하고 순서에 맞게 쌍을 짝지어주면 된다. 이 아이디어를 바로 구현하면 정렬에 필요한 시간 $O(NlogN)$ 이고 전체 시간복잡도는 $O(N^2logN)$ 가 되어 TLE가 뜰 것이다. 문제를 다시 읽어보면 입력받는 숫자는 1부터 100까지의 숫자이다. 이 점을 잘 이용해야 한다. 배열 2개를 만들자. a[100]과 b[100]이다. $a[i]$ : A에 추가된 숫자 i의 개수 $b[i]$ : B에 추가된 숫자 i의 개수 투 포인터($i$, $j$)로 a는 1부터($i$) b는 100부터($j$) 차례대로 내려오면서 개수를 잘 가지고 놀면된다. 예를 들어 $v1=a[i]$..

코드포스르 꾸준히 참가하고는 싶으나 참가할 수 있는 시간대가 거의 없다.ㅠㅠ 시간이 나길래 Codeforces Round #610 (Div. 2) 를 virtual contest로 참가해보았다. 결과는 A,B1,B2만 풀었다. C번은 '-1' 하나때문에 결국 시간내에 못 풀었다. 대략적인 풀이는 다음과 같다. $Ti$을 오름차순으로 정렬하고 각 $Ti$에 해당하는 문제까지 푸는데 걸리는 시간을 $solved[i]$배열에 저장하자. 이 때 $solved[i]$까지 풀었을 때 시험을 종료해도 되는지 살펴보지만 이때 주의할 것은 앞으로 남은 문제 중에 다음 $Ti$ 가 오기 전까지 추가로 얼마나 풀 수 있는지 고려해야 한다. 자명히 easy문제부터 해결해야 될 것이다. 위에서 말한 '-1'은 해결한 $Ti$와..

#Contest 1 2. F7 각 플레이어를 점수 순으로 정렬 시켜 놓고 이분 탐색으로 해결하면 된다. 만약 index=h 인 사람이 우승 가능성이 있다면 그보다 점수가 높은 사람은 모두 우승가능성이 있기 때문이다. 4. boj 2792 이 문제 또한 마찬가지로 이분 탐색으로 해결할 수 있다. 질투심의 범위 $l$~$h$ 질투심이 $mid=(l+h)/2$ 일 때 최대한 적은 사람들에게 나눠주려고 했을 때 얼마나 적은 사람에게 나눠줄 수 있는지 계산하자. for(int i=0;i2 이므로 strength(n)=2 CASE 2. n이 짝수 짝수의 경우는 두 가지 경우 중 하나이다. (1) n -> $2^{i}$(2의 거듭제곱)->3->2 or (2) n->(홀수)->2 언제 (1)의 경우이고 언제 (2)..

Contest #1 5. SORT 이 문제는 문제 이름에도 적혀있듯이 정렬 문제이다. 문제를 잘 읽어보면 두 가지 문제가 합쳐졌음을 알 수 있다. 첫번째는 맨 처음 과정이다. 초기 배열을 v에 저장하고 투 포인터를 활용해서 각 부분 내리차순을 reverse시킨다. 최종적으로 v는 여러개의 부분 오름차순으로 정렬된 상태이다. vector stl을 활용하여 reverse(l,r)을 사용하면 구현이 가능하다. 그 다음은 정렬 과정은 인접한 숫자 쌍 하나씩 변한다. 앞에서 만든 부분 오름차순의 경계에서는 무조건 감소하는 숫자 쌍이 존재한다. 그 숫자쌍을 reverse 해주는 횟수를 세면 된다. 하지만 이는 삽입 정렬 시 움직이는 횟수와 일치한다. 이 문제는 펜윅 트리를 이용해서 O(log N)의 시간복잡도로 해..

1. 방배정 아이디어는 초등부 문제와 같다. 2019/10/10 - [koi해설] - KOI 2016 초등부 해설 2. 주유소 처음에는 lis문제인줄 알았는데 10줄정도로 짤 수 있는 쉬운 문제였다. 주유하는 곳의 가격이 떨어지는 곳에서 계속 충전해주면 된다.(가격이 떨어지면 무조건 선택) 3. 트리 disjoint set 문제이다. 하지만 쿼리를 위에서부터 처리하면 당연히 시간초과가 나기 때문에 아래서부터 반대로 처리해야 한다.(즉, 모두 분리되어 있는 서로소 집합에서 하나씩 간선을 추가한다) 그 과정에서 부모 노드의 정보를 압축하는 과정도 처리해줘야 한다. 4. 레이저 센서 아직...

1. 방 배정 int arr[2][6] arr[i][j]: 성별이 i이고 학년이 j인 사람 수 count 하고 $$\sum(arr[i][j]+K-1)/K)$$ 로 구하면 된다. 2. 타일 장식물 슬라이딩 윈도우 기법으로 배열 크기 2로만 풀 수 있다. arr[i]: 직사각형의 한 변 길이 arr[(i+1)%2]: 직사각형의 다른 변 길이 arr[(i+1)%2 = arr[i%2]+arr[(i+1)%2] 3. 리조트 dp 문제이다. dp[i][j]: i일째까지 리조트 이용하고 j개의 쿠폰이 남았을 때 앞으로 필요한 최소 비용 i일째까지 해결되었으니 j=i+1일 째부터 확인하는데 만약 가지 못하는 날이 있으면 j를 쭉 skip한다. 그리고 처음으로 가야하는 날이 있으면 그 때부터 1. 5일권 : 37000+d..

1. 두 박스 기하 문제이지만 x,y축과 평행한 직선이기 때문에 case만 잘 나누면 된다. 1. 겹치지 않는 경우(NULL) 2. POINT or LINE 3. 그 외에는 FACE 순으로 case를 나누자. 2. 두 로봇 2019/10/10 - [koi해설] - KOI 2018 초등부 해설 3. 물탱크 2019/10/10 - [koi해설] - KOI 2018 초등부 해설 4. 공룡 발자국 백트래킹으로 하나씩 점을 연결하면서 제자리로 돌아오면 발가락 개수 갱신 이런 느낌으로 풀려고 했다. 하지만 좌회전하는 경우에 case처리를 못하겠어서 다른 사람 풀이를 봤다. N개의 점들을 가장 먼저 기준점 기준으로 각도 정렬하고 생각하는 문제였다. 아직 해결 못했다...