알고리즘 과 데이터 구조 - 게임 이론

게임 A 간단 한 게임 에는 두 명의 놀이 꾼 이 있다. A 와 B.21 개의 돌 이 있다.두 사람 은 돌아 가면 서 돌 을 가 져 가 매번 1, 2, 3 개 를 가 져 갈 수 있다.A 선 취.마지막 돌 을 가 져 간 사람 이 이 기 는 것 은 돌 이 없 는 사람 이 지 는 것 이다.
1, 2, 3 개의 돌 이 남 으 면 다음 에 가 진 사람 이 이 길 수 있다.4 개가 남 으 면 다음 사람 이 어떻게 취하 든 앞 에 이런 상황 이 발생 하기 때문에 다음 에 얻 는 사람 은 반드시 진다.5, 6, 7 개의 돌 이 남 았 다 면 다음 에 얻 은 사람 은 4 개의 돌 만 남 겨 두 면 이 길 수 있 었 다.0, 4, 8, 12....................................................................지금 은 21 개의 돌 이 있 고 21 을 4 로 나 누 면 나머지 가 1 이기 때문에 먼저 가 는 사람 은 필승 의 전략 이 있다. 그 는 처음으로 돌 하 나 를 가 져 가면 앞으로 매번 남 은 돌 이 4 의 배수 라 는 것 을 보증 하면 된다.
P 상태 와 N 상 태 는 첫 번 째 게임 처럼 상태 0, 4, 8.......................................................................그리고 1, 2, 3, 5, 6, 7...........................................................................우 리 는 종료 상태 에서 출발 하여 모든 상 태 를 내 놓 아 P 상태 인지 N 상태 인지 지적 할 수 있다.
이제 게임 1 을 조금 확장 하 겠 습 니 다.하나의 의사 결정 집합 S, S 중의 요 소 는 정수 이다.게임 의 규칙 은 크게 게임 1 과 같 습 니 다. 다만 지금 매번 취 할 수 있 는 돌 수 는 S 중의 요소 여야 합 니 다.S = {1, 2, 3} 이 라면 게임 1 입 니 다.S = {1, 3, 4} 일 때 어떤 상태 가 P 상태 이 고 어떤 상태 가 N 상태 인지 분석 해 보 세 요.우 리 는 P 상태 가 {0, 2, 7, 9, 14, 16,...}, N 상 태 는 {1, 3, 4, 5, 6, 8, 10...} 이라는 것 을 발견 했다.규칙 은 n 을 7 로 나 눈 나머지 가 0 이나 2 라면 상태 n 은 P 상태 이 고 그렇지 않 으 면 N 상태 이다.게임 이 시 작 될 때 돌 총 수 는 100 이 라면 P 상태 다. 즉, 나중에 가 는 사람 은 필승 전략 이 있다 는 것 이다.
게임 B 님 게임 은 각각 x1, x2, x3 개의 돌 을 함유 한 세 무더기 의 돌 이 있 습 니 다.두 사람 은 돌아 가면 서 돌 을 채취 하 는데, 매번 한 무 더 기 를 선택 하여 이 더미 에서 임의의 여러 개의 돌 을 가 져 갈 수 있 지만, 취하 지 않 을 수 는 없다.마지막 돌 을 가 져 간 사람 이 이 겼 다.
우 리 는 3 원조 로 상 태 를 표시 하 는데, 매우 뚜렷 하 다 (0, 0, 0) 는 유일한 종료 상태 이 고, P 상태 이다.먼저 돌 이 한 무더기 남 은 상황 (0, 0, x) 을 고려 해 보면 이 상태 들 은 모두 N 상태 임 이 분명 하 다.두 무더기 가 남 은 경우 두 무더기 의 돌 수가 같다 면 (0, x, x) 이것들 은 모두 P 상태 이다.다음 에 걷 는 사람 은 반드시 두 무더기 의 돌 을 같 지 않 게 할 것 이 고, 다음 에는 두 무더기 의 돌 수 를 같은 상태 로 돌려 놓 을 수 있 기 때문에 중지 상 태 를 포함한다.두 무더기 의 돌 수가 같 지 않 으 면 N 상태 다.
'Nim 과' 는 두 개의 수 이 진 이 나타 내 는 불 진 덧셈, 즉 두 개의 정수 가 xor 비트 연산 을 하 는 것 이다.정의: 두 개의 수 (xm... x0) 2 와 (ym... y0) 2 는 (zm... z0) 2 이 며, 그 중에서 zi = (xi + yi) mod 2, 0 < = i < = m 정 수 는 Nim 과 (앞으로 '+' 로 표시) 교환 율 과 결합 율 을 만족시킨다.
정리 1: Nim 게임 의 한 상태 (x1, x2, x3) 는 P 상태 이 고 x1 + x2 + x3 = 0 에 불과 합 니 다.
게임 C 그림 게임 은 두 사람 이 하 는 게임 으로 하나의 그림 G (X, F) 에서 하고 하나의 정점 x0 을 가리 키 며 다음 과 같은 규칙 에 따른다. A 가 먼저 가 고 x0 부터 시작한다.두 사람 은 돌아 가면 서 걷는다.정점 x 에서 출발 하여 정점 y 까지 만 갈 수 있 고 y 는 F (x) 에 속한다.중지 상태 에 부 딪 히 면 걸 을 수 없고, 이 사람 이 진다.
후계 함수 정의: 그림 G 를 (X, F) 로 표시 합 니 다.X 는 정점 집합 이 고 F 는 후계 함수 이다.설정 x 는 정점 이 고 F (x) 는 집합 으로 X 에 포함 되 며 임의의 요소 y 는 F (x) 에 속 하 며 x 에서 y 까지 한 변 이 있 음 을 나타 낸다.F (x) 는 x 의 후계 집합 이 고 x 에서 출발 하 는 결정 집합 으로 볼 수 있다.F (x) 가 비어 있 으 면 x 가 종료 상태 임 을 나타 낸다.
Sprague - Grundy 함수 정의: 경계 가 있 는 그림 G (X, F) 에 있어 SG 함수 g 는 X 에 정 의 된 함수 이 고 함수 값 은 비 마이너스 정수 로 g (x) = min {n ≥ 0 | 임의의 y * 8712 ° F (x), n ≠ g (y)} 즉 g (x) 의 값 은 모든 x 의 후속 SG 함수 에 나타 나 지 않 은 가장 작은 비 마이너스 정수 와 같다.
SG 함 수 는 P 상태 와 N 상태 와 관련 이 있 습 니 다.g (x) = 0 이면 x 는 P 상태 이 고 그렇지 않 으 면 x 는 N 상태 입 니 다.x 가 종료 상태 라면 g (x) = 0.한 상태 x, g (x) ≠ 0 이면 x 의 후계 y 가 반드시 존재 하여 g (y) = 0.한 상태 x, g (x) = 0 이면 모든 x 의 후계 y 는 g (y) ≠ 0 이 있다.
게임 B 와 게임 C 는 본질 적 으로 일치한다.다음 과 같은 이론 이 있다. 덧셈 이론: 국면: (a1, a2,..., an) + (b1, b2,....................................................추론: 초기 국면 S 가 두 개의 똑 같은 '서브 국면' 으로 나 눌 수 있다 면 선행 자 는 마이너스 (S 마이너스) 이다.
분해 이론: 국면 S = A + B 에 대해 선구자 가 필승 전략 이 있 으 면 'S 승' 이 라 고 부 르 고 그렇지 않 으 면 'S 패' 라 고 부른다.1) A 와 B 가 1 승 1 패 하면 S 승.2) A 마이너스 B 이면 S 마이너스.3) A 승 B 승 이면 S 시 승 시 패.추론: 1) S = A + C + C 는 S 의 상황 이 A 와 같다.따라서 국면 (3, 3, 1) 을 국면 (1) 으로 간소화 할 수 있다.2) 공 세 는 마이너스 다.
일반 해법: \ # S 로 국면 S 에 대응 하 는 바 이 너 리 수 를 표시 하면: 국면 S = A + B = > \ # S = \ # A + \ # B 즉 \ # S 는 이 돌무더기 a 의 sg 함수 값 g (a) 와 같다.만약 에 \ # 3 으로 표시 할 수 있다 면 (3).(여기 g (x) = x) 는 (3, 3) = (3) + (3) = > \ # (3, 3) = \ # (3) + \ # (3) = 11B + 11B = 0 (무 진 2 진법 덧셈 즉 이 또는 연산) 이 있다.결론: 만약 에 \ # S = 0 이면 S 가 지고 그렇지 않 으 면 S 가 이긴다.게임 홍보 B 는 매번 상한 m 를 취하 기 위해 g (x) = x% (m + 1) 만 변경 하면 됩 니 다.
게임 D n 개의 그림 게임 과 정의: n 개의 경계 가 있 는 그림 게임 G1 (X1, F1),..., Gn (Xn, Fn) 이 있 습 니 다.새로운 게임 G (X, F) 로 합 쳐 G = G1 + G2 +... + Gn 으로 기록 합 니 다.X 는 모든 게임 의 정점 집합 인 피리 칼 적, 즉 X = X1 * X2 *... * Xn 이다.즉, 우 리 는 n 원조 (x1, x2,..., xn) 로 G 중의 정점 x 를 표시 하 는데 그 중에서 xi 는 Xi 에 속 하고 모든 i 에 대한 것 이다.x 의 후계 F (x) 는 다음 과 같이 정의 할 수 있다.
정리 2: 설정 G = G1 + G2 +... + Gn, Gi 의 SG 함 수 는 gi, i = 1, 2,..., n 이다.그러면 G 의 SG 함수 g (x1, x2,..., xn) = g1 (x1) + g2 (x2) +... + gn (xn), 덧셈 은 Nim 과, 즉 들 어가 지 않 는 바 이 너 리 덧셈 을 나타 낸다.
필승 전략: 통 합 된 SG 값 과 모든 SG 값 을 각각 다 르 게 사용 하거나, 보 이 는 결과 가 원래 쌓 인 SG 값 보다 작 을 지, 작 으 면 이 더 미 를 가 져 올 수 있 습 니 다.
게임 E 가 져 가기 - 분할 게임 갑 을 은 몇 개의 돌 을 마주 하고 그 중에서 한 줄 의 돌 수 를 임의로 확정 할 수 있다.예 를 들 어 초기 국면 은 (7, 3, 3) 이다.한 걸음 한 걸음 어떤 줄 에서 두 개의 돌 을 가 져 가 야 한다.이 두 개의 돌 은 반드시 바짝 붙 어야 한다.
분석: 한 번 씩 가 져 오 는 것 은 다시 쌓 는 것 과 같다.
일반 해법: 1) n 원조 (a1, a2,..., an) 로 게임 의 한 국면 을 묘사 합 니 다.2) 기호 \ # S 로 국면 S 에 대응 하 는 이 진 수 를 나타 낸다.3) 기호 $(x) 로 국면 (X) 의 다음 단계 에 나타 날 수 있 는 모든 집합 을 표시 합 니 다.4) 정의 집합 g (x), 설정: $(x) = {S1, S2,..., Sk}, 면 g (x) = {\ # S1, \ # s2,..., \ # Sk}.5) 마이너스 정수 집합 을 전집 으로 하고 집합 G (x) 는 집합 g (x) 의 보충 집합 을 나타 낸다.6) 정의 함수 f (n): f (n) = min {G (n)}, 즉 f (n) 는 집합 G (n) 의 최소 수 와 같다.7) 국면 S = (a1, a2,..., an), \ # S = f (a1) + f (a2) +... + f (an) 를 설정 하고 무 진 이 진 덧셈 즉 이 또는 연산 을 사용 합 니 다.# S ≠ 0 이면 S 승, 그렇지 않 으 면 S 패.
 
