[codeforces] 722 div.2 후기

A. And Then There Were K

n이 주어지고 n부터 1씩 줄여가며 and연산을 진행할 때,

가장 처음으로 연산 결과를 0으로 만드는 가장 큰 k를 찾는 문제이다.

 

일단 답은 바로 보였다.

n보다 작으면서 가장 가까운 2의 거듭제곱 -1 이 답이다.

근데 n이 2의 거듭제곱일 경우를 생각을 안하고 무지성으로 풀어버려 1틀을 했다.

이번 콘테스트 자체가 사람들이 문제를 많이 풀지 않아서

하나 하나의 패널티가 너무 큰데 너무 성급했다. 

 

B. Palindrome Game (easy version)

문자열이 주어졌을 때, 0의 개수를 기준으로

짝수면 B가 승 1이 아닌 홀수인 경우 A가 승인 문제였다.

 

게임이론 문제를 정말 별로 풀어보지 않아서

본인에게 최적인 선택이 상대를 고려했을때의 최적의 선택과 다르다는 것을

고려하지 못해 계속 뻘짓을 했었다.

풀어보니 게임이론 문제도 재밌는거 같긴 했다.

 

C.  Sequence Pair Weight

풀이를 뇌절의 뇌절해서 못풀었다.

나는 prefix sum으로 접근했는데

2의 길이를 가진 subsequence에서의 pair의 개수는

(pre[n] - pre[n-1]) + (pre[n-1] - pre[n-2]) + ... + (pre[2] - pre[1])

이 나오기 때문에 이런 식으로 정리해서 될 줄 알았는데 내 식이 잘못된건지 

코드를 잘 못 짠건지 암튼 걸렸다.

 

정해를 맨 처음 봤을 땐 이해가 가지 않았는데

n-1의 subsequence가 있을 때 뒤에 숫자 하나를 더 붙히면 어떻게 될 지 생각해봤더니

바로 이해가 갔다.

알고리즘 진짜 화가 잔뜩 난다 ㅎㅎ