돌이 코딩하는 방

이 문제는 굉장히 어렵고 이 글에는 강력한 스포(풀이의 전체)가 있다. 2주가 넘는 시간동안 이 문제에 정말 많은 시간을 쏟아서 만들었다. 문제에 대해서 많은 고민을 해본 후에 이 풀이를 봐주셨으면 좋겠다. 더보기 일단 가장 먼저 발견해야하는 것은 게임판에 "유리도"라는 개념을 부착하는 것이다. 이 게임판이 A,B 둘 중 누구에게, 얼만큼의 유리함을 가져다 주는 지에 대한 값으로 정식 명칭은 아니지만 "유리도" 라고 부르려고 한다. 솔직히 아무것도 모르는 상태에서 "유리도"를 생각하는 것은 정말 말도 안되는 일이고, 따라서 판 뒤집음, 구간 게임판 사용등으로 한 게임판을 수치화 시켜야 된다는 일말의 힌트를 남겨놓긴 하였다. 이 게임의 가장 큰 특징은 내가 턴을 넘기면 무조건 이득이다. 절대로 턴을 넘겨서..

제가 한동안 포스팅을 하지 못한 이유를 드디어 공개하네요. 일정이 빡빡하여 진행이 힘들 수도 있어서 미리 글을 쓰지는 못했는데, 거의 5.16에 하는 것이 확정된 듯 싶습니다. 최근에 좋은 대회가 많았어서 부담이 좀 많이 되지만 좋은 검수자님들을 많이 둔만큼 좋은 결과를 뽑아내기 위해서 최선을 다해보려고 합니다!! 5.16에 Semi-Game Cup으로 돌아오겠습니다!! 제가 백준에 쓴 Semi-Game Cup 홍보 게시물 링크입니다. https://www.acmicpc.net/board/view/50953

4/16 만들고 싶은 문제는 있는데, BOJ stack 권한이 없었다. 대회를 한 번 만들어 볼까? 라는 이야기를 Blackking26과 나눴다. 게임 문제들 모아서 대회를 열어보라는 말도 조금 들어본 적이 있어서 관심이 생겼다. 4/19 흥분되었다. 생각보다 재미있었고, 아이디어는 가지고 있던 것들이 꽤 많이 나왔다. 사람들도 열심히 모았고, 어느정도 구체화 시켜서 개최 요청 메일을 보내드렸다. 현재까지 만들어진 문제는 왕들의 외나무다리 돌게임, NDSR 게임, 돌 술래잡기 게임, 고인물의 리듬게임, ㄱ 폭탄게임이다. 고인물의 리듬게임은 훌륭한 대장장이 gs18115님에 의해서 강화가 될 예정으로 기초 단계만 만들어 놨고, ㄱ 폭탄 게임은 최근에 엄청난 대회 퀄리티 때문에 부담감을 가져서 풀이 없이 문..

한동안 PS도 별로 안하고 있고 블로그 글도 안 쓴지 좀 된 것 같다. 한동안 이쪽에 시간투자를 아예 안하고 있다. 사실 못하고 있다고 보는 것이 맞을 것이다. 시간을 쏟아야 할 다른 곳이 생겼기 때문이다. 조만간 그곳에 시간을 좀 더 쏟은 후 좋은 소식으로 다시 돌아오려고 한다. 앞으로 조만간은 계속 포스팅 양이 확 줄 예정이다...

문제 링크 : https://www.acmicpc.net/problem/10067 문제 소개 길이 n의 수열을 k번 자른다. 자를 때 마다, 자른 후 양쪽 수열의 값의 각각의 합을 곱한 것만큼 점수를 얻는다. 이때 얻을 수 있는 최대 점수와 자르는 방법을 구하시오. 문제 풀이 우리는 이 문제를 최종 시점관점에서 보면서 점수에 어떤 값을 이 추가되었는지를 살펴보아야 한다. (a,b,c,d)를 (a,b),(c,d)로 잘랐다고 하자. 이러면 우리는 (a+b)*(c+d)의 점수를 얻게 된다. 이를 다른 식으로 풀어쓰면 ac+ad+bc+bd 만큼의 점수를 얻게 된다는 것이다. 이는 서로 다른 그룹에 속하는 임의의 두 값을 곱해서 더한 값이다. 결국 그전에 어떤 순서로 어떻게 잘랐건 간에, 마지막에 다른 그룹에 있..

