jwvg0425 Problem Solving

오늘도 망했다. C를 대회 끝나고 30초 뒤에 제출해서 맞았고.. B는 풀지를 못했다. 왜 B같은 유형은 도저히 풀리질 않을까.. 잘 풀리다가 다시 연속으로 말아먹으니 멘탈이 너무 깨진다. A. Multiples of Length 어떤 수에 (x+1)을 더하면 x로 나눈 나머지는 1만큼 증가한다. 따라서, 전체 구간(1 ~ n)을 잡고 (n-1)로 나눈 나머지가 0이 되게 전체 값을 조정해준다. 그 다음 1 ~ n -1 / 2 ~ n 구간을 잡고 전체 값이 0이 되게 만들면 문제를 해결할 수 있다. n = 1일때 예외를 잘못 처리했다가 한 번 틀렸다. 이런 실수 하면 안 되는데.. B. Stoned Game 이런 식의 케이스 분석 기반의 게임 문제는 도저히 풀지를 못 하겠다. 나올 때마다 못 푸는 듯. ..

오늘도 말아먹었다. 흠.. A번에서 멍청한 실수 두 번한 건 아쉽긴 한데, B 못푼 건 그냥 실력이어서 별로 할 말도 없다. 필요한 관찰 다 해놓고 못 풀었다.. 갈 길이 멀다. A. Boboniu Chats With Du 값이 m보다 큰 것과 그렇지 않은 것을 구분해보자. m보다 큰 값이 하나도 없는 경우 전체 합이 곧 답이 된다. m보다 큰 값이 하나라도 있는 경우, 그 개수를 c라고 하자. 하나를 고를 때마다 최대 d개의 다른 원소를 쓰지 못하게 할 수 있으므로, c개중에 (c + d) / (d + 1)개는 반드시 답에 포함이 되어야 한다. 이 값을 x라고 하자. m 보다 큰 걸 x ~ c개 쓰는 각각의 경우에 대해 값을 구해서 그 중 최댓값을 취하면 된다. 이 때 c개 중 k개를 쓴다고 가정했을 ..

좀 잘된다 싶더니 바로 거하게 말아먹었다. 오늘 문제는 내가 유독 약한 쪽이기도 했고.. 뭔가 실수라거나 말려서라기보단 그냥 실력 부족인 것 같다. 케이스 분석 능력이 항상 엄청 떨어지는데 이런건 어떻게 해야 키울 수 있는지 잘 모르겠어.. A. String Transformation 1 각각의 알파벳을 그래프 상에서의 노드로 보고, 알파벳 x에서 y로 변환이 필요한 경우 x -> y 엣지를 만들어주자. 이 경우, 항상 x < y 이기 때문에 만들어지는 그래프는 DAG이고, 각각의 weakly connected component에서는 항상 (그 컴포넌트 크기 - 1) 만큼의 변환을 하면 원하는 변환을 모두 할 수 있게 된다. 따라서, 이렇게 그래프를 구성한 후 wcc 기준으로 (크기 -1)을 전부 구해서..

오늘도 잘 쳤다. 약간의 실수가 아쉽지만, 이거는 할만한 실수였던 거 같다. A를 좀 더 빨리 풀만했는데 시간을 많이 써서 이것도 조금 아쉽다. D를 좀 더 고민해볼까 했는데 좀 지쳐서 그냥 문제만 읽고 컷했다. 근데 되게 재밌어 보이는 문제여서 나중에 따로 시간 잡고 풀어봐야할 듯. 큐에 넣어둬야지 A. Prefix Flip Easy / Hard가 나뉘어 있는 문제였는데 그냥 바로 A2 풀었으니 A2를 기준으로 풀이를 쓴다. prefix를 통째로 뒤집는거니 맨 마지막 칸부터 순서대로 맞추면서 앞으로 온다고 생각하고 보자. 양쪽의 맨 오른쪽 끝 위치 칸이 같으면 그냥 한 칸씩 당겨주면 된다. 값이 다른 경우가 문제인데, 여기서 경우를 나눌 수 있다. 1. 현재 남은 구간에서 맨 왼쪽 끝 위치 값이 만들어..

