CodeForces Educational Round 178

https://codeforces.com/contest/2104

 

 

Performance Rating : 2250

 

A

$a$, $b$, $c$ 중 $b>\frac{a+b+c}{3}$이거나 $a+b+c\;\mathrm{mod}\; 3\neq 0$이면 불가능하다.

 

B

마지막 $k-1$개는 무조건 들어갈 수밖에 없으므로 뒤에 $k-1$개의 원소의 합과 multiset을 활용해 나머지 숫자 중 최댓값을 더해 답을 구했다.

 

C

$1$이 쓰인 카드와 $n$이 쓰인 카드를 모두 가지게 되면 다른 카드와 관계없이 이긴다는 것을 관찰했다. $1$과 $n$이 같은 사람에게 있으면 둘 다 가지고 있는 사람을 출력했다. 그 후 $0$을 Bob이 가지고 있다면 $n-1$을 Bob이 가지고 있으면 $n$은 $0$으로, 나머지는 $n-1$로 대응하면 되지만 $n-1$이 Alice에게 있다면 $n-1$을 대처할 수 없으므로 Alice가 이긴다. $n$을 Bob이 가지고 있다면 Bob이 $n$을 제외한 카드를 하나라도 가지고 있다면 $0$에 대응이 가능하므로 이기고 아니라면 진다.

 

D

모든 숫자를 소수로 만드는 것이 이득이라는 것을 관찰했다. 또한 $a$의 숫자 중 큰 것부터 사용해야 최대한 많은 개수를 사용할 수 있겠다는 생각을 하여 $a$를 내림차순 정렬한 뒤 우선 에라토스테네스의 체로 소수를 모두 구해놓고 $a_1+\cdots+a_k\geq p_1+\cdots+p_k$인 $k$의 최댓값을 통해 답을 찾았다. 처음에 소수의 개수를 너무 적게 잡아 WA를 한번 받았다.

 

E

그리디 문자열 매칭이라는 생각이 바로 들었다. $i$번 인덱스보다 큰 인덱스 중 $j$번째 알파벳의 가장 작은 인덱스를 $nxt[i][j]$에 저장해두고 $dp[i]$에는 $i$번 인덱스 이후 문자열에 대해 그 문자열의 부분문자열이 아닌 가장 짧은 문자열의 길이를 저장해 두었다. 이후 $t$마다 매칭을 시킨 뒤 $dp$로 구해놓은 값을 출력하였다.