Green Hackenbush? 일반그래프 Green Hackenbush는 IPSC 2003 G번에 나온적 있음.
Tree Hackenbush: ONAG p88
Cycle Hackenbush: ONAG p90, 전봇대에 연결된 전선을 끊는게임으로 전봇대와 분리된 전선은 사라지는 게임은 그린사이클헤켄버시임
Cactus Hackenbush: Ground에 붙어있는 한 점을 루트로 해서 Cycle압축한 트리의 위상정렬 순서대로 처리하자. 어떤 사이클을 처리하려면 그 이전 사이클들은 값이 계산된 상태로 연결되어 있으니 p.88의 공식을 적용할 수 있는듯. 이 사이클을 처리할 때는 p.90의 공식은 사이클에 다른 Hackenbush가 붙어있어서 쓸수 없을 듯 하고, 두번째 방법으로 하나씩 간선 잘라봐서 나오는 트리의 simplest Number를 구하는 거로 계산가능할 듯.
Col: ONAG p93에 따르면 Number x 또는 x+*형태의 값만 나오니 DP가 가능할듯.
더일곱이게임 임의위치 시작버전
Mex 세그먼트 트리(https://codeforces.com/problemset/problem/1436/E)로 효율적으로 그런디넘버 구하는 게임문제
##########################################
그린 헤켄버시 트리의 각 정점을 루트로 할때 각 그런디값 구하는 문제
https://codeforces.com/contest/1498/problem/F 계산방식 사용하면 가능
##########################################
돌무더기가 N개 있다. I번째 돌무더기는 m_i개의 돌이 있으며, i번째 돌무더기의 j번째 돌에는 숫자a_ij가 적혀있다. 각 플레이어는 자신의 차례에 Non-Empty인 돌무더기 하나를 골라, min(그 맨 위에 놓인 돌의 숫자, 돌무더기 크기)이하만큼의 돌을 꼭대기에서 제거할 수 있다. 두 플레이어가 최적의 방법으로 게임할때, 선공이 승리하기 위해 첫 턴에 할 수 있는 움직임의 개수를 출력하라.
입력형식)
N
M0 a0[0] a0[1] … a0[m0-1]
…
M_N-1 a_n-1[0] …
제한)
1<=N,mi,sum(mi)<=10^5
##########################################
OO 건설회사는 아파트단지를 지었다. 각 아파트의 층은 검은색 또는 흰색이다. 아파트가 좁다는 주민들의 의견을 수용해서 각 건물을 확장해서 발코니를 만들었다. 파괴신 B와 W는 건물을 부시는 게임을 할것이다. B는 검은색 층을, W는 하얀 층을 선택하여 파괴할 수 있으며, 건물의 i층을 부수면 그 위층들과 발코니들도 같이 부서진다. 건물의 i층 발코니를 부수면, 그 발코니만 부서진다. 누가 이기는가?
제한: 아파트개수 N<=10^2, 각 아파트 층 M[i]<=20
\/
\/
\/
\/
/
이런 형태의 hackenbush 값 구하는 문제다. DP를 통해 f(x,y,z)=건물이 x층까지 있고, 흑의 베란다는 y층, 백의 베란다는 z층까지 있을때 값. 이라는 식을 세울 수 있다. 베란다를 부술 때는 각각 최상단의 것만 부시는게 최적이기 때문이다.
Proof)
어떤 작은가지 2개가 있을때 위의것을 선택한것과, 아래것을 선택한것의 negative game의 합을 생각해보자. stalk를 제거시 대응하는 stalk를 제거할 수 있으니 최소 0이다. 위 가지와 아래가지의 중간을 자를 경우, 위의 가지가 남은(=아래가지를 자른)것은 가능한 움직임이 하나 줄어들지만, 아래가지가 남은(=위 가지를 자른)것은 남는다. 좀 더 formal하게 쓰는게 좋겠지만 아무튼 이거로 충분할듯. 따라서 위 제거가 이득이다.
O(N*M^4)
트리 Hackenbush값 구하는 방법(ONAG Part1 앞부분에 나옴) 쓰면 훨씬 빠르게 구할 수 있을것이다.
##########################################
Boj.kr/17962 문제 잘못읽어서 나온 문제다.
선공 승리조건: 어떤 정점을 루트로할때 가능한 모든 서브트리에 리프까지의 거리%2==0인게 있다면 A, 아니면 B.
f(v, from child idx)=이 서브트리의 모든 서브트리가 승리조건 만족하는가?
상태개수=O(V), 이유:두번째 인자가 child idx이므로 이게 최대 V일 수 있어서 V^2같지만, 그 합은 degree와 같으므O(V+V)가 된다.
상태당 계산량=O(degree)=amortized O(1) 이유: 이것도 자식개수 합=amortized O(V)이고, 상태개수합도 O(V)이므로 O(V)/O(V)=O(1)
구현 디테일
DP테이블 정의할때 정적배열말고 벡터로 child크기만큼만 잡아줘야 함.
자기 자신도 첫번째 child로 정의해주면 구현 편함
스위핑같은거로 어렵게 구하지 말고, f(v,0)를 N개 다 돌리면 O(N)이 됨.
---------------------------------------------------------------------------------------
포레스트 버전(그런디)
V<=10^6
포레스트가 주어진다. 각 플레이어는 하나의 트리를 선택하여
1. 아직 돌이 놓이지 않았다면, 임의의 곳을 선택하여 돌을 둔다.
2. 돌이 놓여 있다면 그에 인접한 노드로 돌을 옮길 수 있다. 단, 이미 방문한 정점은 다시갈 수 없다.
위와 같은 작업을 할 수 있다. 누가 이길까?
위에서 설명한 Tree DP로 O(N)에 각 트리의 Grundy를 구하는거로 변형할 수 있다(mex를 구하면 되므로 이 작업도 상태당 각 O(deg)만큼만 걸린다)
각 트리 의 그런디를 다 xor해서 0이면 선공승, 아니면 후공승
굳이 그런디를 끼얹을 필요는 없을듯? 트리로 깔끔하게 충분하지 않을까.
##########################################
{-1,0,1} 로 이루어진 수열이 주어진다. 두 플레이어는 수열을 분할해야 하는데, A는 증가부분(a[i]<a[i+1])을, B는 감소부분(a[i]>a[i+1])을 자를 수 있다. 분할된 수열의 앞뒤 끝부분에 0이 하나라도 존재하면 남고, 하나도 없으면 사라진다. 자신의 차례에 분할할 방법이 없는 사람이 패배한다. 누가 이기는가? 단, 인접한 두 0 사이에는 최대 60개의 (0아닌)수가 있다. 수열의 길이N은 최대 10^6이다.
풀이: /ㅡㅡㅡㅡ\/ㅡㅡㅡㅡ\/\ (\는 백슬래시) 형태의 Hackenbush 값 구하기. 사실 Ground에 정점 하나만 붙은 Cycle Hackenbush값 구하기와 같고, ONAG Part1 앞부분에 간단한 해답이 존재한다. 처음 의도는 0으로 컴포넌트 나눠서 각각을 정방향,역방향 스위핑 2번으로 Hackenbush 전처리한 후, simplest number 정리 한번 적용해서 각 컴포넌트 값 구하는거였다. 아무튼 두가지 풀이로 교차검증가능할듯
Simplest Number 찾는법:
k=0에서 시작한다.
K<=x 이면 k+=1, k>=y이면 k-=1, 아니면 k가 답
K<=x 이면 k+=1/2, k>=y이면 k-=1/4, 아니면 k가 답
K<=x 이면 k+=1/4, k>=y이면 k-=1/4, 아니면 k가 답
…