Codeforces Round 971 (Div.4) E, F, G1 풀이
현재 Div.4는 블루라 언레라 contest를 직접 치지는 않았다. 하지만, 컨테스트가 끝나고 심심해서 문제 이름을 보니 원신, 붕괴 스타레일 캐릭터길래 찍먹으로 E, F, G1 정도만 풀어보았다. E. Klee's SUPER DUPER LARGE Array!!! 클레가 가지고 있는 수열에서 mid를 기준으로 [k, mid], [mid+1, k+n-1]로 구간을 나누어 각자의 합을 구한 다음 차를 비교하는 것은 가우스 합 공식을 이용하면 O(1)에 가능하다. 이때, mid가 커질수록 [mid+1, k+n-1] - [k, mid] 값이 strict하게 증가하므로 mid의 부호에 따라 파라매트릭 서치를 통해서 이 값의 절댓값을 최소로 하는 인덱스를 찾아줄 수 있다. 소스코드#include #include ..
2024. 9. 5.
