CodeForces #447 (Div.2 Only)

2017. 11. 20. 02:21알고리즘 문풀/Others

링크

두 번째 인생...코포.


Solved : 4 / 5


Rank : 

29 (Official)

51 (Including Unofficial)


Rating Change : 1738 -> 1895 (파들파들)



A. QAQ (00 : 02)


Tag : Implementation


어떤 문자열이 주어졌을 때 그 문자열의 'QAQ' subsequence 개수를 묻는 문제. Q가 나올 때마다 개수를 더해 주면서 A가 나오면 (지금까지 나온 Q 수) * (앞으로 나올 Q 수) 를 답에 더해 주면 된다.


Complexity : \(O(n)\)


B. Ralph and His Magic Field (00 : 34)


Tag : Combinatorics, Number Theory


쉬운 수올 문제. 였으나... 알아보지 못하고 백트래킹을 돌려서 답을 유추했다.


\( k = -1 \wedge n+m \ : \ odd\)이면 0, 아니면 \(2^{(m-1)(n-1)}\)이 답이 된다. \(mn\)이 long long의 범위를 넘어가는 것에 주의하여 코딩해야 한다. (alpah 지못미...)


Complexity : \(O(\lg(nm))\)


C. Marco and GCD Sequence (00 : 50), (01 : 39), (01 : 50)


Tag : Number Theory, Observation


운빨 ㅈ망 문제. 생각이 나면 풀리고 안나면 ...

불가능할 조건은 \(s_0 \not{|} s_i\). \(s_0\)는 전체의 gcd임이 명백하기 때문이다.

수열은 \(s_0 s_i\)를 반복해서 출력하면 된다. 역시나 alpah 지못미...



Complexity : \(O(m)\)


D. Ralph and His Tour In Binary Country (01 : 28)


Tag : Data Structure

 

간단히 설명하자면


노드마다 벡터를 만들어서 자기 서브트리까지의 거리를 정렬해 놓고, 이에 대한 부분합도 구해 놓는다. (merge sort처럼 하면 \(O(n \lg n)\)에 구현 가능하다)


쿼리가 들어오면,


맨 처음 자기 서브트리를 보고,


자기 형제의 서브트리를 보고,

자기 바로 위 부모 자체를 보고,

자기 부모로 넘어가서 이를 반복한다.


노드가 이진 트리이므로 보게 되는 노드는 \(O(\lg n)\)개고, '보는' 과정에서는 lower_bound등을 이용하여 방문 가능한 모든 정점까지의 거리 합을 더해 주면 된다. 이 과정에서 \(O(\lg n)\)의 시간이 필요하므로,


Complexity : \(O(n \lg n + q \lg ^ {2} n)\)


E. Raplh and Mushroom (--:--)


Tag : Graph, SCC+DAG, Dynamic Programming


D 풀고 나서 시간이 얼마 안 남았고, 더러워 보여서 그냥 가만히 있었다...


풀이를 생각해 보면,

어떤 에지를 끝까지 '뽑아먹을' 수 있는 양은 정해져 있다. 즉, 버섯이 \(X\)개 있는 에지는 최대 \(f(X)\)개 만큼 먹을 수 있고, \(f(X)\)는 좀 더럽지만 \(O(1)\)만에 구할 수 있다.


그래프를 SCC - decomposition하면 각 SCC 내에서는 한도까지 '뽑아먹을' 수 있고, SCC들을 연결하는 DAG 상의 에지는 최대 1회 갈 수 있으므로 그냥 \(X\)만큼 버섯을 얻을 수 있다. 따라서 DAG에서 DP를 잘 돌려주면 답을 구할 수 있다.


Complexity : \(O(n+m)\)

'알고리즘 문풀 > Others' 카테고리의 다른 글

Codeforces Goodbye 2017 Contest  (0) 2017.12.30
Codechef 2017 November LunchTime  (0) 2017.11.26
CodeForces #447 (Div.2 Only)  (1) 2017.11.20
Codeforces Round 433 Div.2  (1) 2017.09.07
[IOI 2016] Detecting Molecules 풀이  (1) 2017.08.09
APIO 2015 Jakarta Skyscrapers 풀이  (0) 2017.07.13