CodeForces Round #735 A, B, D (Div.2)

https://codeforces.com/contest/1554

Dashboard - Codeforces Round #735 (Div. 2) - Codeforces

블루!

 

A (00:09)

길이 3 이상의 연속하는 부분 수열을 보는 것이 길이 2의 부분수열보다 나은 답을 내놓지 않는다. 길이 2의 부분수열 N - 1개만 확인하면 된다.

 

B (01:17)

$i\ast j-k\ast (a_i|a_j)$에서, i, j가 맨 뒤에 있다고 하면, 곱은 대충 $N^2$라고 하고, \(  (a_{i} | a_{j}) \)는 최대 2N이다. $N^2-2KN$을 최대화 하는 것인데, K의 조건이 min(N, 100)이므로 식은

$N^2-200N$정도로 볼 수 있다. \( (a_{i} | a_{j}) \)가 최소라고 해보면, i * j의 곱이 최소 $N^2-200N$가 되는 것이므로, 넉넉잡아서 뒤의 300개정도만 확인해도 매우 충분하다. 설명 뭐같이하네

O(300 * N)

 

D (00:59)

B, C 보다가 D를 갔는데 3분만에 풀렸다.문자열의 길이가 짝수인 경우aaa...  b  ...aaaa 꼴로 만들면 된다.문자열의 길이가 홀수인 경우aaa...  bc ...aaaa 꼴로 만들면 된다.

 

간단하게, 'a'로만 이루어진 문자열의 N/2번째에 'b'를 놓고, N이 홀수면 'b' 오른쪽에 'c'를 놓으면 된다.

 

생각보다 퍼포가 자비로워서 놀랐다