뉴비의 PS 낙서장

대학에 진학하고 나서 처음으로 SCPC를 쳤다. 예선 1차는 딱히 쓸게 없어 보여서 쓰진 않았고, 2차도 간단하게 쓸거 같다.수식 같은거 잘 못쓰고 풀이를 진짜 진짜 못써서 못 알아들을 수도 있다는거 양해 부탁드립니다 ㅠㅠ 문제 5. (9:00 ~ 10:20, 0:00 ~ 1:00)문제가 처음 열리자 마자 5번 문제를 봤다.그냥 얼마나 어려운지 체크해보기 위해 문제를 확인한거고, 생각보다 어려워서 고민을 좀 했다. 보물이 있는 A정점을 Ao, 없는 A정점을 Ax, 보물이 있는 B정점을 Bo, 없는 정점을 Bx라 하자. 서브테스크 ? (모든 B는 Bo, 모든 A는 Ao)사실 문제를 잘못 읽어서 여기서부터 시작했다.여기서 해본 관찰은1. A-A 는 A가 이긴다.2. B-B 는 B가 이긴다.3. B에서 A가 ..

2601번: 도서실카펫 (acmicpc.net) 2601번: 도서실카펫 모든 사각형의 좌표는 1,000,000 보다 작은 음이 아닌 정수이고 가로 세로의 길이는 1,000,000 보다 작은 양의 정수이다. 얼룩 직사각형은 서로 겹치지 않지만 접할 수는 있다. 얼룩 직사각형과 카펫 www.acmicpc.net 알고리즘 태그 : 레이지 세그먼트 트리, 스위핑 시간 복잡도 : \(O(NlogN+MlogM)\) 각 얼룩 마다 어디에 카펫을 설치할 경우 이 얼룩이 지워진다는 것을 직사각형 모양의 범위로 표현할 수 있다. 이제 이 범위들을 가지고 스위핑을 하며 구간 업뎃을 해서 각 업뎃이 끝났을 때 마다 전체 구간의 최댓값을 구해주면 된다. #include #define x first #define y second..

https://www.acmicpc.net/problem/17493 17493번: 동아리 홍보하기 1, 4, 7번 전봇대에 전단지를 붙이면, 모든 곳에서 전단지를 볼 수 있다. www.acmicpc.net 보통 저런 문제들이 트리 dp형태인데, dp테이블을 직관적으로 세워보자. \(dp[i][0] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드는 자식들 중 한 노드에 전단지가 붙여져있을 때, 최소 전단지 수 \(dp[i][1] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드에 전단지를 붙일때, 최소 전단지 수 \(dp[i][2] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드의 부모가 전단지가 붙여져있을 때, 최소 전단지 수 이렇게 \(dp\)식을 세..

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net \(N\)개의 수를 그리디적으로 적절히 정렬할려고 한다. 어떤 두 수 \(A\), \(B\) 에 대해 \(AB\)랑 \(BA\) 중에 더 크게 되도록 정렬을 해주면 된다. 만약, \(AB\) > \(BA\) 라면 \(A\), \(B\) 순으로 정렬해주면 되고, 반대라면 \(B\), \(A\) 순으로 정렬해주면 된다. 자리수를 구할때 입력받은 수가 0인 경우에 0자..

https://www.acmicpc.net/problem/8146 8146번: Tetris Attack A puzzle called "Tetris Attack" has lately become a very popular game in Byteotia. The game itself is highly sophisticated, so we shall only introduce its simplified rules: the player is given a stack of 2n elements, placed one on another and marked with n www.acmicpc.net 일단 여러가지 관찰을 해본게 있는데, 1. \(x..y..x..y\)의 경우엔, \(x..x...y..y\) 경우가 되거..

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 딱 보면 뭔가 금광세그를 박아야 할 것 같은 느낌이 든다. 그래서 한번 금광세그를 박았을때 뭘 어떻게 해야 할지를 적어보면, struc..

https://www.acmicpc.net/problem/18919 18919번: Allowed Swaps You are given a permutation of length $N$ and a list of allowed swaps. Each swap is defined by two distinct integers between 1 and $N$, inclusive --- positions in the permutation that can be swapped. Your task is to sort the permutation using no more than www.acmicpc.net \(x, y\) 쌍이 들어오면 \(x\) 와 \(y\)를 이어주는 간선을 만들어준다. 그러면, 그래프가 형성되는데, 사..

https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net '('을 1, ')'을 -1이라 가정한다. 만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다. 이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다. 따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다..

https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 이 문제는 언뜻 보면 어려워 보이는데, 사실 \((2000/2)^{2} = 10^{6}\) 임을 알면 왼쪽에 1000개, 오른쪽에 1000개에 적당한 약의 개수를 넣으면 \(10^6\) 개를 만들 수 있을 것 같다. 어떤 약의 수 X만큼을 주기 위해 X를 1000으로 나눈 몫과 나머지에 대한 식을 세워보자. $$X = 1000*b + r$$ 왼쪽엔 1000짜리 1000개, 오른쪽에는 1짜리 1000개를 넣으면, 원하는 수 만큼의 약을 담을 수 있다. #include using nam..

https://www.acmicpc.net/problem/17958 17958번: Cycle String? In the first example, substrings of the restored string are: “abbab”, “bbabc”, “babcb”, “abcbc”, “bcbcc”, “cbccb”, “bccba”, “ccbab”, “cbabb”, “babba”. Note that the first example does not contain repetitions, however www.acmicpc.net 일단 \(NO\)가 되는 조건을 알아보자. 1. 등장하는 문자가 1개인 경우 ex)\(aa...a\) 2. 등장하는 문자가 2개고, 한 문자가 \(2N-2\)개 이상인 경우 ex) \(aa..