Codeforces Round 1047 (Div. 3)

Contest info

> Go to Codeforces Contests list

Problems

Solution

A. Collatz Conjecture

요약

다음 작업을 $k$번 한 결과 $x$가 주어짐:

• $x$가 짝수이면, $x/2$
• $x$가 홀수이면, $3x+1$

가능한 초기값 중 아무거나 출력

제한

테스트케이스 $t$ ($1 \leq t \leq 400$) 작업횟수 $k$, 최종결과 $x$ ($1 \leq k, x \leq 20$)

풀이

$res = x \times 2^k$

B. Fun Permutation

요약

길이 $n$짜리 순열 $p$

$1 \leq i < n$ 인 모든 i에 대하여 $\gcd(p_i+q_i, p_{i+1}+q_{i+1}) \geq 3 $을 만족하는 순열 $q$를 구하여라

제한

테스트케이스 $t$ ($1 \leq t \leq 10^4$) 순열 길이 $n$ ($1 \leq n \leq 2\cdot 10^5$) 순열 요소 $p_1, … p_n$ ($1 \leq p_i \leq n$, 중복x)

(모든 테스트케이스의 $n$합은 $2\cdot 10^5$를 넘지않음)

풀이

$1 \leq i \leq n$ 인 모든 $i$에 대하여 $q_i = n-p_i+1$ 모든 $p_i + q_i$가 같아짐.

C. Maximum Even Sum

요약

$a, b$가 주어짐. $b = 0 \pmod k$ 인 $k$ 중 가장 큰 짝수인 $ak + b/k$를 구하라. 없으면 $-1$

제한

테스트케이스 $t$ ($1 \leq t \leq 10^4$) $a, b$ ($1 \leq a, b \leq a\cdot b \leq 10^{18}$)

풀이

기본적으로 $k$가 $\sqrt{b}$에 가까워 질 수록 결과가 작아짐 결과는 최대한 양 끝 값 (1 또는 $b$) $k$가 1이면 $a+b$ $k$가 $b$면 $ab+1$

a: 3, b: 16
k=1     3*1+16=19
k=2     3*2+8=14 (even)
k=4     3*4+4=16 (even)
k=8     3*8+2=26 (even)
k=16    3*16+1=49

• Case 1. $a, b$ 모두 홀수:
  • $k$가 $1, b$ 모두 가능, 둘중 큰거 선택
• Case 2. $a, b$ 모두 짝수:
  • $k$가 $b$이면, ($\text{짝수} \times \text{짝수} + 1 = \text{홀수}$)가 되어 불가능, 그 다음으로 크면서 가능한 $a*(b/2)+2$로 비교
• Case 3. $a$가 홀수, $b$가 짝수:
  • $b$가 4의 배수가 아니면 불가능 (무조건 홀수가 되버림)
    • $b = 2 \pmod{4}$: $b = 2 \times \text{홀수}$
      • $k$가 짝수: $ak 짝수 + b/k 홀수$
      • $k$가 홀수: $ak 홀수 + b/k 짝수$
  • 4의 배수라면 $k_{min}$과 $k_{max}$ 비교
    • $k_{min} = 2$ (1일경우 홀수+짝수로 홀수가됨)
    • $k_{max} = b/2$ (b일경우 동일하게 짝수+1)
• Case 4. $a$가 짝수, $b$가 홀수:
  • 불가능 (b의 약수는 모두 홀수, 짝수+홀수는 무조건 홀수임)

D. Fun Permutation

요약

배열 $a$가 있음 $f(x)$: 배열 $a$에서 $x$가 나타난 횟수

길이 $n$짜리 배열 $b$가 주어짐 $(1 \leq i \leq n)$인 모든 i에 대하여 $f(a_i)=b_i$를 만족하는 길이 $n$인 배열 $a$를 구하라 즉, $a_i$의 개수가 $b_i$개여야함 없으면 $-1$

제한