이제 진짜 원래 폼은 회복한 것 같다. 대충 해결 가능한 문제들은 다시 빨리, 정확하게 풀게 됐음. 이제 실력 향상을 위해 업솔빙을 열심히 해야 할 때.. B를 빨리 푼 건 굉장히 좋았던 듯. 구현 정확도가 상당히 많이 올라간 것 같다. A. Johnny and Contribution 토픽 번호가 가장 작은 것부터 순서대로 방문해야 함은 명확하다. 이제, 이렇게 순서대로 방문했을 때 각 블로그에서 조건을 만족하는지 아닌지 여부를 빠르게 판단할수만 있으면 된다. 이를 간단히 처리할 수 있는데, 각 블로그별로 현재 mex값을 mex[b] 라고 하자. 어떤 블로그 k에 토픽 x로 글을 썼다면, 그 k의 모든 이웃 i에 대해 mex[i] == x인 경우 mex[i]를 1늘려주면 된다. 중간 과정에 이 mex[i..

AB는 빨리 잘 풀었는데 C를 한참 고민하고 못 풀었다. 이제 정확도, 속도는 어느 정도 돌아온 것 같다. 이제 업솔빙으로 못푸는 문제의 컷을 높이는게 필요할 듯. 문제를 다양하게 풀어보자.. A. Unusual Competitions (는 +1, )는 -1로 두고 값이 음수로 내려가는 시점부터 0이 되는 순간까지 구간의 길이를 모두 더해주면 된다. 이러한 구간은 전부 조정이 필요한데 마지막에 합이 0이 됐으면 잘 조정해서 음수가 아예 나오지 않게 만들어줄 수 있기 때문이다. B. Present 가장 작은 수에 해당하는 비트부터 순서대로 0,1,2,3..., b로 번호를 붙여보자. 덧셈을 했을 때 어떤 x번 비트의 값에 영향을 줄 수 있는 건 0...x번 비트까지다(즉, x+1번 비트 이후는 필요가 없다..

ABC는 빠르고 정확하게 풀었는데 D를 90분이나 시간이 있었음에도 못 풀었다. 심지어 풀이는 거의 10분만에 나왔는데.. 이런 류의 문제를 항상 잘 못 푸는 것 같다. 풀이를 좀 더 깔끔하게 생각을 하든, 구현을 좀 더 잘 하든 둘 중에 하나는 해야하는데. 오늘 업솔빙까지 끝내고 싶었지만 너무 피곤해서 D 업솔빙은 내일로 미룬다. AC 받고 나서 풀이 업뎃해야지 이 사이트 퍼포먼스를 좀 짜게 주는 것 같다. 본 대회에서 나랑 비슷한 점수 기록한 사람이 오렌지에서 레드까지 레이팅이 올랐던데? 그러면 이것도 퍼포먼스 수치가 레드 언저리여야하는 것 아닌가... 흠... 일부러 가상 참가는 약간 과소평가하게 만들어놓은건가 싶기도 하고. A. Journey Planning 가끔 보이는 종류의 문제. 각각을 하나..

A에서 좀 헤맨게 아쉽지만 그래도 B,C는 깔끔하게 푼 것 같다. D는 풀이를 생각했음에도 불구하고 시간복잡도가 안 된다고 생각해서 시도를 안했다.. 이게 너무 아쉽다. O(N^5)가 안 된다고 생각해서 O(N^4)로 어떻게 줄여야할지를 한참 고민했는데, 생각해보면 O(N^5)는 맞는데 쌩 N^5가 아니라 상수가 많이 줄어서 충분히 할만하다. 이걸 마지막에 시도라도 해봤어야 했는데 시도를 왜 안 했을까.. 정확하게 / 타이트하게 판단하지 않고 적당한 경험에 의거해서 대충 판단하는 것도 나쁜 습관인 것 같다. 2100 초반에서 수렴하는 중.. 정말 바닥을 치고 있다... D를 풀었으면 꽤 올랐을만한 상황이었는데 시도를 안한게 너무 아쉽다. 끝나고 짜서 제출해보니 바로 맞던데 흑흑 A. MP3 서로 다른 수..

이제는 뭐 기대를 하면 안 될 것 같애.. 조만간 퍼플로 내려가겠다. A1. Add on a Tree 문제를 잘 정리해보면, degree = 2 인 노드가 하나라도 있으면 불가능하다. degree 2인 트리에서 양쪽 리프를 하나씩 잡으면 해당 두 엣지에 항상 같은 값이 추가되는데, 이 때문에 이 양쪽 엣지에 다른 값이 들어가있는 경우 생성이 불가능. A2. Add on a Tree: Revolution B가 수식을 잘 조정해서 푸는 문제였는데 못 풀겠어서 A2만 한참을 붙잡았다. 근데 못 풀었다.. 문제에서 주어진 조건을 좀 더 잘 활용해서 유연하게 생각했어야 했는데 그걸 못 했다. 왜 이렇게 생각이 빨리빨리 안 돌아가는지.. 모든 값이 짝수 / 서로 다르다는 점을 생각해보자. 모든 엣지에 들어가있는 값..

끝을 모르고 내려가는 중이다. 문제가 내가 많이 약한 부분에서 나왔다고 위안이라도 하고 싶지만.. 애초에 이 난이도 범위에서 약한 파트가 있다는 것 자체가 아쉽다. 뭐가 나와도 빠르고 정확하게 잘 풀어야지. A에서 코딩 실수한 건 반성해야 할 부분일 듯. B도 냄새는 맡았는데 빠르게 접근을 떠올리지 못한게 아쉽다. C는 못 풀었을 것 같은데, 이 비슷한 발상에서 내가 좀 약한 것 같다. A. Increasing by Modulo 답이 최대 M이라는 사실은 비교적 쉽게 도출할 수 있다. M번 돌면 모듈러한 모든 값을 다 만들어줄 수 있고, 더해줄 때 한 번에 여러 인덱스를 묶어서 더해줄 수 있으니 M번보다 많이 더해줄 이유가 없다. 따라서, 0 ~ M 사이에서 parametric search를 이용해 답이..