#686 div3 11/24

codeforces.com/contest/1454

Dashboard - Codeforces Round #686 (Div. 3) - Codeforces

 

시작 전에 유튜브를 보다가 시간을 확인해보니깐 38분이길래 호다닥 접속해서 시작하였다. 이때 잘까 할까 두가지 생각이 있었는데 오랜만에 코딩을 하는거고, 또 오늘 이거 하고나서 공부를 다시 해야겠다 생각한거였기 때문에 그냥 고

 

A 

 

index에 있는 수가 index와 다르게 수열을 만드는 것인데 그냥 +1 한 상태로 나열을 하면 될 것같아서 그렇게 구현을 하였다. 근데 +1 과 %를 사용해서 맞추는게 생각보다 까다롭게 느껴져서 하나하나 해보면서 짜느라 좀 늦었다. 

 

8분 솔브

 

B

 

여기서 좀 많이 당황을 했던게 일단 구현을 어떻게 해야할지에 대해서 생각이 쉽게 떠오르지 않았다. 

하나만 존재하는 수중에 가장 작은 수의 인덱스를 출력하는 문제인데, priority_queue를 사용할까 set를 사용할까 생각을 하였다. 

 

근데 pq를 사용하려니깐 문제가 발생하는 것을 인지하였고, set를 사용하려고 하니깐 이것도 좀 아닌것 같아서 그리고 div3 B인데 이럴까 싶어서 다른 방법을 생각하였다 

 

처음에는 수들의 최대가 평소처럼 메모리 초과나는 수인지 알고 그렇게 안했었는데 

문제 조건에 수들의 최대가 n인걸 확인하였고 배열을 만들어도 메모리가 괜찮을 것 같아서 갯수를 +해서 가장 작은 것부터 조사하면 될 것이라고 구현했지만,, 

 

TLE가 발생하였다. 

 

알고보니 대충 벡터를 선언할때 vector<int> v(number); 이런식으로 선언하면 0으로 초기화 하느게 대충 O(number)의 시간이 걸리는것같았다 왜냐하면 벡터의 크기를 줄여주니깐 TLE가 없어졌다.

 

48분 솔브

 

C

 

B에서 조건이 그대로이길래 생각보다 방법은 쉽게 찾았다 그냥 나오는 횟수를 계산하는 방법으로 하면 될것같았다 하지만 구현은 오래걸렸고 또 구현해서 제출했더니 계속 프리텟2에서 막혔다. 

 

...반례를 아무리 찾아도 없길래 설마 RTE나야하는데 안 나는것일까 해서 벡터 크기도 바꾸고 했지만 그건 아니었다. 

아무리 해도 안되길래 D로 넘겼다.

 

D

 

방법은 쉽게 찾았다 그냥 소인수분해 문제였다 n의 범위가 10^10이었으므로 sqrt(N)의 소인수분해가 필요하다고 생각하였고, 얼마전에 div2 C에서 sqrt(N)의 소인수분해를 몰라서 틀린 문제가 있었기 때문에 이번에는 구글링 한번만에 이해를 하고 구현을 할 수 있었다. 

 

그렇게 했지만 또 걸렸고.. 

 

보니깐 소인수분해를 하면서 나눈 수를 마지막에는 온전한 것처럼 사용하고 있었다.

바보가 아닐까 

 

1시간 48분 솔브

 

C

 

아니 근데 다른 케이스를 계속 작성해서 넣었었는데 뭐가 다른지에 대해서 생각을 안하고 무작위로 넣어서 모두 같은 종류의 케이스를 넣은게 아닐까 생각한다. 

뭐가 다른지에 대해서 생각해도 아마 똑같이 몰랐겠지만 

 

 

685div2는 편두통이 심해져서 쉬었었다. 그런 김에 좀 휴식을 취했었는데 카페도 못가고 이제 아마도 당분간은 집에서 공부하지 않을까 싶다 집에서는 공부가 안되는데 ..