Daddy's Journey to Platinum

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정도이므로 충분하다.

There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n 

Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

Print m lines: the required information after each day.

5 3
1 2
1 3
4 5

4 2
3 3
2 3

• 1 <= n < 1e5
• 1 <= m < 2 * 1e5
• 1 <= a, b <= n

connected component count & component size 를 찾는 문제이다. 그래프에서 connected component를 찾는 방법은 DFS, BFS, Union find 등의 방법을 사용한다. 전체 node를 검사하는 경우 시간복잡도는 O(nm)) 이지만, n=1e5, m=2x1e5 의 입력에서 시간초과가 나오므로, 중간에 계산량을 줄이는 방법이 필요해진다.

이 문제는 road(edge)가 추가되므로 추가된 부분과 연결된 부분만 계산한다. 

즉, 모든 edge를 검사할 필요 없이, 이번에 추가되는 edge와 연결된 vertex들에 대해서, 같은 component에 있는 지 확인하고, 있다면 component 숫자나 최대 크기를 변경할 필요가 없고, 서로 다른 component에 있는 경우에는 component 숫자를 줄이고, 새롭게 만들어진 component 크기와 원래 최대 크기를 비교해서 최대크기를 갱신하면 된다.

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... x_n : the number of sticks in each heap.

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

3
4
5 7 2 5
2
4 1
3
4 4 4

first
first
second

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9 
• the sum of all n is at most 2*1e5 

Nim Game의 변형문제이다.

제외할 수 있는 숫자가 1~k개로 제한되는 경우에는 (k+1) modulo 결과를 Nim Sum 이라고 한다.

• Nim Sum == 0 : 나중에 하는 사람이 승리하는 전략이 존재
• Nim Sum != 0 : 먼저하는 사람이 승리하는 전략이 존재

대항해시대4의 경우에 동전을 제거하는 게임이 나오는데 같은 원리를 적용하면, 승리할 수 있다. (컴퓨터가 이 전략을 적용하기 때문에 최초에 남는 동전에 따라 게임 결과가 정해져 있다고 생각하면 된다.) 

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

The first input line contains an integer tt: the number of tests. After this, tt test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... , x_n : the number of sticks in each heap.

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

3
4
5 7 2 5
2
4 1
3
3 5 6

first
first
second

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9
• the sum of all n is at most 2*1e5

Game Theory 에 나오는 Nim Game 

Nim Sum 을 계산해서, 0인 경우는 나중에 하는 플레이어가 이기게 되고 0이 아닌 경우는 먼저하는 플레이어가 이기는 승리전략이 존재한다. 따라서, 문제에서 플레이어가 이 전략을 알고 거기에 따라서 행동하기 때문에 Nim Sum을 계산하면 답을 찾을 수 있다. Nim Sum은 이진수로 표현했을때 각 자리수의 1들을 2개씩 짝지을 수 있으면 0 없으면 1로 계산하는 것이다. 즉, 값들을 bit XOR 를 하면 Nim Sum을 얻을 수 있다.

There is a staircase consisting of n stairs, numbered 1,2,…,n. Initially, each stair has some number of balls.

There are two players who move alternately. On each move, a player chooses a stair kk where k≠1 and it has at least one ball. Then, the player moves any number of balls from stair k to stair k−1. The winner is the player who moves last.

Your task is to find out who wins the game when both players play optimally.

The first input line has an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of stairs.

The next line has n integers p_1,p_2,…,p_n : the initial number of balls on each stair.

For each test, print "first" if the first player wins the game and "second" if the second player wins the game.

3
3
0 2 1
4
1 1 1 1
2
5 3

first
second
first

• 1 <= nT <= 2x10^5
• 1 <= tN <= 2x10^5
• 1 <= p_i <= 10^9
•  sum of all n is at most 2x10^5

Nim Game ( link ) 의 변형 문제이다. 

아래에 있는 계단부터 마지막 계단까지 1 ~ N 으로 번호를 붙였을때, 마지막으로 볼이 남아있는 계단을 선택하는 사람이 승리하게 된다.

Nim 게임에서는 선택한 것을 제거하는데, 이 게임에서는 아래로 옮길 수 있.으므로 게임속에서 계속 남아 있게 된다.

단, 첫번째 계단 (1번 계단) 은 선택할 수 없기 때문에 계단2에서 계단 1로 옮기는 경우가 볼을 제거하는 것과 같은 효과를 가진다. 즉, 2번째 계단에 마지막으로 볼이 남아 있을때가 게임이 끝나는 순간이 된다.  그러므로, 짝수 계단에 있는 볼들을 대상으로 Nim Sum을 계산해보면 게임의 승자를 알 수 있게 된다.

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

The first input line has two integers n and mm: the array size and the upper bound for each value.

The next line has n integers x_1,x_2,…,x_n : the contents of the array. Value 0 denotes an unknown value.

Print one integer: the number of arrays modulo 10^9+7.

3 5
2 0 2

3

Explanation: [2,1,2], [2,2,2] , and [2,3,2]

• 1 <= N <= 10^5
• 1 <= M <= 100
• 0 <= x_i <= M 

배열에서 어떤 위치의 숫자는 바로 전 위치의 숫자 값에 따라서 결정된다(+1, -1, 0). 이렇게 가능한 경우의 배열을 x_0 부터 x_n-1까지 계속해서 더해서 만든다. 단, 이렇게 더하는 과정에 커지는 숫자는 modulo 연산으로 일정하게 만든다.

You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

N X // Number of books, maximum total price

h_i // books price

s_i // number of pages

the maximum number of pages.

4 10
4 8 5 3
5 12 8 1

13

• 1<= N <= 1000
• 1<= X <= 1e5
• 1<= h_i, s_i <= 1000 

Knapsack 문제이다. 어떤 특정한 책을 선택했을 때 페이지와, 그 책을 고르지 않았을 경우에 얻을 수 있는 페이지의 최대값을 비교해서 큰 값을 선택하도록 한다.

Consider an N x N grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square where you only can move right or down.

First line: N /// grid size

N line : grid information ( . : empty cell, * : trap)

Print the number of paths modulo 1e9 + 7

4
....
.*..
...*
*...

3

1 <= N <= 1000

어떤 특정한 cell ( path[i][j] ) 까지 도착하는 경로는 왼쪽에서 온 경우( path[i-1][j])와 위쪽에서 온 경우(path[i][j-1])의 합으로 결정된다. 제일 처음 출발하는 cell부터 목표로 하는 cell 까지 cell이 trap(*)인 경우는 제외하고 더해서 만들어 간다.