[2020-09-20] Codeforces Round 659 (Div.1)
좀 잘된다 싶더니 바로 거하게 말아먹었다. 오늘 문제는 내가 유독 약한 쪽이기도 했고.. 뭔가 실수라거나 말려서라기보단 그냥 실력 부족인 것 같다. 케이스 분석 능력이 항상 엄청 떨어지는데 이런건 어떻게 해야 키울 수 있는지 잘 모르겠어.. A. String Transformation 1 각각의 알파벳을 그래프 상에서의 노드로 보고, 알파벳 x에서 y로 변환이 필요한 경우 x -> y 엣지를 만들어주자. 이 경우, 항상 x < y 이기 때문에 만들어지는 그래프는 DAG이고, 각각의 weakly connected component에서는 항상 (그 컴포넌트 크기 - 1) 만큼의 변환을 하면 원하는 변환을 모두 할 수 있게 된다. 따라서, 이렇게 그래프를 구성한 후 wcc 기준으로 (크기 -1)을 전부 구해서..
[2020-09-19] Codeforces Round 658 (Div.1)
오늘도 잘 쳤다. 약간의 실수가 아쉽지만, 이거는 할만한 실수였던 거 같다. A를 좀 더 빨리 풀만했는데 시간을 많이 써서 이것도 조금 아쉽다. D를 좀 더 고민해볼까 했는데 좀 지쳐서 그냥 문제만 읽고 컷했다. 근데 되게 재밌어 보이는 문제여서 나중에 따로 시간 잡고 풀어봐야할 듯. 큐에 넣어둬야지 A. Prefix Flip Easy / Hard가 나뉘어 있는 문제였는데 그냥 바로 A2 풀었으니 A2를 기준으로 풀이를 쓴다. prefix를 통째로 뒤집는거니 맨 마지막 칸부터 순서대로 맞추면서 앞으로 온다고 생각하고 보자. 양쪽의 맨 오른쪽 끝 위치 칸이 같으면 그냥 한 칸씩 당겨주면 된다. 값이 다른 경우가 문제인데, 여기서 경우를 나눌 수 있다. 1. 현재 남은 구간에서 맨 왼쪽 끝 위치 값이 만들어..
[2020-09-18] Codeforces Round 647 (Div.1)
이제 진짜 원래 폼은 회복한 것 같다. 대충 해결 가능한 문제들은 다시 빨리, 정확하게 풀게 됐음. 이제 실력 향상을 위해 업솔빙을 열심히 해야 할 때.. B를 빨리 푼 건 굉장히 좋았던 듯. 구현 정확도가 상당히 많이 올라간 것 같다. A. Johnny and Contribution 토픽 번호가 가장 작은 것부터 순서대로 방문해야 함은 명확하다. 이제, 이렇게 순서대로 방문했을 때 각 블로그에서 조건을 만족하는지 아닌지 여부를 빠르게 판단할수만 있으면 된다. 이를 간단히 처리할 수 있는데, 각 블로그별로 현재 mex값을 mex[b] 라고 하자. 어떤 블로그 k에 토픽 x로 글을 썼다면, 그 k의 모든 이웃 i에 대해 mex[i] == x인 경우 mex[i]를 1늘려주면 된다. 중간 과정에 이 mex[i..