#796 div2 6/28 virtual

https://codeforces.com/contest/1688

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

 

A 

 

x and y > 0, 

x xor y > 0인거 중 최소 y 찾는 문제 

 

그리디하게

1. 두 비트 이상 같으면 최소 비트만 1인 것 출력하고, 

2. 한비트만 같으면 그 비트의 위치가 가장 오른쪽인지 아닌지로 나눠서 판단한다. 

 

cout << 1<<idx << '\n' 이렇게 했는데 계속 이상한 값이 나와서 괄호를 하고 

'아 이거 이상하네' 생각만 했는데 다시 보니깐 시프트연산자랑 cout 출력이랑 모양이 같아서 그럴만하다

 

B

 

배열에서 다른 index 값 두개를 합치거나 하나를 골라서 반절하는 연산 두가지 존재,

최소의 연산횟수로 모두 홀수로 만들기 

 

짝수를 홀수를 만드는데에 최소 한번의 연산 필요

홀수 하나가 있다면 홀+짝 = 홀이므로 한번의 연산으로 계속해서 모든 짝수를 홀수로 만들 수 있음 

 

따라서 하나의 홀수를 확보하자 

 

2의 몇 승이냐에 따라서 몇 번 반절했을 때 홀수가 되느냐를 결정 따라서 그걸 세보고 판단

 

C 

 

읽다가 문제를 이해 못해서 D로 패스 아직 문제 이해 못함 

 

 

D

 

k만큼의 턴이 존재, 그 턴에 있는 곳에 보석을 먹을 수 있음 

먹으면 없어지고, 턴이 끝나면 모든 곳에 보석이 하나씩 증가 

인접한 곳으로만 이동 가능하고 처음에는 아무 곳에서나 시작 가능

 

처음에 무지성 그리디함 처음부터 다시 돌아오면 가능 사실은 예제에서 불가능인데 

귀신에 씌인건지 거짓말같이 37이 나옴 

 

그래서 구현하려는데 계속해서 등차 합공식 여러번 하고 계속해서 더하는 것에 어려움을 겪음

대회 중에는 한시간동안 구현만 하다가 계속 조금씩 다르게 나와서 실패 

 

 

오늘 지하철에서 생각하다보니깐 문제의 본질을 발견 (k>=n case에서)

 

늘어나는 양은 고정 -> 늘어난 것을 최대한 많이 먹어야 함 

 

예를 들어서 마지막에 0 1 2 3 4 9 이런식으로 끝나면 안됨

 

a b c d e f g 라고 했을 때

 

결국 a -> g 로 끝나면 됨 그래서 마지막에는 6 5 4 3 2 1 0 이 되면 됨

왜냐 좀 엄밀하게 생각했는데 지금은 잘 안됨 일단 자야되니깐 여기까지 

 

아이디어로 바로 풀 수도 있지만 엄밀하게 증명하는 능력이 우선인 것 같다. 

그리고 난 확실히 밖에서 사람들 있는 곳에서 생각이 더 잘된다.