#705 div2 03/06

codeforces.com/contest/1493

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

 

 

A 

 

합이 k가 되게 하는 두 수 중에서 더 작은 것만 계속 제외시키면 결국 합이 가장 커지게 된다. 

처음에 바로바로 출력시키는 방법으로 하려다가 갯수까지 출력해야 해서 벡터로 바꿈 

 

7분 솔브

 

B 

 

매우 짧은 -> 매우 긴 디스크립션으로 바뀌어서 좀 당황을 하였다.

 

그냥 구현문제 

처음에는 뭐 다른게 있을까 생각을 하였지만 떠오르지 않았고 그냥 1씩 증가하면서 구현을 하였다. 

 

42분 솔브

 

C 

 

이때 처음으로 스탠딩을 봤는데 친구 중 C를 아무도 못 풀었길래 좀 많이 쫄고 들어갔다. 

 

n길이의 문자열 s에서, 사용된 문자들만 사용해서 s보다 사전식 순서가 같거나 뒤인, 그 중에서 사전식 순서가 가장 빠른, 쓰인 문자들의 갯수가 모두 k로 나누어 떨어지는 문자열을 출력하는 문제

 

보다보니깐 a->b로는 무조건 가능 그러니깐 사전식 순서가 빠른거에서 느린거로 변경은 가능, 

느린거에서 빠른거로 변경은 불가능 이 아이디어를 이용해서 

cnt[]를 뒤로 넘기는 방식으로 구현을 했지만 abcd에서 bbdd가 나와서 문제점을 찾았다. 

 

30분정도 남은 상황이었고, 다시 생각을 해보았다. 

 

이번 관찰은 무조건 s의 상황을 따라가다가, 어느 index에서 그 index의 문자보다 더 큰 문자로 변경을 한다면, 그 뒤에꺼는 아예 상관없다는 관찰이었다. 

 

그래서 26가지의 알파벳에 대해서 N의 길이만큼 변경을 했을때, 변경이 가능한지에 대해서 조사를 하고, 가능하면 그 중에서 가장 빠른걸로 조합을 짜면 되겠다 싶었는데 사실 구체화된 생각도 아니고, 구현도 꽤 까다로울 것 같아서 남은 시간을 그냥 보냈다. 

 

-----------------------------------------------------------------------------------------------------------------

3/15

위에서 생각한 아이디어를 이용하기는 했는데 구현이 생각보다 빡셌다. 아니 구현까지 가는 생각이 빡세다고 해야하나 

생각을 구체화하는 연습이 아직 더 많이 필요할 것 같다. 

 

------------------------------------------------------------------------------------------------------------------

D 

 

일단 C가 매우 어렵다는 사실, D를 푼 사람이 Green55님 밖에 없었다는 사실에 매우 대충 봤다. 

지금 다시 보니깐 어차피 계속해서 1이상의 값이 곱해지는 것이니깐, 그 전에 있던 소인수는 변할게 없고, 추가되는 소인수만 생겨난다. 따라서 추가되는 소인수 중 min으로 변화가 생기는거 뭔가 해보면  뭔가 가능하지 않을까 생각을 한다. 

 

운이 좋게 스피드코포가 되어서 처음으로 민트를 갔다. 열심히 해보자