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에서 루트부터 역방향으로 내려오면서 탐색해서 중앙값을 찾아낸다. 마찬가지로 다음 수가 주어지면 그 수를 업데이트 해주고, 반대로 제일 먼저 들어왔던 첫번째 수를 빼주고 업데이트 하는식..

https://www.acmicpc.net/problem/14432 (머그컵 E번) 이 문제의 핵심은 문제 마지막문단에 있는 "(단, 임의의 마을 A에서 B까지 무조건 한 가지 경로가 존재한다.)" 이다. 다시말해 이 마을들간의 관계는 트리형태이고, 따라서 한점을잡아 root로 간주하여 DFS로 탐색하면서 값을 갱신해주면 정답을 도출해 낼 수 있다.

https://www.acmicpc.net/problem/14437 (머그컵 A번) DP로 접근하면 D[현재위치][남은횟수]를 가지고 풀이하면 O(N*S)에 풀 수 있을 것 처럼 보인다. 다른 방법으로는 중복조합과 포함배재의 원리를 이용해서 풀 수도 있다. 중복조합을 이용하면 속도도 빠를 뿐 아니라, combination 값을 구할 때 DP가 아닌 fermat little thm이용해서 풀면 배열을 잡을 필요가 없어진다. 즉 메모리에 구애받지 않는 풀이가 된다. 시간복잡도는 O(N+logP).

http://kks227.blog.me/220802519976 SCC구하는 알고리즘 중 Tarjan Algorithm에 대해 잘 정리해놓은 블로그 개인적으로 kosaraju Algorithm이 더 쉬운것같은데.. 이번에 문제풀다가 타잔알고리즘으로만 풀 수 있게 생긴문제가 나와서 공부하게됐다. 그 문제 : https://www.acmicpc.net/problem/13988

https://www.acmicpc.net/problem/7975 (AMPPZ 2012 B번) 어찌보면 흔한 BFS문제처럼 보일 수 있지만 "두 관광 명소 사이를 이동하는 와중에도 매력도가 100m마다 1씩 증가한다." 라는 조건때문에도착점이 동일하더라도 시작하는 위치에 따라 cost가 바뀐다는 점을 해결하는 것이 이문제의 키포인트로 보인다. 결국 이 문제는 변수가 아래 두가지인 셈이다.1. 현재위치와 다음위치 사이의 거리2. 다음위치의 매력도 이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.즉 2번 변수를 고정시켜 '만약 도시의 매력도가 모두 동일하다면 어떤점을 선택하는것이 유리할까' 라는 문제로 접근을 해보면, 간단하게도 현재위치에서 갈수있는 다음위치들중 가..

https://www.acmicpc.net/problem/9521 이 문제는 i에서 출발하여 f[i]로 향하는 간선을 직접 그려보면 몇가지 특징을 확인 할 수 있다. 1. 각 지점마다 하나의 간선을 출발시킨다는 점2. 상호간에 간선관계가 직/간접적으로 전혀 없는 덩어리?그래프?들로 이루어져 있다는 점3. 이 덩어리들안에는 무조건 단 하나의 루프가 있다는 점(자기자신으로 향하는 간선을 가진점도 루프로 간주) 결국 이 문제는 N개의 점이 몇개의 덩어리들로 나누어 져 있으며, 그 덩어리들은 각각 하나씩 루프를 가지고있다.루프에 포함되지 않는 점들은 K-1개의 경우를 가지게되고, 결국 루프를 구성하는 점들의 경우의 수를 구할 수 있어야 한다. 1번부터 M번까지, M개의 점으로 이루어진 루프가 있다면 1번 = K..