A B C D E F CodeForces Gym일부러 집중력이 떨어진 상태에서 짧은 대회를 쳐봤다. 어떤 실수를 얼마나 하는지 보려고..템플릿도 안 켜고, 중간에 엎드려 잘 뻔하고... 결국 집중력 저하로 1시간만에 던졌다.DE는 풀 수 있을 것 같은데, PS를 크게 쉰 이후로 자료구조 구현에 굉장히 오랜 시간이 걸리고 있다. 보완이 필요하다. 풀이는 D E 푼 뒤에 올리는 걸로 하자.

대회 링크정신 나간 유사대회...코딩 습관 개선을 위해 후기를 쓰기는 하지만, 절대 추천할 만한 대회는 아니다. A B(+2) C D E1963 -> 2008 (+45) This section is intentionally left blank. Div1A. Cram Time (+, 13min) Tag : Constructive 10910^9109 범위의 두 정수 a,ba,ba,b에 대해서, 1⋯n1\cdots n1⋯n의 정수를 적절히 두 집합으로 분할해서 첫 번째 집합의 합은 aaa, 두 번째 집합의 합은 bbb를 넘지 않도록 해야 한다. 답은 너무 당연히 k(k+1)/2≤a+bk(k+1)/2 \le a + bk(k+1)/2≤a+b인 최대의 kkk일 것 같고, 실제로도 그렇다. 첫 번째 집합에 1,2,⋯m1, 2, \cdots m1,2,⋯m을 쑤셔넣자...

트리 / 그래프의 기본기인 DFS technique를 연습하려고 한다.너무 쉬운 건 말고, Div.1 A ~ B 부터 짬짬이 풀어야지. 링크 396C. On Changing Tree 코드 트리에 기본적으로 DFS numbering을 해주자.잘 모르겠다면 코드, 또는 다음 설명을 참조. 노드 vvv가 발견되는 시점을 dt[v]dt[v]dt[v], 노드 vvv의 탐색이 끝나는 시점을 ft[v]ft[v]ft[v], 노드 vvv의 깊이를 dep[v]dep[v]dep[v]라고 한다.합 세그먼트 트리를 2개 관리한다. 각각 X,KX, KX,K라고 하자. type 1 쿼리 (v,x,k)(v,x,k)(v,x,k) :XXX의 [dt[v],ft[v]][dt[v], ft[v]][dt[v],ft[v]]에 x+k⋅dep[v]x + k \cdot dep[v]x+k⋅dep[v]를 더해줌.KKK의 [dt[v],ft[v]][dt[v], ft[v]][dt[v],ft[v]]에 \(..

말그대로 여기서 태그에 DnC가 붙어 있는 놈들을 풀어보려는 시도입니다. 백준에서 좋은 DnC 찾기가 너무 힘들어서... 559B. Equivalent Strings 559B 문제가 말하는 "동치 관계"가 정말로 equivalent relation의 조건을 만족시킨다는 것이 관찰 포인트이다.그렇다면 한 string SSS의 대표원 rSr_{S}rS​를 정해줄 수 있고, 편의상 사전 순으로 가장 빠른 string으로 정해주면 된다. 어떤 길이가 짝수인 string S=A+BS = A + BS=A+B에 대해서 rS=min(rA+rB,rB+rA)r_{S} = \text{min}(r_{A} + r_{B}, r_{B} + r_{A})rS​=min(rA​+rB​,rB​+rA​)로 정해질 것이므로, 시간복잡도는 T(n)=2T(n2)+T(n) = 2T(\frac{n}{2}) + T(n)=2T(2n​)+ (문자열 비교하는 시간) \(..