제목 추천:
ZOJ Problem Set - 3529 A Game Between Alice and Bob
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4464
제목:
Alice 와 Bob 두 사람 은 게임 을 하고 있 습 니 다. 처음에 n 개의 정수 가 있 었 습 니 다. Alice 가 먼저 조작 한 다음 에 쌍방 이 돌아 가면 서 조작 할 수 있 습 니 다. 한 개의 수 를 선택 하여 이 수의 하나 와 자신 이 다른 약수 로 바 꿀 수 있 습 니 다. 누가 모든 수 를 1 로 바 꾸 면 누가 이 길 수 있 습 니까?
분석:
sg 함수 g (n) = {n 의 질 인자 의 개수}.구 질 인자 개 수 는 먼저 빠 른 잘 생 긴 소수 법 으로 소수 와 각 수의 최대 질 인 자 를 표시 한다.그러면 이 수의 질 인자 개 수 를 다시 처리 하 는 것 은 최대 질 인 자 를 나 눈 후의 질 인자 개수 + 1 (DP) 이다.그 다음 에 게임 문제 의 합병 을 이용 하면 각 수가 얻 은 SG 값 이 다 르 거나 0 이 아니면 0 이 아니면 0 이 되면 마이너스 임 을 알 수 있다.그 다음 에 후반 부 는 또 다른 전형 적 인 문제 이다. 합 친 SG 값 으로 모든 SG 값 과 각각 다 르 거나 보 이 는 결과 가 원래 쌓 인 SG 값 보다 작 는 지, 작 으 면 이 더 미 를 찾 을 수 있다.
개인 코드 참고 (개인 적 인 느낌 은 비교적 뚜렷 하 다):

