AtCoder Beginner Contest 248

https://atcoder.jp/contests/abc248/tasks

 

대회가 있다는 사실을 몰랐기 때문에 30분 늦게 unrated로 시작하였다.

제시간에 대회를 참여했다면 아마도 1950~2050 정도의 퍼포가 나왔을 듯하다.

 

A. Lacked Number

 

미리 a에 '0'~'9'를 더해두고 S에 있는 모든 char을 빼주면 된다.

 

B. Slimes

 

말 그대로 B보다 커질 때까지 k를 곱해주면 된다.

integer overflow가 나는지 살짝 고민했지만 B의 범위가 1e9까지라 걱정을 멈추었다.

 

C. Dice Sum

 

(x + x^2 + ... x^m)^n 의 k차 이하의 계수를 전부 더해주면 된다.

n, m의 범위가 상당히 후하기에 FFT 따위는 필요없다.

 

D. Range Count Query

 

쿼리의 형태가 워낙 merge sort tree같아서 아무 생각 없이 그냥 merge sort tree를 박은 사람들이 많은 듯하다.

vector<set<int>>에 vector[val].insert(index)를 해준뒤에 upper_bound(r) - lower_bound(l)이 정해인 듯하다.

 

E. K-colinear line

 

모든 직선은 ax + by + c = 0 이며, 이 셋을 gcd(a, b, c)로 나누어주고 a > 0으로 하면 이 표현은 유일하다.

따라서 모든 두 점을 지나는 직선을 {a, b, c}로 만들고 map<tuple, int>로 각 표현마다 개수를 세주면 된다.

-> 만일 이 직선이 kC2번 이상 세진다면 이 직선 위에는 k개 이상의 점이 존재한다.

 

F. Keep Connect

 

DP를 '잘' 하면 된다. 

 

-> 관찰을 통해서 어떤 위치 a, b의 위쪽 혹은 아래쪽 edge가 없을 경우, 그 사이에 기둥이 최소 하나는 존재한다

-> 따라서 제일 왼쪽 기둥부터 제일 오른쪽 기둥까지 dp를 한다고 할 때 다음과 같이 4가지 state를 정할 수 있다.

    1) 직전에 기둥이 있으며, 위와 아래에 edge가 모두 있다.

    2) 직전에 기둥이 있으며, 위와 아래에 없는 edge가 있다.

    3) 직전에 기둥이 없으며, 기둥이 없기 직전부터 지금까지 위와 아래에 없는 edge가 없다.

    4) 직전에 기둥이 없으며, 기둥이 없기 직전부터 지금까지 위와 아래에 없는 edge가 존재한다.

-> 직전 state가 1이라면 현재 기둥과 그 옆의 위아래 edge에 뭔짓을 해도 괜찮다.

-> 직전 state가 2라면 현재 기둥과 그 옆의 위아래 edge를 동시에 제거할 수는 없다.

-> 직전 state가 3이라면 마찬가지로 뭔짓을 해도 괜찮다.

-> 직전 state가 4라면 2와 같이 동시에 제거하는 일은 있을 수 없다.

https://atcoder.jp/contests/abc248/submissions/31042317

-> 사실 위의 풀이를 보더라도 (1, 3) (2, 4)가 유사하여 묶을 수 있을 듯한데... 귀찮다.

 

G. GCD cost on the tree

 

https://www.acmicpc.net/problem/18172

위의 문제의 트리버전 정도라고 생각했는데 보니까 훨씬 간단한 문제이다.

 

이 문제는 모든 경로에 대해서 (포함하는 노드 수) * (GCD)를 더하는 문제라고 볼 수 있다.

아무튼 각 노드마다 현재 노드가 제일 상위노드인 경로들을 더해주면 된다.

-> 노드마다 (현재까지의 gcd값 X) = {gcd값이 X인 경로들의 합, gcd값이 X인 경로들의 개수}를 저장해둔다.

-> 그렇다면 DFS에서 (현재 노드 cur)와 (현재 자식 노드 nxt)에서의 경로들을 잘 합쳐주면 된다.

-> cur까지 gcd의 값이 d1인 경로들의 합이 x1, 개수가 y1이고, nxt까지 gcd값이 d2인 경로의 합, 개수가 x2, y2라 하자.

-> 이 두 종류의 경로들을 그대로 합친다면 총 경로의 개수는 y1y2이고 x1은 총 y2번, x2는 총 y1번 더해져야 한다.

-> 따라서 gcd(d1, d2) * (x1y2 + x2y1)을 답에 더해주는 것이 이 노드가 제일 상위노드인 경로들에 대한 C의 합이다.

각 노드당 저장된 gcd값이 그래봤자 로그개이기에 O(nlgnlgn)을 넘을 리는 없다.

https://atcoder.jp/contests/abc248/submissions/31061020 (물론 map을 써서 로그가 하나더...)

MOD값을 1e9 + 7로 해놓고서 왜 틀렸는지 고민하느라 1시간이나 버렸다.

 

sol2)

well known) \(\sum_{d|n}^{}{\phi(d)}\)

-> \(ans = \sum{n * length} = \sum{\phi(d)*sum\_of\_length(d)}\)

-> 모든 1~1e5인 d에 대해서 간선의 양 옆 노드가 모두 d의 배수인 간선들만 연결시킨 그래프에서 dp를 하면 된다.

-> 모든 간선은 자신의 약수 개수인 최대 로그번 등장하고 아마도 nlgn...?을 보일 것 같다.

https://atcoder.jp/contests/abc248/submissions/31036259

 

EX. Beautiful Subsequeces