버츄얼을 했는데, educational 한 셋이어서 풀이를 올려본다.
뭣 같은 에듀코포보다 훨씬 좋다.
https://atcoder.jp/contests/abc244
D.
문제 요약 !
RGB로 이루어진 순열 S와 T가 주어진다.
S를 T로 만들건데, S의 임의의 원소 2개를 골라서 swap하는 작업을 정확히 1e18번 해서 바꿀 수 있는지 구해라.
잘 알려진 문제이다.
S와 T의 inversion의 기우성에 따라 변하는데, segment tree등의 자료구조를 사용하면 O(nlogn)에 구할 수 있다.
근데 n이 3이다. 오버킬이다. 어떻게 할까?
이럴때는, 3C2가지 경우에 대해서 각각의 경우를 모두 따져주면 된다.
즉 S에서 R>G 였는데, T에서 R<G라면 cnt를 1씩 증가시켜 준다.
이런식으로 모든 쌍에 대해서 해준다.
cnt가 짝수라면 yes 아니라면 no 이다.
E.
문제를 요약:
그래프에서 S->T로 가는 path 중에서 경로의 길이(사이의 간선의 개수)가 정확히 K이면서, X가 짝수번 등장하는 path의 경우의 수를 구하여라.
문제를 처음에 잘못 읽어서, 경로의 모든 정점이 짝수번 등장해야 하는 줄 알고 엄청 어려운 문제인 줄 알았다;;;
그렇게 20분정도 날려먹고 예제를 보니까 x라는게 있어서 다시 이해했다.
풀이는 엄청 쉬운데, N<=2000,K<=2000인게 누가 봐도 dp이다.
dp[n][k][2]로 정의 하고 dp를 돌리면, k의 대소관계에 따라 살펴봐야 하는 dp값의 방향이 정해지기 때문에, dag라 풀 수 있다.
시간복잡도가 O(NKM)인걸로 착각할 수가 있는데, 시간복잡도가, 동일한 K에 대해서 간선을 최대 M번 보기 때문에 O(KM)이다.
따라서 O(N^2)으로 해결할 수 있다.
F.
문제 요약:
마찬가지로 그래프에서 경로를 찾을건데, 이제 N<=17이다.
경로를 아무거나 하나 찾으면, 각각의 정점이 홀수번 혹은 짝수번 방문했는지 2^N 가지 경우의 수가 있다.
따라서 우리는 이 2^N가지 경우의 수에 대해서 가장 경로의 길이가 짧은 것들의 합을 구하면 된다.
처음에 조금 해맸었는데, N<=17이라 완전탐색을 생각하고 있었다;
근데 완탐을 하기엔 조금 컸고, bit dp같은 것도 생각하고 있었다.
그래서 bit dp에서 아이디어를 얻었는데, 사실 이 문제는 bfs 문제였다.
bit 로 i번째 정점이 홀수번/짝수번 반복되었는지를 나타낼 수 있고, 동일한 bit에, 마지막으로 방문한 정점이 동일하다면 같은 상태이기 때문에 총 상태의 수는 2^N * N개이다.
따라서 시작 상태에서 bfs를 돌리면, 한 정점에서 간선은 최대 N개이기 때문에,
2^N*N*N인데, N=17이라 충분히 돌아간다.
재밌는 문제였다.
이 문제는 좋은 문제였다.
끝나고 10분 후에 풀었다 ㅠ.ㅠ
아마 E를 제대로 읽었다면 버츄얼 중에 풀었을 것 같다.
이번에는 그래프가 주어지고, 또 path를 찾을 건데, 각각의 정점이 홀수번/짝수번 방문되었는지가 주어진다.
이때, 방문하는 정점이 4N이하인 path를 construct 해서 출력해봐라.
문제의 아이디어는 한 20분정도 고민하고 발견했다.
그런데 시간이 15분 정도 남아있어서 구현미스로 버츄얼중에 못 풀었는데 ㅠ.ㅠ
가장 핵심적인 아이디어는 임의의 정점 s에서 s->t->s로 돌아오게 되면, s와 t는 홀수번 방문하게 되고, 그 사이의 경로는 짝수번 방문하게 된다는 사실이다.
이걸 이용하면 아주 멋진 짓거리를 할 수 있는데, dfs 스패닝 트리를 우선 만들어준다.
그리고 각각의 정점에 대해서 자신의 자식 노드를 dfs해서 들어갈 건데
재귀적으로 타고 들어가기 때문에 아래 서브 트리에서 모두 문제를 해결하고 돌아온 이번 노드에 대해서 이 노드의 방문 기우성이 정답과 다르다면
자식 노드 -> 현재 노드
이 쿼리를 한번 날리면 된다.
그리고 현재 노드의 기우성을 바꿔주면 된다.
이렇게 하다 보면 마지막 1번 노드 의외에는 전부 만족하게 만들어 줄 수 있다.
그런데 dfs로 경로를 탐색한 것이기 때문에, 마지막 1번 노드는 방문하던지, 하지 않던지는 내 자유이다.
따라서 기우성이 정답과 다르다면 방문하고, 같다면 방문하지 않으면 된다.
그렇다면 전체 트리 탐색에 최대 2n번, 그리고 각각 자식 노드 방문에 최대 2n번 사용하기 때문에
4n이하의 path가 항상 construct 된다.