문제 태그: https://www.acmicpc.net/problem/7578 문제 소개 2열에 걸쳐 N개의 숫자가 주어진다. 윗줄과 아랫줄에 한쌍의 같은 숫자가 선으로 연결되어있다. 교차되는 선의 쌍의 수를 구하시오. 문제 풀이 일단 같은 숫자끼리 (a,b)의 쌍을 만들어서 생각해보자. 우리는 N개의 (a,b)를 얻을 수 있으며 그중에 i,j 에 대해 $a_{i} b_{j}$ 또는 $a_{i} > b_{i}, a_{j} < b_{j}$를 만족하는 쌍의 갯수를 구하면 된다. 한 쌍의 두 값에 대해서 순서가 바뀌어있는 갯수를 세는 문제이며, 이를 흔히 inversion counting 문제라고 불린다. inversion counting 문제는 merge sort 혹은 se..

문제 태그 : https://www.acmicpc.net/problem/2357 문제 소개 N개의 숫자들이 주어지고 쿼리가 주어진다. 쿼리가 a,b가 주어지면 a번째 숫자부터 b번째 숫자 사이의 최솟값과 최댓값을 구해야 한다. 문제 풀이 지금은 N개의 숫자들이 바뀌지는 않지만, 아무튼 구간의 최댓값과 구간의 최솟값은 Segment Tree를 사용함으로써 한 번 구하는 데 $O(lgN)$에 구할 수 있음이 잘 알려져 있다. 구간합을 구할 때 구하고자 하는 구간에 포함되어지지 않는 노드는 0을 반환한다. 항등원이기 때문이다. 같은 이유로 최솟값 세그트리에서는 항등원인 inf를 반환해야 하고, 최댓값연산에서는 항등원이 -inf이므로 구간이 포함되어지지 않으면 -inf를 반환해야 한다. 코드 1 2 3 4 5 ..

문제 태그:https://www.acmicpc.net/problem/1761 문제 소개 간선의 길이가 있는 트리가 주어지고, 두 정점이 계속해서 주어지면, 그 두 정점사이의 거리를 계속 답하면 된다. 문제 풀이 LCA의 성질을 이용하면 쉽게 이 문제를 해결할 수 있다 a와 b의 LCA를 c라고 했을 때, a와 b사이의 거리는 a와 c사이의 거리+b와 c사이의 거리이다. 하지만 이것도 두 정점사이의 거리이므로, 좀 더 쉽게 이 문제를 해결하기 위해서 관점을 바꾸어보면, a와 b사이의 거리는 루트에서 a까지의 거리+루트에서 b까지의 거리- 2*루트에서 c까지의 거리이다. 우리는 dfs를 돌리는 과정에서 루트에서 어떤 정점까지의 거리를 쉽게 구할 수 있다. 또한 LCA는 이글에 따르면 전처리 과정 $O(Nlg..

LCA란? LCA는 Lowest Common Ancestor의 약자로 해석하면, 최소 공통 조상(가장 낮은 공통 조상)이라는 뜻을 가지고 있다. '조상'이기 때문에 트리에서 사용하며, 다양한 특징을 가지고 있어 트리 문제를 해결할때 기초로 잘 사용되어진다. 트리에서는 조상이 존재한다. 어떤 노드의 부모, 부모의 부모, 부모의 부모의 부모해서 루트까지의 모든 노드를 조상노드라고 하며, 공통 조상은 2개의 노드들에 대하여 어떤 노드가 그 두 노드의 공통적으로 조상일때를 말한다. 그러한 공통 조상들 중에서 가장 낮은 (깊이가 깊은, 처음 만나는) 공통조상이 최소 공통 조상 즉 LCA가 된다. 위와 같은 트리가 있다고 할 때 LCA(9,10)=4, LCA(9,11)=2, LCA(5,9)=2, LCA(12,13)..

문제 링크 : https://www.acmicpc.net/problem/1226 문제 소개 어떤 당이 빠져도 합이 과반수가 안되는 집합을 깔끔한 연합이라고 한다. 가장 큰 크기의 깔끔한 연합을 구하여라. 문제 풀이 가장 큰 크기의 깔끔한 연합을 구하는 것이 아니라 관점을 바꾸어서 크기가 K인 깔끔한 연합이 존재하는 지에 대해서 구해도 된다. 모든 값에 대해서 다 가능성을 구해주면 된다. 일단 기본적으로 몇 개의 값의 합이 K가 되어야 한다. 합이 K가 되는 여러가지 방법중 깔끔한 연합이 될 확률이 가장 높은 것은 것은 연합내의 가장 작은 값이 커야 한다는 것이다. 가장 작은 값만 빼더라도 과반수가 안되면 깔끔한 연합이라고 할 수 있고, 그러기 위해서는 연합내 가장 작은 값이 커야한다. 따라서 N개의 숫자..