문제 난이도 미쳤네. 정해를 드디어 찾은거 같은데 이건 뭐 문제 푸는 사람보고 서커스 하라고 하는거 같습니다. 입력으로 각기 3개의 서로 다른 숫자를 가진 M개의 엔트리가 주어지는데, 그 중 겹치는 숫자가 하나도 없으면 무조건 해가 나올 수 없고 두 개 이상이면 무조건 해가 나오게 된다는 사실을 이용해 모든 엔트리에 하나의 숫자가 겹치는 경우에 대해서만 답을 찾도록 문제를 변형시키는게 첫 걸음입니다. 그 후 만약 M개의 엔트리에서 최대 총합 2개의 숫자를 제하여 각 엔트리에서 오직 하나의 숫자만 선택 될 수 있는지 여부를 확인하면 되는데, 여기서 사람들은 이제 문제를 다 풀었다 착각할 수 있습니다. 착각입니다. 나이브하게 완전탐색을 시도하면 최악의 경우 O(M^3)의 시간복잡도가 나오게 됩니다. 그래서 관찰을 더 해보면, 각 엔트리에 중복되는 수를 제하면 각기 2개의 숫자를 가지게 되는데, 여기서 숫자를 노드로 그리고 두 숫자를 포함한 엔트리를 엣지로 하여 그래프를 만들 수 있음을 알게 됩니다. 그리고 그러한 그래프에서 모든 분절점을 찾아 biconnected component로 분할할 수 있고, 그리 분할한 bc에 대해 분할정복을 할 수 있습니다.작성자메가스콤네노스작성시간22.08.22
주말 동안 타르코프와 에펙을 했는데, 에펙하면서 하루만에 실버 2에서 골드까지 쭉 올라갔다. 저번 시즌에 머리가 깨진 사람들이 이번 시즌 랭크를 포기해서 하는 사람들만 남아서 그런 것인지 평균적으로 중간 언저리 쯤에서 하는 애들 정도는 만나는듯.작성자Khrome작성시간22.08.22
생각해보면 가계도도 트리입니다. 모종의 두 사람 사이 촌수를 계산하고 싶다면 그 사이 경로의 길이를 구하면 됩니다. 근데 모든 가계도가 트리일 수는 없습니다. 근친은 사이클을 만들고 트리는 사이클을 가질 수 없기 때문입니다. 이 경우 가계도는 그래프가 되는데, 그러면 이 경우 두 사람 사이 촌수는 트리에서의 노드 간 거리가 아니라 그래프에서의 노드 간 거리를 통해 구해야합니다.
근친이 없다는 전제하에, 나의 부모의 형제가 삼촌인 이유는 명확합니다. 부모와 나 사이에 하나의 엣지가 있고, 부모와 부모의 부모 사이 하나의 엣지가 더 있고, 부모의 부모와 부모의 부모의 자식, 즉 부모의 형제 사이에 다시 하나의 엣지가 더 있고, 트리에서 모든 경로는 최단경로이니 이것이 곧 거리가 됩니다. 따라서 나의 부모의 형제는 나와 삼촌 관계가 됩니다.
하지만 나의 부모의 형제만이 나에게 삼촌이 되는건 아닙니다. 나의 형제의 자식 역시 나에게 삼촌이 되고, 나의 부모의 부모의 부모 역시 삼촌이 되고, 나의 자식의 자식의 자식 역시 삼촌이 됩니다. 만약 결혼을 통한 연결 역시 유효하다 가정하면, 나의 자식의 배우자의 부모 역시 삼촌이 됩니다.작성자메가스콤네노스작성시간22.08.19
으허허허. 이기기 위해 자기 자신을 속이는 사람들은 뭔가 안 부끄럽나. 이전에 했던 발언이 새록새록 뇌리 한 구석에 남아 있는데 잊어먹으리라 생각했나. 마치 자신은 그런 일 했던 것 없는 척마냥 뻔뻔하게 입 놀리는 것을 보면 이 친구를 어떻게 해야 하나 싶습니다. 사람들은 절대 바보가 아닌데. 요즘 들어서 제가 예민해진 건지 아니면 못된 사람들만 봐서 그런 건지 매사 부정적인 인간이 되버리네요. 안되는데. 학교 공부 때문인지도 모르겠네요.작성자달녘작성시간22.08.19