Codeforces Round 917 (Div. 2)

Dashboard - Codeforces Round 917 (Div. 2) - Codeforces

 

아직 작심삼일이 지나지 않았기 때문에 언레지만 참가했다. 초반부터 쭉 말렸지만 문제가 어려워서 퍼포는 괜찮게 나온 듯.

 

Prob. A

음수의 개수, $0$의 개수, 양수의 개수를 구하고 음수를 만들 수 있는지, 0을 만들어야 하는지에 따라 경우를 나눠주면 된다.

 

Prob. B

어렵다. 해시 써야 하나 한참 고민하다가 문자열의 길이를 고정한다고 생각해보니 풀이가 나왔다. 만들 문자열의 길이를 $m$이라 하면 뒤의 $m-1$개의 문자는 고정되고 앞에서 아무거나 하나 선택할 수 있다. 그래서 뒤에서부터 스위핑하며 개수를 관리하고 답을 구할 수 있다. 문제는 좋은데 이게 B?

 

Prob. C

$a_i$가 다 $0$일 때를 생각해보면 연산을 몇 번 해도 $a$는 단조 감소하기 때문에 점수는 최대 $1$ 증가한다. 그리고 이는 구간을 한 번만 더하고 점수를 더하면 연산 두 번에 확정적으로 $1$점을 얻을 수 있다. 따라서 처음 $a_i$에서 점수를 얼마나 얻을 수 있을지만 확인하면 되고, 이는 그냥 넉넉하게 $5n$번을 구간에 더해보면 된다. 처음에 $n$번만 했다가 틀렸다.

 

Prob. D

쓰기 귀찮아서 컨테 당시 필기로 대신한다. 대충 케이스 나누고 인버전 카운팅을 펜윅으로 로그 번 돌리는 풀이인데, 정해가 아닌 것 같다. 처음에 pbds로 날먹하려다가 TLE 나서 슬펐다.