생각날때마다 올리는 블로그

문제 링크icpc.me/1813 해설문제에서 요구한 맞는 말의 개수는 k개가 맞다고 한 사람이 k명 있을때가 된다.따라서, 배열에 체크해주면서 차례대로 세면 된다. 코드http://colorscripter.com/s/mfhPYPx

http://codeforces.com/contest/483/my 본론어제 엄청난 킹 갓 분들이 버츄얼을 뛰시기에 나도 꼽사리를 껴서 해봤다.어제 오후 4시 30분쯤인가 그쯤 시작했는데, 단 36분만에 GG 치고 나왔다.다른 갓분들은 D까지 푸셨다.. 부럽 나도 이렇게 잘하고싶다.다음은 스코어보드윗 사진은 방금 내가 D를 풀어서 이렇게 되어있었다.버츄얼 대회에서는 난 C까지 밖에 못푼... ㅠㅠ다음은 내가 대회하면서 한 생각 + 풀이를 적도록 하겠다 A. AC(00:02)문제를 보니 a,b는 서로소, b,c도 서로소인데 a,c는 서로소가 아닌 쌍을 찾아란 것임을 깨달았다.(a

https://www.acmicpc.net/problem/3653 문제상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다.보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다.상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫자로 쉽게 구별할 수 있다.각 영화의 위치를 기록하는 프로그램을 작성하시오. 상근이가 영화를 한 편 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야 한다. 입력첫째 줄에 테스트 ..

서론우리는 많은 쿼리 문제를 만나게 된다. 특히, 그 중에서도 구간을 처리하는 쿼리문제는 많이 나오면서도 중요한데, 이를 일반적으로 naive하게 처리하면 망한다(...)예를 들어, 구간의 최소값을 구하는 문제가 있다고 하자. 이 경우, 일반적으로 짜면 모든 구간을 다 돌면서 확인하는 식일건데, 쿼리의 개수를 Q라고 하고, 구간의 최대 길이를 N이라고 하면 O(QN)의 시간이 소요된다. 하지만, Q가 10만, N도 10만으로 주어지는 일반적인 문제에서는 TLE로 코드가 터지고 내 멘탈도 터지고(...)어찌됐든, 다른 방안을 모색해야한다. 이 때 사용하는 것이 세그먼트 트리이다. 우리는 세그먼트 트리에 대해 자세히 알아보고, 일반적인 재귀로 짜는 방식 말고 비재귀로 짜는 방식에 대해 알아보겠다. ( 개인적..

https://oj.uz/problem/view/JOI18_stove 풀이a[i]-(a[i-1]+1)이 공백기이다.공백기를 가장 작은 순서대로 N-K개 가지고 있으면, 이는 최소시간이 된다.또한, 무조건 사람이 왔을때 켜야 되므로, N명이 있으면 최소 N의 시간이 걸린다.ans=N으로 잡고 priority_queue로 관리해주면 된다. 코드https://oj.uz/submission/49483

서론우리는 종종 트리에서 u점과 v점의 거리 차이를 구하는 문제를 접하게 된다. 문제가 하나라면 순회하면서 찾아내면 되지만, 만약 쿼리로 주어진다면...? naive하게 짜다간 뚝배기가 깨진다.따라서, 우리는 naive가 아니라 다른 방법을 찾아내야한다. 이 때, 우리는 하나의 중요한 점을 관찰할 수 있다. 바로, u와 v의 거리는 u와 v가 동시에 가르키는 공통 조상(Common Ancestor)과 관련이 있음을 알 수 있다. 그러면, 우리는 각 점에서 트리의 시작노드에서 그 노드까지의 거리를 저장해놓고, 공통조상까지의 거리를 구해서 빼면 됨을 알 수 있다. 그러면, 공통 조상은 어떻게 구할까? 이걸 지금 알아보도록 하자. 필요한 사전지식구간 트리(흔히 Segement tree,세그먼트 트리라고 불림)..

[05-28,21:00] 문제에 도전! [05-28,23:50] ㄹㅇ핵어렵다 어떻게 해야하지?[05-29,14:32] 아이디어 생각은 해냈으나, 말도 안되는 아이디어 + 증명 실패라서 풀이를 찾아봄http://blog.myungwoo.kr/45?category=565846LCA가 필요한 풀이란걸 꺠달음 LCA 공부하고 재시도각[05-29,17:00] One-Liner 보고 소름 돋음. 굉장한 문제다.... 증명 하고 꼭 올려봐야지

Codeforces에서 열렸던 Avito 대회에서 나온 D랑 비트 크기 55로 바꾸고, Bitwise OR 연산에서 AND 연산으로 바꾸기만 하면 완전히 동치이다.참고로 역대 APIO 문제들 중에서 가장 쉬웠던 문제들 중 하나라고 한다.... 난이도 실화? https://oj.uz/problem/view/APIO15_sculpture 코드포스 D문제는 맨 끝에 올려놓을테니 완전히 이해되면 한번 풀어보길 바란다. 문제 요약주어진 배열 A를 K개의 그룹으로 분할하려고 한다. 각 그룹에 들어가있는 수들의 합을 구하여 전부다 Bitwise OR 연산을 수행하였을 때 최대값을 구하여라. 풀이일단 우리는 Bitwise OR 연산이라는 것에 주목해야 한다. Bitwise 계산이고, 최대 들어오는 값이 10억(대략 2..

https://oj.uz/problem/view/JOI18_tents 풀이 dp[h][w] : h개의 행과 w개의 열을 가지고 있을 때, 텐트를 놓을 수 있는 경우의 수 우리는 h번째 행에 중심을 둘 것이다. 1. h번째 행에 아무 텐트도 놓지 않을 경우 2. w개의 열 중에 텐트 하나를 놓을 경우 3. w열 중에 하나 놓고, 하나 놓은 것과 다른 열에 하나를 놓는 경우 4. w열 중에 하나 놓고, 그것과 동일한 열에 h-1개의 행 중 하나를 놓는 경우 1번 같은 경우엔 점화식은 2번 같은 경우엔 점화식은 3번 같은 경우엔 점화식은 4번 같은 경우엔 점화식은 점화식이 나와있으니 스무스하게 탑다운으로 짜면 그냥 머 뚝딱 하나 조심해야 하는 부분은 다 비어있는 경우를 제외해야 한다. 최종답 - 1을 해주면 ..

https://oj.uz/problem/view/JOI18_worst_reporter3 [05-27,14:00] D_i는 주기를 가진다.[05-27,14:56] 1번째 사람은 무조건 D_1의 배수에 위치.[05-27,14:58] 수정, 1번째 사람은 무조건 (D_1의 배수)-1에 위치.[05-27,15:20] 각 학생의 규칙을 찾음[05-27,17:16] 구현 시작[05-27,17:40] 구현 귀찮아서 때려치고 내일로 미룸[05-28,17:38] 구현 재시작[05-28,17:50] 구현 완료, AC ( 100점! ) 풀이 말했다시피 각 학생은 규칙을 가진다.규칙은 몇번 해보면 알겠지만, 각 학생마다 주기가 임이 됨을 알 수 있다. 몇번 노가다하면 나온다. 여기까진 굉장히 빨리 찾았는데.. 각 쿼리를 처리..