Contest info
> Go to Codeforces Contests list
| Title | Codeforces Round 1060 |
| Division | (Div. 2) |
| Date | 2025 / 10 / 19 |
| Official | Rated |
| Rank | 3971 |
| Performance | 1652 |
| Rating | 1485 (-28) |
Problems
| # | Name | Solved | Attempt | | :—: | — | :—: | :—: |
| A | Notelock | solved | 0 |
| B | Make it Zigzag | solved | 0 |
| C1 | No Cost Too Great (Easy Version) | solved | 0 |
| C2 | No Cost Too Great (Hard Version) | 0 | |
| D | Catshock | 0 | |
| E | No Mind To Think | 0 | |
| F1 | Bombing (Easy Version) | 0 | |
| F2 | Bombing (Hard Version) | 0 |
Solution
A. Notelock
요약
다음 조건에 맞는 $s_i$를 0으로 바꿀수있다.
- $s_i = 1$
- $s_i$는 보호되지 않음
- $i$이전의 $k-1$개의 요소가 1을 포함하지 않음
- $S_{max(1, i-k+1)}, …, S_{i-1}$이 0으로만 이루어짐
$s$를 바꿀 수 없게 만들기 위한 최소 보호 횟수
제한
테스트케이스 $t$ ($1 \leq t \leq 100$) array 길이 $n$ ($1 \leq n \leq 1000$) 필요한 연속된 0개수 $k$ ($2 \leq k \leq n$) array 요소 $s_i \in {0, 1}$
모든 테스트케이스의 $n$의 합은 1000을 넘지 않음
풀이
뒤에 $1$이 있는 연속된 $0$의 개수가 $k-1$개 미만이여야함. 직전에 연속된 $0$의 개수가 $k-1$이상인 $1$들을 보호하면됨.
B. Make it Zigzag
요약
길이 $m$짜리 배열 $b$를 다음과 같이 지그재그로 만들어야함 $b_1 < b_2 > b_3 < b_4 …$
2가지 작업 수행 가능
-
- $i$를 하나 골라서 $a_i := max(a_1,…,a_i)$로 만듬.
- $a_1 ~ a_i$중 최댓값으로 바꿈
- $i$를 하나 골라서 $a_i := max(a_1,…,a_i)$로 만듬.
-
- $i$를 하나 골라서 $a_i–$
$a$를 지그재그로 만들 수 있는 최소한의 ‘작업2’ 횟수
제한
테스트케이스 $t$ ($1 \leq t \leq 10^4$) array 길이 $n$ ($2 \leq n \leq 2\cdot 10^5$) array 요소 $a_i$ ($1 \leq a_i \leq 10^9$)
모든 테스트케이스의 $n$의 합은 $2 \cdot 10^5$을 넘지 않음
풀이
작업1은 무제한 사용가능. 작업2만 줄이면됨.
i가 홀수 (지그재그 중 작은수)일 때 이전 값과 이후값(또는 perfix max)중 더 작은값을 기준으로 작업2를 계산
C1. No Cost Too Great (Easy Version)
요약
작업: $i$를 골라서 $a_i$를 1 증가시킴. 이때 비용은 $b_i$
$1 \leq i < j \leq n$인 $i, j$에 대하여 $\gcd(a_i, a_j) > 1$이 존재하도록 하는 최소 비용
제한
테스트케이스 $t$ ($1 \leq t \leq 10^4$) array 길이 $n$ ($2 \leq n \leq 2\cdot 10^5$) array 요소 $a_i$ ($1 \leq a_i \leq 2\cdot 10^5$) 덧셈 비용 $b_i$ ($b_i = 1$)
모든 테스트케이스의 $n$의 합은 $2 \cdot 10^5$을 넘지 않음
풀이
최대 비용은 2(홀수, 홀수일 때 +1, +1하면 최대공약수 2) $a_i$의 약수와 $a_i+1$의 약수를 각각 관리함. 만약 $a_i$의 약수 중 중복된 약수가 나온다면 비용은 0 $a_i$의 약수와 $a_i+1$의 약수가 중복되면 비용은 1 그렇지 않으면 비용은 2