jwvg0425 Problem Solving

https://www.acmicpc.net/problem/12797 12797번: 연금술 첫 줄에 정수 n과 m(1 ≤ n ≤ 109, 1 ≤ m ≤ 103)이 공백으로 구분되어 두고 주어진다. 다음 줄에 a1, a2, ..., am (1 ≤ ai ≤ 109)이 공백으로 구분되어 주어진다. www.acmicpc.net 고생 고생 끝에 겨우 풀었다. 정리해둘만한 내용이 많은 문제인 것 같아서 풀이를 기록해 둠. 우선 점화식부터 유도해보자. $ DP(n, m) $ 을 $1 \dots m $ 번 까지의 재료를 써서 $ n $ 개 조합할 때 만들 수 있는 완성품 품질의 총합이라고 정의한다. 이 경우 $ DP(n, m) $의 점화식은 다음과 같이 세울 수 있다. $$ DP(n, m) = a_m \cdot DP(n..

오늘도 망했다. 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 가끔 보이는 종류의 문제. 각각을 하나..

인터랙티브 문제를 처음 접하면, 틀릴 때 도대체 왜 틀렸는지 모르겠는데 디버깅하는 방법도 알 수가 없어서 굉장히 헤매게 된다. 모든 인터랙티브 문제에서 사용할 수 있는 방법은 아니지만 인터랙터의 구현이 어렵지 않은 경우 쉽게 쓸 수 있는 코드 구조가 있어 간단히 정리해본다. 대부분의 인터랙티브 문제가 인터랙터 구현이 심플하기 때문에 이 방법만으로도 어지간해서는 로컬 디버깅을 어렵지 않게 할 수 있다. 인터랙터 흉내내기 인터랙티브 문제의 로컬 디버깅에서의 어려움은 일단 확실한 해결 방법이 하나 있다. 바로 문제에서 제시된 인터랙터(쿼리에 대한 응답을 하는 프로그램)를 그대로 로컬에 구현한 다음 이걸 이용해서 디버깅을 하는 것이다. 하지만 인터랙터를 별개의 프로그램으로 만든 후 이 인터랙터를 통해서 채점하는..

지난 번 팀연습도, 이번 팀연습도 생각보다 훨씬 퍼포먼스가 잘 나왔다. 문제 푸는 것도 매끄럽고 아주 좋다. 재밌다! 초중반에 몇 가지 아쉬웠던 점들이 있지만 뭐 아쉬운 점이 하나도 없는 대회는 있을 수가 없으니.. 아래는 타임라인에 따른 진행. 이번에도 내가 앞에서부터 읽고, xtalxlr님이 뒤에서, acka님이 중간을 읽었다. 00:30 I AC 초반에 상당히 멘붕이었다. 사람들이 푸는 문제들을 이것저것 봤는데 전부 다 어려워보이는데 이게 도대체 왜 풀리지 하는 느낌.. 일단 I, D가 제일 많이 풀려서 그걸 봤는데 둘 다 잘 모르겠었고.. 그 다음에 악어님이 E 풀어볼만할 것 같다고 하셔서 나는 E를 봤다. 그리고 E 대충 풀이가 나왔고, 그 사이에 xtalxlr님이 I번 풀이를 생각해서 AC. ..