20210218 PS 스케치

풀고 싶은 문제가 많은데 하나같이 너무 어려워서 진전이 없다

 

BOJ 19017 Automorphism

 

Subtree를 실시간으로 관리하기 위해 Dynamic Euler Tree를 생각했었으나 tree isomorphism 관련 글을 읽어보니 서브트리를 해싱해서 isomorphism을 찾고 간선 추가 쿼리를 오일러 트리를 쓰던 다른 BST 쓰던가 해서 관리하는 걸로 보인다.

아직 풀기엔 사전 지식이 부족해서 나중에 다시 제대로 잡아봐야겠다.

 

BOJ 18761 Interesting Game

 

우선, 계모의 턴마다 계모가 취할 수 있는 최선의 전략은 수열에서 가장 큰 원소 B개를 지우는 것이라 볼 수 있다.

신데렐라의 최선 전략은 다음 턴에 0이 되는 가장 큰 B개의 원소들을 제외한 나머지 원소들에 수열 대체 조건을 만족하는 한계 내에서 A값을 분배하거나 올인하여 M의 최댓값을 갱신해나가는 것인데, 수열을 A'로 대체하기 위해선 A'의 합이 기존 수열의 합 + A보다 작아야 하지만 2 턴마다 수열의 합이 0이 되어 수열의 합은 계속 감소해나가므로 M의 최댓값은 상한이 있음이 자명하다. 따라서 유의미한 게임 진행이 가능한 최대 턴까지 수열의 합이 최대가 되도록 하는 그리디에 약간의 최적화를 섞으면 풀리지 않을까?

 

BOJ 20656 지구 종말

 

Generalized River Crossing Problem으로 불리는 문제 유형이다.

흔히 알고 있는 강 건너기 문제와는 달리 RULE이 고정되어 있지 않으므로 DFS를 초기 조건에서 돌리며 가능한 state를 갱신해나가는 방법에서 나아가 n차원 하이퍼큐브 그래프를 이용해 단절점을 찾는 문제로 환원된다.

관련 논문을 내가 제대로 이해한 게 맞다면 단절점의 개수는 M의 크기보다 작거나 같아서 각 테스트 케이스가 $O(n|F|)$에 해결된다는 거 같다.