CodeTON Round 2 (Div. 1 + Div. 2)

https://codeforces.com/contest/1704

뻘짓을 조금 많이했다.

보니까 5솔로 2150 ~ 2600퍼포까지 받을 수 있었는데 A를 1번 틀리고 E에 개뻘짓해서 2350.

 

A. Two 0-1 Sequences

 

맨 앞부분만 바꿀 수 있다.

따라서 a의 뒷부분 끝이 b와 같아야 하고 (1번째 자리 제외) 나머지 부분에서 b[0]를 가지면 된다.

 

B. Luke is a Foodie

 

단순하게 앞에서부터 최대한 새로운 v값이 필요없도록 해주면 된다.

mini, maxi를 저장해주어서 이 둘이 2 * x를 넘지 않도록 구간을 잘 나눠주면 된다.

 

C. Virus

 

우선 마을들을 infect된 마을들을 기준으로 m개의 조각으로 나눌 수 있다. (처음에는 clean한 마을들의 연속)

그렇다면 크기가 큰 마을부터 최대한 살려내면 된다.

당연히 양끝을 protect하는게 제일 이득이 되는 방법이다.

https://codeforces.com/contest/1704/submission/166360691

 

D. Magical Array

 

sum(a[i] * i) 값이 operation 1에서는 변하지 않고, operation 2에서는 1 증가한다.

 

E. Count Seconds

 

문제를 잡고 80분 동안 실제로 어떤 식으로 나눠주게 되는지 구현하였다.

https://codeforces.com/contest/1704/submission/166389906

게다가 a_x < 0이 되는 경우도 있다고 문제를 잘못 읽어서 구현도 상당히 빡셌다. 

 

WA를 받은 후 최대한으로 나눠주게 된다면 2^N * MAXA 까지 가능하다는 것을 알게 되고 새 풀이를 고안했다.

사실 문제가 되는 부분은 a_x > 0 이였다가 a_x = 0이였다가 다시 a_x > 0이 될 수 있다는 것이다.

하지만 관찰을 통해서 a_x = 0이였다가 a_x > 0이 되는 시기는 n보다 작다는 것을 알 수 있다.따라서 1000 + 10번은 그냥 단순구현하고 그 이후는 모두 a_x > 0 이었다가 a_x = 0이 되지 않는다고 가정하면 된다.그러면 1000 + 10번의 쉬운 단순구현 + 간단한 DAG DP.

 

F. Colouring Game

 

라운드 중 생각한 것) 이 게임은 당연히 RB를 동시에 흰색으로 칠하는 것이 유리하다.연속한 RB의 개수를 일단 모두 세서 vector에 넣어주자.R과 B의 개수가 같은 상황에 한하여 여기서 ALICE와 BOB이 게임을 한다고 생각해도 무방하다.-> 조금 애매하지만 이 둘은 거의 같은 행위를 할 수 있고 (어차피 RB를 지우려고 할 것이기에)-> RB를 더 이상 지울 수 없는 사람이 손해를 본다.

 

이쯤 생각해내고 그런디를 이용하여 풀기에 시간이 부족하다고 느꼈다.어차피 Alice는 어떻게든 1번 더 하려고, Bob는 똑같은 횟수를 하려고 한다.즉 Alice는 횟수를 홀수로 맞추고 싶어하고  Bob는 짝수로 맞추고 싶어한다.-> 적당한 전략을 구사하면 혹시라도 가능하지 않을까라는 생각으로 대충 코딩하여 WA

 

editorial)위에서 언급한 게임은 그런디 게임이다.

이제 수식은 G(n) = mex(G(i) ^ G(n - 2 - i))이다. 

왜냐하면 한번의 행위는 G(i)와 G(n - 2 - i)로 쪼개버리기 때문이다.

이것을 굴려보면 34를 주기로 숫자들이 나온다는 것을 알 수 있다.

-> 따라서 nim_Value를 생각보다 쉽게 구할 수 있고, 답을 구할 수 있다.

 

주기가 34라는걸 그냥 발견해야한다니 이거 참 마음에 들지 않는다

뭐 게임 문제들이 다 이런 모양이긴 한다지만...

https://codeforces.com/contest/1704/submission/166381484