Codeforces Virtual Participation

http://codeforces.com/contest/483/my

본론

어제 엄청난 킹 갓 분들이 버츄얼을 뛰시기에 나도 꼽사리를 껴서 해봤다.

어제 오후 4시 30분쯤인가 그쯤 시작했는데, 단 36분만에 GG 치고 나왔다.

다른 갓분들은 D까지 푸셨다.. 부럽 나도 이렇게 잘하고싶다.

다음은 스코어보드

윗 사진은 방금 내가 D를 풀어서 이렇게 되어있었다.

버츄얼 대회에서는 난 C까지 밖에 못푼... ㅠㅠ

다음은 내가 대회하면서 한 생각 + 풀이를 적도록 하겠다

A. AC(00:02)

문제를 보니 a,b는 서로소, b,c도 서로소인데 a,c는 서로소가 아닌 쌍을 찾아란 것임을 깨달았다.(a<b<c)

근데, 1차이가 나는 서로 다른 두 수는 서로소임이 자명하다

그리고, 2차이 나는 홀수도 서로소이다

하지만, 2차이 나는 짝수는 서로소가 아니다!

따라서, 구간 l,r이 들어오면 선 처리를 해준다

선처리란 l이 짝수면 놔두고, l이 홀수면 +1을 해주는 것이다.

그러고나서, l과 r의 차이가 2보다 작으면 -1을 출력하고, 그 외엔 l,l+1,l+2를 출력한다.

http://codeforces.com/contest/483/submission/38914498

B. AC(00:19)

보고 처음에 뇌가 비었다. 아니 이걸 어캐풀지??? 하면서

근데 뭔가 느낌이 Parallel Search 같아서 걍 답에 대한 이분탐색 때렸다

기모띠하면서 맞음

풀이는 이분탐색 하면서

n-n/a가 x보다 크고, n-n/b가 y보다 크고, n-n/(a*b)가 (x+y)보다 크면 된다. r을 줄인다.

그 외의 경우엔 l=mid+1로 해서 늘린다.

http://codeforces.com/contest/483/submission/38914981

C. AC(00:36)

딱 보자마자 바로 풀이를 알았다. B보다 C를 더 많이 푼 이유를 알게 해주는 문제였다

문제를 요약하자면, 서로 이웃된 항끼리의 차의 절댓값이 띠는 서로 다른 값의 개수가 k개를 만족시키게 수열을 만들어라이다.

k번째부터 n번째까지 왔다리갔다리하면 된다. 이거 말로 표현하기 어렵다. 코드를 보고 직접 해보면 암

http://codeforces.com/contest/483/submission/38915445

D. GG, After VP AC

 에디보고 똑같이 풀었다. 대충 비트수로 슥삭슥삭 한다는 감을 잡았는데, 그 뒤로 접근을 못했다 ㅠㅠㅠ

일단 a[i]를 i번째 숫자에서 무조건 있어야하는 비트들로 이루어져있는 숫자으로 구성되어있다고 하자.

그러면, l과 r 사이의 and 쿼리를 세그먼트 트리로 처리해줄 수 있다!!

과연 이 비트가 존재한다는 것을 어떻게 알 수 있을까?

그건 쿼리를 처리하면서 l번쨰부터 r번째까지는 q의 비트들을 다 가지고 있다고 가정을 하는 것이다.

그렇게 해서 누적합을 구해준다음에, 0보다 크면 적어도 하나는 있다는 것이므로 Bitwise OR 처리를 해준다.

그렇게 해서 모든 수를 구한 다음에, 세그먼트 트리 만들고 한다.

여기서, 중요한 점은 만약 쿼리를 처리했는데 q[i]보다 다르면, 이는 안된다는 것 따라서, NO를 출력한다.

왜 구간내의 값을 다 1로 해줘도 되는지에 대해선 한번 곰곰히 생각해보도록 하라.

http://codeforces.com/contest/483/submission/38941105

E. GG

나도 몰라

결론

앞으로 더 열심히 해야지