#include "stdio.h"

#define MAX 5000005
long isPrime[MAX];
long input[MAX];
long sg[MAX];

/**
 *        
 *  i   isPrime[i]=i   isPrime[i]       
 */
void initPrime(){
	long i,j;
	isPrime[0]=isPrime[1]=sg[0]=sg[1]=0;
	for(i=2;i<MAX;i++){
		isPrime[i]=i;
		sg[i]=-1;
	}
	for(i=2;i<MAX;i++){
		if(isPrime[i]==i){
			for(j=2;i*j<MAX;j++)
				isPrime[i*j]=i;
		}
	}
}
/**
 * dp  SG   
 * n                           +1
 */
long getSG(long n){
	if(sg[n]!=-1)return sg[n];
	else if(isPrime[n]==n)return sg[n]=1;
	else return sg[n]=getSG(n/isPrime[n])+1;
}


int main()
{
	long n,i,SG,count=1;
	initPrime();
	while(scanf("%ld",&n)!=EOF){
		for(SG=i=0;i<n;i++){
			scanf("%ld",&input[i]);
			SG=SG^getSG(input[i]);
		}
		for(i=0;i<n;i++){
			if((SG^getSG(input[i]))<getSG(input[i]))break;
		}
		if(SG!=0)printf("Test #%ld: Alice %ld
",count++,i+1);
		else printf("Test #%ld: Bob
",count++);
	}

	return 0;
}