테스트케이스 $t$ ($1 \leq t \leq 10^4$) 배열 길이 $n$ ($1 \leq n \leq 2\cdot 10^5$) 배열 요소 $b_1, …, b_n$ ($1 \leq b_i \leq n$)

(모든 테스트케이스의 $n$합은 $2\cdot 10^5$를 넘지않음)

풀이

$a_i$는 뭐가 되든 상관없음. 1부터 순서대로 채워넣는다 배열 $b$에서 $b_i$의 개수는 $b_i$의 배수여야함. ($|3|=9$일 때, 3, 3, 3 분배 가능) 위 조건을 만족하면 각 $b_i$에 대하여 $b_i$개씩 동일한 숫자를 집어넣으면됨

E. Mexification

요약

$MEX(a)$: 배열 $a$에서 나타나지 않은 0을 포함한 양의 정수 중 가장 작은것

길이 $n$인 배열 $a$가 주어짐. 다음 작업을 $k$회 실행

• 모든 $a_i$에 대하여 $a_i$를 $MEX(a_1,…,a_{i-1},a_{i+1},…,a_{n})$ 값으로 만듬. 모든 작업은 동시에 실행 (새로 변경된 값은 연산에 반영되지 않음) 즉 $a_i$: 자신을 제외한 나머지 배열의 요소들 중 MEX값

$k$번 실행했을 때, 배열 요소들의 합을 구하라

제한

테스트케이스 $t$ ($1 \leq t \leq 10^4$) 배열 길이 $n$ ($1 \leq n \leq 2\cdot 10^5$) 작업 횟수 $k$ ($1 \leq n \leq 10^9$) 배열 요소 $a_1, …, a_n$ ($0 \leq a_i \leq n$)

(모든 테스트케이스의 $n$합은 $2\cdot 10^5$를 넘지않음)

풀이

대충 5번정도 돌려보면 1~2가지 패턴이 반복된다는 것을 알 수 있음. 반복되는것을 확인하면 남은 k번 계산해서 배열 합 계산

F. Prefix Maximum Invariance

요약

길이 $m$짜리 배열 $x$와 $y$가 주어짐. 길이 $m$짜리 배열 $z$: $x$의 prefix maximum 즉 $1 \leq i \leq m$인 모든 i에 대해 $max(x_1,…,x_i) = max(z_1,…,z_i)$

$f(x, y)$: $z_i=y_i$인 개수

$\sum^{n}{l=1}\sum^{n}{r=l} f([a_l, …,a_r], [b_l, …, b_r])$ 를 구하라 = $1 \leq l \leq r \leq n$인 모든 l,r에 대하여 $f([a_l, …,a_r], [b_l, …, b_r])$의 합을 구해라

제한

테스트케이스 $t$ ($1 \leq t \leq 10^4$) 배열 길이 $n$ ($1 \leq n \leq 2\cdot 10^5$) 배열 요소 $a_1, …, a_n$ ($0 \leq a_i \leq 2 \cdot n$) 배열 요소 $b_1, …, b_n$ ($0 \leq b_i \leq 2 \cdot n$)

(모든 테스트케이스의 $n$합은 $2\cdot 10^5$를 넘지않음)

풀이

$i$번째 요소가 총합에 얼마나 기여하는지 계산

$1 \leq i \leq n$인 모든 $i$에 대해 $i$번째 요소는 최대 $i \times (n-i+1)$번 기여 가능 $(1…i * i…n)$

Stack을 활용하여 현재까지 나온 최대값을 관리

$a_i = b_i$이면, 어떤 경우에도 가능. $a_i \neq b_i$이면,

• Stack이 비어있으면 최대값 갱신, 기여못함
• Stack이 비어있지 않으면, Stack에 들어있는 요소 중 $b_i$보다 크면서 가장 마지막에 나온 index까지 기여 가능 (stack은 내림차순이기때문에 이분탐색 가능)
  • $b_i$보다 작은 요소부터 시작하면 $z_i$가 새로운 max값이 되기 때문에, 기여할 수 없음
  • $(1…j * i…n, a_j \geq b_i)$