https://www.acmicpc.net/problem/7469 Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다. 실제로 구현해 본 건 처음이었는데 예전에 명우씨한테 잠깐 설명들었던게 도움이 됐다. (Persistent Segment Tree에 대한 설명은 요기에) vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N) 자세한 설명은 다음에... 테스트케이스 : (출처 : NEERC Subregional Contest) #include #include #include #include #define MAXN 262150#define INF 1987654321using name..

http://codeforces.com/contest/831/problem/E E. Cards Sortingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputVasily has a deck of cards consisting of n cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on them.Vasily decided to sort the cards...

http://codeforces.com/problemset/problem/831/C C. Jury Markstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp watched TV-show where k jury members one by one rated a participant by adding him a certain number of points (may be negative, i. e. points were subtracted). Initially the participant had some score, and each the marks were one..

유적지 여행 유근이는 N개의 도시와 M개의 도로로 연결된 유적지를 여행하려고 한다. 유근이는 사실 도시를 방문하는 것 보다 드라이브하는 것에 더 관심이 많아서 N개의 도시를 모두 방문하지 못하더라도 M개의 도로를 모두 지나가길 원한다. 다만 유근이는 M개의 도로 중 2개의 도로는 한번씩만 지나고, 나머지 M-2개의 도로는 정확히 2번씩 방문하는 여행루트를 만들려 한다. 도로로 연결되어있지 않은 곳은 서로 이동할 수 없기 때문에 한 번 여행을 시작하면 시작점과 연결된 도시들만 여행할 수 있다. 또한 여행 루트에서 출발지와 목적지 도시는 중요하지 않고, 어떤 도로를 한번씩만 지나는지, 어떤 도로를 두 번씩 지나는지에 따라 각기 다른 루트로 간주한다고 한다. 유근이가 모든 M개의 도로를 여행할 수 있는 여행루..

http://codeforces.com/contest/791/problem/B 임의의 세점 X,Y,Z에 대해 X-Y && Y-Z 이면 X-Z를 만족하는가를 묻는 문제이다. 한점 X와 연결되어있는 Xi 들은 모두 서로 연결되어있어야 한다는 것을 알 수 있고, 따라서 임의의 점 X를 잡고 그것과 연결된 노드들 X1 ~ Xk 의 개수를 k라 하면 X에 연결된 노드 개수와 X1~Xk에 연결된 노드 개수들의 합이 k*(k-1)인지를 확인하면 된다. 주의할 점은for(int i=1;i

http://codeforces.com/contest/785/problem/D 괄호문자열이 주어지면 문자열에 있는 괄호들을 임의로 선택하여 만들 수 있는 RSBS(regular simple bracket sequences)의 개수를 찾아 그 개수를 1e9+7로 나눈 나머지를 출력하는 문제이다. RSBS란 It is not empty (that is n ≠ 0).The length of the sequence is even.First charactes of the sequence are equal to "(".Last charactes of the sequence are equal to ")". 인데 간단히 말해 앞쪽은 n/2개의 '(' 뒤쪽은 n/2개의 ')'로 이루어진 괄호를 말한다. 즉 (())나 (..

http://codeforces.com/contest/782/problem/B N명의 사람들이 각각 이동할 수 있는 최대속도가 주어지고, 남/북 방향중 한쪽으로 일정한 속도로 이동할 수 있을 때 최소 몇시간(단위시간)만에 모두 만날 수 있는지를 묻는 문제이다. 속도와 거리의 범위가 1~1e9이므로 만나는 시간을 기준으로 parametric search를 시도한다. 다시말해 처음엔 k 시간동안 N명의 사람들이 이동할 수 있는 거리범위를 모두 구했을 때 만날 수 있는 장소가 있다면(교집합이 존재한다면) N명의 사람들은 늦어도 k시간 안에는 만날 수 있다는 뜻이므로 최소 시간의 범위는 1~k사이에 있게 된다. 문제에서 오차범위를 1e-6이하로 줄이라고 했기 때문에 시간의 low, hi범위의 차가 1e-7정도 ..

https://www.acmicpc.net/problem/6591 정답이 int범위 안에 들어온다는 힌트가 주어진 Combination을 구하는 문제이다. 파스칼의 삼각형을이용한 DP로 접근을 하면 n = k = 2^(31)-1 인 경우도 있기 때문에 배열자체를 잡을 메모리가 부족하다. (DP배열을 벡터로 짜보면 될것같기도한데.. 해보진않음) 간단하게 정말 조합을 구하는 손으로 구하는것처럼 계산하면 overflow없이 계산할 수 있다. 먼저 r>n/2인경우에 r=n-r로 바꿔준다. (∵ nCr = nC(n-r)) r>0인 경우만 생각해보면, n/2>=r 이고, r>0므로 (n-r+1) >= (r+1)/r > 1 을 만족한다. 따라서 (n-r+1)/r > 1 이고, nCr < 2^31 이므로 nC(r-1)..

http://codeforces.com/contest/779/problem/A 1~5까지의 성적을 가진학생들이 두 반에 무작위로 속해 있을 때 최소한 몇번의 학생교환을 하면 두반에 속해있는 학생구성이 같게되는지를 묻는 문제이다. 학생구성이 같다는 뜻은 1점부터 5점까지 받은 학생의 수가 두 반에 동일하게 분포되어있는 상태를 말함. 일단 두반에 동일하게 분포시킬 수 없는경우는 두 반에 속해있는 1점부터 5점들의 학생수를 세어보았을때 하나라도 홀수명인 점수가 있는 경우이다. 이 경우를 제외하곤 무조건 동일하게 분포가 가능하다. 각 반에 있는 점수대별로 인원을 체크 한 후, 더 많은 인원/2명을 상대방 반으로 넘기는 식으로 계산을 해주면 해결할 수 있다.

https://www.acmicpc.net/problem/9426 예전엔 중앙값 관련 문제 풀때 PQ 2개를 두고 풀거나 (최대/최소 중앙값을 찾는경우)parametric search로 풀었던것 같은데 오랜만에 중앙값 문제를 봐서 그런지 전에 풀었던 풀이가 기억이 나지않아 좀 다른 방법으로 풀었다. counting을 체크하는 리프노드가 65536개 짜리인 indexed tree를 구성하고, 최초 k개의 입력된 숫자를 indexed tree에 update한 뒤 중앙값인(k+1)/2번째 숫자가 어디있는지를 indexed tree에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다. 마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식..