Sunday, July 6, 2014

Codeforces #254

Div1 Problem : Link

A. 밀도는 그래프의 크기가 커질 수록 평균치에 수렴. 따라서 간선 하나가 답. AC.
http://codeforces.com/contest/444/submission/7022561

B. 1이 등장 많이하면 O(N)을 돌면서 set을 써서 큰 a[k]부터 해당 b[i-k]가 1인지 체크를 해주면서 답을 구하고, 1이 적게 등장하면 O(N * 1의 개수)만큼 돌면서 c[]를 채움. 처음에 d이하이면 1인 거에 집착한 나머지 1의 개수에 따라 경우를 나눌 생각은 못함. 결국은 a[]나 b[]나 랜덤으로 생성되는건데 빨리 캐치하지 못한 잘못이 큼. Upsolving함.
http://codeforces.com/contest/444/submission/7037368

C. 전형적인 Segment Tree 문제. 난 짜는 속도가 느려서 대회 때 나오면 남한테 맡기거나 포기함. 정말 많은 연습이 필요함. Upsolving 할 계획.

D. 쿼리로 주어지는 글자가 최대 길이가 4이므로 Hashing을 해서 저장한다. S[i]~S[i+3]까지 각각이 어디서부터 시작할 수 있는지 다 알아놓은 다음에(vector v[]) O(QN). 여기서 쿼리에 대한 답을 저장해주고 이미 구한 거면 안 구하면 AC. 이게 왜 TLE가 안 나느냐하면
1. 문자 종류가 한 가지일 경우, 쿼리 종류가 극소수. 따라서 빠름.
2. 문자 종류가 다양하면, v[i]의 원소 수가 매우 적어짐. 길이가 1인 건 N/26, 길이가 4인 건 대략 N/200정도로. 그래서 빠름. 결론적으로 빠름ㅋㅋ Upsolving함.
http://codeforces.com/contest/444/submission/7037656
Upsolving할 때는 Merge하는 방법 짜기가 귀찮아서 그냥 lower_bound함수 씀.O(QN log N). 그래도 AC.

E. 안 읽어봤는데 정렬 후, Union Find하면 된단다.

No comments:

Post a Comment