Codeforces Round 1099 (Div. 2)

트리플에스보러 카이스트축제 놀러갔다가 엘마가서친구가사주는칵테일마시고 취했는데 기차에서 노트북으로 코드포스를 켜서 A번을 제출해버리는 실수를 한 후에 -104가 됨

 

A

생략

여담: 사실 2분만에 풀었는데 그때딱 기차가도착해서 기차타서 가방 치우고 노트북폈는데 와이파이연결개억까당해서 9분에제출함

 

B

대충 2개의 bucket을 만들어서, a[i]>a[i+1] 이면 a[i+1]에 k를 무조건 더해야만 하니까 k를 더하는 버킷으로 보내면될거같음 근데 예제가 안도는걸보니 반례가 있는듯

그뒤로 멀미나서 속이안좋아서 살짝 위기를 겪고 노트북덮고 20분정도잤음

.

B업솔빙

왜 못 풀었지 그냥 k를 max(지금까의 max값-a[i])로 고르고 앞에서부터 이 k가 되는지 안되는지를 확인하면 되는거아님?

귀찮아서 코드는나중에짬 (사실 정수론 과제해야됨)

 

C

다행히일어났더니더이상안토할것같아서 c를 봄 짝수면 나눠지고 홀수면 1을 더함

관찰1. 언젠가는 2^n 꼴에 수렴해서 1이 될거고 1→2→1→2→ ... 가 반복됨

관찰2. 그러면 이 경로에 있는 수 중에서 수에 도달하는 스텝수를 계산해서 n개에서 다 나타나면서 스텝수가 최소가 되는 걸 구하면 됨

관찰다했는데 최적화를 제대로 못해서 틀린게개아쉽다 아직 짬이더차야하는듯

.

C업솔빙

관찰1의 '사이클'에서 1로 끝나는 경우랑 2로 끝나는 경우를 나눠서 생각하면 되고

어차피 1 또는 2에서 시작하니까 사이클을 뒤집은다음에 그리디하게 모든 수가 만들어질 수 있을때까지 가면 됨 (페타쌤 풀이를좀참고했어요ㄱㅅㅎㄴㄷ)

예를 들어 예제의 [3, 6, 7, 16, 8, 8, 7]

3: 3 4 2 1 / cost 3, 7: 7 8 4 2 1 / cost 4

뒤집으면

1 2 4 3 6

1 2 4 8 7 이니까 4가 만들 수 있는 최선의 선택

공간이터지진않겠지? n 10^5 * path길이60 * 2 * 4bytes = 4.8*10^7 < 512*10^6 → ok 

 

AC

 

D 업솔빙 → 귀찮아서 나중에함