[버추얼 매일 돌리기 프로젝트 #8] Codeforces Round #473 (Div. 2)

결과.

1800대. 좋다 
요즘 1700~1900대의 퍼포를 내고 있는거 보면 좀만 더하면 퍼플을 갈 수 있다는 생각이 든다.
좀만 더 열심히 하자.


A. Mahmoud and Ehab and the even-odd game
홀짝성을 구별하는 문제이다.
1분 AC.
코드

B. Mahmoud and Ehab and the message
map을 이용하면 쉽게 해결할 수 있다.
같은 뜻의 문자열들을 다 같은 최소비용으로 통일해놓은 상태로 맵에 저장해두면 쉽게 해결 할 수 있다.
13분 AC
코드

 

C. Mahmoud and Ehab and the wrong algorithm
상당히 재밌다.
되는 경우를 생각해보자. 

트리를 하나의 체인처럼 i번째 노드와 i+1번째 노드를 이어주는 경우
1을 루트로 해서 다른 노드들을 다 이어주면 되는 경우

안되는 경우를 생각해보자.

N<=5인 경우) 무조건 되는 경우밖에 없다!
N>5인 경우) 노드 1에 2,3,4를 이어주고, 나머지 노드들은 2에 연결해준다.

참고로 1을 l로 써서 계속 틀리고 있었다(...)
코드

 

E. Mahmoud and Ehab and the xor-MST
먼저 이 문제의 해답은 

이다.

이는 dp로 해결할 수 있는데, 문제의 해답을 f(n)이라고 하자.
dp[i] = f((2^i)-1)
dp[i] = 2*dp[i-1]+2^i
코드

D는 보다가 뇌절이 와서 솔브 수가 더 많은 E를 풀었다.