CSES 7. Stick Game (1729)

출처: https://cses.fi/problemset/task/1729/

---

문제 설명

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P={p1,p2,…,pk} determines the allowed moves. For example, if P={1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1,2,…,n if the first player has a winning or losing position.

입력 

The first input line has two integers n and k: the number of sticks and moves.

The next line has k integers p1,p2,…,pk that describe the allowed moves. All integers are distinct, and one of them is 1.

출력

Print a string containing n characters: W means a winning position, and L means a losing position.

입력 예

10 3
1 3 4

출력 예

WLWWWWLWLW

제약조건

1 <= n <= 1e6

1 <= k <= 100

1 <= p_i <= n

---

문제 풀이

움직일 수 있는 수 집합 P에 1이 항상 들어있으므로, 첫번째 위치는 플레이어 1이 이기는 위치가 된다. 다른 p_i개의 경우도 플레이어 1이 모든 스틱을 제거할 수 있으므로, 이 위치들도 모두 이기는 위치가 된다. 

다음 단계로 P_i에 2가 없는 경우에 플레이어 1이 2의 위치에 있다면, 제거할 수 있는 스틱은 1이 되고, 다른 플레이어가 스틱이 1개가 남은 위치가 되고, 다른 플레이어도 최선의 전략을 선택하기 때문에 이경우는 지게된다.

 

즉, 임의의 위치 i에서 p_i를 통해 움직일 수 있는 위치가 L이라면, 현재의 위치는 W이 된다.

 

그냥 1~N까지 위치를 움직이며, p_i들을 빼서 비교하는 방법을 사용하면 O( N*K )가 되고, 문제에서 나오는 조건으로는 1e8정도이므로 충분하다.

프로그램 내용

...
for(int id = 1; id <= tN; ++id)
{
	for(int idn = 0; idn < tK; ++idn)
    {
	    int cur = id - pi_[idn];

		if(cur < 1)
		{
			continue;
		}

		if(!visited[cur])			/// L position
		{
			visited[id] = true;
			break;
		}
	}
}
...

 

Mathematics ( link )