본문 바로가기

Competitive Programming

(36)
Codeforces Round #848 (Div. 2) Dashboard - Codeforces Round #848 (Div. 2) - Codeforces codeforces.com 복귀 성공 Prob. A 대충 다 해보면 된다. Prob. B 초기에 조건을 만족하는지 확인하고, 그렇지 않다면 인접한 거끼리 위치를 바꾸거나 멀리 보내보면 된다. Prob. C 대충 비트마스크 써서 다 해보면 된다. 이런 걸 굳이 냈어야 싶지만.. 정확히 k개 쓸 때만 확인하는 게 정해인 듯 한데, 나는 k개 이하일 때 다 확인해보고 통과했다. Prob. D 다른 개수에 대한 기댓값 DP식을 세우고, 조금 변형하면 $dp_{i+1} = p \times dp_{i} + q \times dp_{i-1}$ 꼴로 나타낼 수 있다. 이제 $dp_0$과 $dp_1$만 찾으면 되는데, $d..
TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) Dashboard - TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces codeforces.com D에서 말려서 대회 던질 뻔 했다가 E를 빠르게 풀고 기사회생했다. Prob. A 일단 하나에 1을 넣어보면 $n$이 짝수일 때 다른 하나로 $\frac{n}{2}$이 가능하다는 걸 알 수 있고, 예제를 보면 $n$이 홀수일 때 불가능하다는 것을 추측할 수 있다. 대충 기우성으로 증명할 수 있겠지. 여담으로 0분대 솔브가 나 포함 5명 밖에 안 돼서 순간 누텔라 퍼포를 찍었다. Prob. B 잘 생각해보면 $a_i$를 크게, $p_i$는 작게 만드는 것이 최적이므로 루트 시간에 소인수분해를 하고, 소인수 개수로 정렬한 후 그리디하게 최대한 ..
Codeforces Round #846 (Div. 2) Dashboard - Codeforces Round #846 (Div. 2) - Codeforces codeforces.com C의 정해가 틀려서 대회가 언레가 되었다. 코포하려고 단과대 신환회도 탈주했는데 참... Prob. A (홀, 홀, 홀) or (홀, 짝, 짝)이 가능한지 확인한다. Prob. B 구간을 덜 나누는 게 이득이어서 두 개짜리를 모두 해보면 된다. Prob. C 우선순위 큐로 그리디하게 하면 된다고 생각했는데... 출제자도 몰랐던 반례가 있더라. Prob. D 하위 비트부터 건드려보고 얼마나 변하는지를 확인하면 된다. 내 IDE에서는 인터렉티브를 풀 수 없어서 제출 디버깅을 했다. Prob. E 식을 열심히 정리하면 $\left \lfloor \frac{r}{g} \right \rf..
Codeforces Round #845 (Div. 2) Dashboard - Codeforces Round #845 (Div. 2) and ByteRace 2023 - Codeforces codeforces.com PS 재활 시작...! Prob. A 연산을 한 번 할 때마다 패리티가 같은 인접한 쌍이 하나 사라진다. 따라서 패리티가 같은 인접한 쌍의 수를 세주면 된다. Prob. B 아직 심층식 사고가 남아있는 탓인지 $(1, 2, \cdots , n-1)$에 $n$을 추가하는 식으로 생각했다. 이걸 이용하면 조합론 DP를 할 수 있는데 뇌절이고, 전체적인 구조만 살펴보면 $n \times (n-1) \times n!$이 답이라는 걸 알아낼 수 있다. Prob. C 풀이는 뻔하다. 대충 정렬하면 가운데에 위치한 놈들은 다 쓰는 게 이득이니까 투포인터를 잘 ..
Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) Dashboard - Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces codeforces.com 치졸한 방법으로 개인 최고 퍼포를 내고 맥레를 찍었다. 핵도 실력이지 ㅎ Prob. A $1$이 나올 때마다 부호를 바꿔준다. Prob. B 일단 비둘기집을 이용해보려 했는데 construction이 잘 안 되어서 계속 뇌절했다. $n$을 $k$에 대하여 최대한 고르게 자르면 $n$이 $k$의 배수가 아닐 때 $\left \lfloor \frac{n+k-1}{k} \right \rfloor$ $n \bmod k$개, 나머지는 $\left \lfloor \frac{n-1}{k} \right \rfloor$가 된다. $n$이 $k$의 배수..