CodeForces #447 (Div.2 Only)

링크

두 번째 인생...코포.

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)\)