CP를 연습하고 싶어 시간만 된다면 앞으로 많이 해볼 계획이다.
00:06 AC
홀수 항과 짝수 항이 모두 같을 수 있는지 판별하면 된다.
00:15 AC
$s$가 good이면 무조건 Yes이다. $s$와 $t$가 good이 아니면 무조건 No이다. 그렇지 않은 나머지 경우에 대해서만 생각하면, $t$는 항상 good이다.
$s$가 good이 되지 못하도록 하는 모든 쌍에 대해, 그 쌍에 $t$를 넣었을 때 해당 쌍이 good에 기여할 수 있는지 판별하면 된다.
00:48 AC
$i = 1$부터 차례대로, $s_i \neq s_{n-i+1}$이면 $i$를 증가시켜 계속 탐색한다. 만약 $s_i = s_{n-i+1}$이면, 두 가지 경우가 있다.
· $s_i = 1$인 경우, $s_i$ 앞에 "01"을 삽입한다.
· $s_i = 0$인 경우, $s_{n-i+1}$ 뒤에 "01"을 삽입한다.
이렇게 작업을 수행하면, 반드시 $s_i = s_{n-i+1}$을 만족하게 된다. $i$를 증가시켜 계속 탐색해주자.
01:04 WA 01:09 WA 01:44 AC
서로 다른 컴포넌트에 속한 어떤 정점 $i, j (i>1, j>1)$를 서로 이을 수 있다고 가정하자. $k$가 속한 컴포넌트의 $a$의 합을 $s_k = \sum \limits_{b \in S} a_b$라고 한다면, $s_i + s_j \ge i\cdot j\cdot c$이다.
이 때, $i$와 $1$, $j$와 $1$ 사이를 모두 잇지 못한다고 가정해보자.
$s_i + s_1 < i\cdot c$, $s_j + s_1 < j\cdot c$이고, 잘 정리하면 $s_i + s_j < i\cdot c + j\cdot c - 2s_1$이다.
위의 조건에 의해 $i\cdot j\cdot c < i\cdot c + j\cdot c - 2s_1$이 되고 $i>1, j>1$이므로 저 부등식은 성립할 수 없다.
가정이 모순이므로 '서로 다른 컴포넌트에 속한 어떤 정점 $i, j$를 이을 수 있으면, $i$와 $1$ 혹은 $j$와 $1$ 사이를 이을 수 있다.'가 성립한다. 따라서, 모든 점을 다 $1$와 이을 수 있는지만 확인하면 된다. 연결 순서는 $i\cdot c - a_i$가 작은 $i$부터 이어주면 된다.
E1 - Doremy's Drying Plan (Easy Version)
남은 시간동안 끄적여봤지만, 명쾌한 해답이 나오지 않았다. $K = 2$라서 스위핑 + 적당한 case_work로 해결할 수 있을 것 처럼 보였는데 막상 짤려고 보니 생각이 자꾸 꼬여서 결국 못 풀었다.
E2 - Doremy's Drying Plan (Hard Version)
???
???
Rating
+361
883 -> 1244
빨리 이쁜 색 갖고싶다.
'CP' 카테고리의 다른 글
| Codeforces Round 909 (Div. 3) (0) | 2023.11.19 |
|---|---|
| 2023 Sogang Programming Contest Open (Master) (0) | 2023.11.18 |
| 2023 IGRUS Newbie Programming Contest Open (0) | 2023.11.18 |
| SASA Programming Contest 2023 Open Contest Div. 1 (0) | 2023.11.18 |
| Codeforces Round 900 (Div. 3) (1) | 2023.10.29 |