Additional Problems

  1. Shortest Subsequence 
  2. Counting Bits 
  3. Swap Game 
  4. Prufer Code 
  5. Acyclic Graph Edges 
  6. Strongly Connected Edges 
  7. Even Outdegree Edges 
  8. Multiplication Table 
  9. Advertisement
  10. Special Substrings 
  11. Permutation Inversions 
  12. Maximum Xor Subarray 
  13. Movie Festival Queries 
  14. Chess Tournament 
  15. Tree Traversals 
  16. Network Renovation 
  17. Graph Girth 
  18. Intersection Points 
  19. Inverse Inversions 
  20. Monotone Subsequences 
  21. String Reorder 
  22. Stack Weights 
  23. Pyramid Array 
  24. Increasing Subsequence II 
  25. String Removals 
  26. Bit Inversions 
  27. Xor Pyramid 
  28. Writing Numbers 
  29. String Transform 
  30. Letter Pair Move Game 
  31. Maximum Building I 
  32. Sorting Methods 
  33. Cyclic Array
  34. List of Sums 
  35. Increasing Array II 
  36. Food Division 
  37. Bit Problem 
  38. Swap Round Sorting 
  39. Binary Subsequences 
  40. Tree Isomorphism I 
  41. Counting Sequences 
  42. Critical Cities 
  43. School Excursion 
  44. Coin Grid 
  45. Robot Path 
  46. Programmers and Artists 
  47. Course Schedule II
  48. Removing Digits II 
  49. Coin Arrangement 
  50. Counting Bishops 
  51. Grid Puzzle I 
  52. Grid Puzzle II 
  53. Empty String 
  54. Grid Paths 
  55. Bit Substrings 
  56. Reversal Sorting 
  57. Counting Reorders 
  58. Book Shop II 
  59. Network Breakdown 
  60. Visiting Cities 
  61. Missing Coin Sum Queries 
  62. Number Grid 
  63. Maximum Building II 
  64. Filling Trominos 
  65. Stick Divisions 
  66. Coding Company 
  67. Flight Route Requests 
  68. Two Stacks Sorting 
  69. Tree Isomorphism II 
  70. Forbidden Cities 
  71. Area of Rectangles 
  72. Grid Completion 
  73. Creating Offices 
  74. Permutations II 
  75. Functional Graph Distribution 
  76. New Flight Routes 
  77. Grid Path Construction 

 

CSES Problem Set 소개 (link)

'CSES' 카테고리의 다른 글

CSES 10. Advanced Techniques  (0) 2021.07.21
CSES 9. Geometry  (0) 2021.07.21
CSES 8. String Algorithms  (0) 2021.07.21
CSES 6. Tree Algorithms  (0) 2021.07.21
CSES 5. Range Queries  (0) 2021.07.21

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


문제 설명

You have n coins with certain values. Your task is to find all money sums you can create using these coins.

입력 

The first input line has an integer n: the number of coins.

The next line has n integers x1,x2,,xn : the values of the coins.

출력

First print an integer k: the number of distinct money sums.

After this, print all possible sums in increasing order.

입력 예

4
4 2 5 2

출력 예

9
2 4 5 6 7 8 9 11 13

제약조건

1<= n <=100

1<= x_i <= 1000


문제 풀이

가능한 최대값은 100*1000 (max_n, max_xi) 이다. 가능한 최대값과 같은 크기의 boolean 배열을 만든다. 각 코인마다 값들을 더해가면서 falst->true 로 변경한다. 만들어진 배열에서 true 경우를 세고, dp[u] == true 이면, u가 가능한 값이 된다.

프로그램 내용

더보기
vector<bool> dp(n*1000+1);
...
for (int c : coins) 
{
	for (int i = dp.size() - 1; i > 0; i--) 
	{
            if (dp[i]) 
                dp[i + c] = 1; 
            d[c] = 1; 
	}
}
...

 

Dynamic Programming link )

'CSES' 카테고리의 다른 글

CSES 6. Tree Algorithms  (0) 2021.07.21
CSES 5. Range Queries  (0) 2021.07.21
CSES 3. Rectangle Cutting (1744)  (0) 2020.07.28
CSES 3. Edit Distance (1639)  (0) 2020.03.18
CSES 4. Road Reparation (1675)  (0) 2020.01.20

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


문제 설명

The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are:

  • Add one character to the string.
  • Remove one character from the string.
  • Replace one character in the string.

For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

입력 

The first input line has a string that contains n characters between A–Z.

The second input line has a string that contains m characters between A–Z.

출력

Print one integer: the edit distance between the strings.

입력 예

LOVE
MOVIE

출력 예

2

제약조건

1 <= n,m <= 5000


문제 풀이

두개의 문자열을 행과 열로 하는 테이블을 생각한다. src[i] == dest[j]는 변경할 필요가 없으며 값을 변경하지 않아도 된다. 문자열이 다르면, dist[i][j] = min({dist[i][j-1], dist[i-1][j], dist[i-1][j-1]) + 1 로 계속 변경해서 테이블을 완성한다.

프로그램 내용

더보기
...
for(int i=0; i <= m; ++i)
{
	for (int j=0; j <= n ; ++j)
	{
		if ( i == 0)
        	dist[i][j] = j; /// init for desStr
		else if ( j == 0)
        	dist[i][j] = i; /// init for srcStr
		else if ( srcStr[i-1] == desStr[j-1])
        	dist[i][j] = dist[i-1][j-1];
		else
        	dist[i][j] = 1 + min({	dist[i-1][j],      /// insert
									dist[i][j-1],      /// remove
									dist[i-1][j-1]});   /// replace
	}
}
...

 

Dynamic Programming link )

'CSES' 카테고리의 다른 글

CSES 3. Money Sum (1745)  (0) 2020.07.29
CSES 3. Rectangle Cutting (1744)  (0) 2020.07.28
CSES 4. Road Reparation (1675)  (0) 2020.01.20
CSES 7. Stick Game (1729)  (0) 2020.01.19
CSES 4. Road Construction (1676)  (0) 2020.01.13

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


문제 설명

There are n cities and mm roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

입력 

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 roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

출력

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

입력 예

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

출력 예

14

제약조건

1 <= n <= 1e5

1<= m <= 2*1e5

1 <= a, b <= n

1 <= c <= 1e9


문제 풀이

도시들을 정점으로하고 연결하는 도로들을 간선으로 하는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 

간선의 비용을 기준으로 작은 것부터 도시들을 계속해서 연결해 나간다. 도시 하나를 연결할때 연결된 도시수를 기록한다. 모든 도시가 연결된다면 필요한 최소 간선의 수는 도시의 수보다 1 작은 값이 되야 한다. 이 값보다 크다면, 연결할 수 없는 도시가 존재하므로 "IMPOSSIBLE"을 출력하고, 연결되면 연결하면서 기록한 비용을 출력한다.

프로그램 내용

더보기
for(int id=0; id < tE; ++id)
{
	int a, b, c;
	cin >> a >> b >> c;
	vt.push_back({c, a, b});
}        
...
long sum = 0;
int cnt = tN;
for(int id=0; id < tE; ++id)
{
	int a, b, c;
	tie(c, a, b) = vt[id];
	if(merge(a, b))	/// union
	{
		sum += c;
		cnt--;
	}
}
...

 

 Graph Algorithms link )

'CSES' 카테고리의 다른 글

CSES 3. Rectangle Cutting (1744)  (0) 2020.07.28
CSES 3. Edit Distance (1639)  (0) 2020.03.18
CSES 7. Stick Game (1729)  (0) 2020.01.19
CSES 4. Road Construction (1676)  (0) 2020.01.13
CSES 4. Graph Algorithms  (0) 2020.01.13

출처: 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 )

'CSES' 카테고리의 다른 글

CSES 3. Edit Distance (1639)  (0) 2020.03.18
CSES 4. Road Reparation (1675)  (0) 2020.01.20
CSES 4. Road Construction (1676)  (0) 2020.01.13
CSES 4. Graph Algorithms  (0) 2020.01.13
CSES 7. Nim Game II (1098)  (0) 2020.01.05

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


문제 설명

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,,

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 크기와 원래 최대 크기를 비교해서 최대크기를 갱신하면 된다.

프로그램 내용

더보기
...
int cnt = n;				/// number of components 
for (int i = 0; i < m; i++)
{
	int a, b;
	cin >> a >> b;

	if( find_root(a) != find_root(b))
	{
		join(a, b);			/// component merge & max_sz update
		cnt--;				/// number of components decrease
	}

	cout << cnt << " " << max_sz << "\n";
}
...

 

Graph Algorithms link )

'CSES' 카테고리의 다른 글

CSES 4. Road Reparation (1675)  (0) 2020.01.20
CSES 7. Stick Game (1729)  (0) 2020.01.19
CSES 4. Graph Algorithms  (0) 2020.01.13
CSES 7. Nim Game II (1098)  (0) 2020.01.05
CSES 7. Nim Game I (1730)  (0) 2020.01.05

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


문제 설명

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

프로그램 내용

더보기
/// (1~k) substraction game
/// Nim sum == XOR values of (value % (k+1))

...
	int tN, ret = 0;
	cin >> tN;

	for(int id=0; id<tN;++id)
		int tmp;
		cin >> tmp;

		ret ^= (tmp%MAX_R);
...        

 

7. Mathematics link )

'CSES' 카테고리의 다른 글

CSES 4. Road Construction (1676)  (0) 2020.01.13
CSES 4. Graph Algorithms  (0) 2020.01.13
CSES 7. Nim Game I (1730)  (0) 2020.01.05
CSES 7. Mathematics  (0) 2020.01.01
CSES 7. Stair Game(1099)  (0) 2020.01.01

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


문제 설명

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을 얻을 수 있다.

프로그램 내용

더보기
/// Nim sum == XOR values
...
	int tN, ret = 0;
	cin >> tN;

	for(int id=0; id<tN;++id)	
    	int tmp;
		cin >> tmp;

		ret ^= tmp;
...

 

7. Mathematics link )

'CSES' 카테고리의 다른 글

CSES 4. Graph Algorithms  (0) 2020.01.13
CSES 7. Nim Game II (1098)  (0) 2020.01.05
CSES 7. Mathematics  (0) 2020.01.01
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Array Description (1746)  (0) 2019.12.31

Mathematics

  1. Josephus Queries
  2. Exponentiation  (0)
  3. Exponentiation II  (0)
  4. Counting Divisors
  5. Common Divisors
  6. Sum of Divisors
  7. Divisor Analysis
  8. Prime Multiples
  9. Counting Coprime Pairs
  10. Binomial Coefficients
  11. Creating Strings II
  12. Distributing Apples
  13. Christmas Party
  14. Bracket Sequences I
  15. Bracket Sequences II
  16. Counting Necklaces
  17. Counting Grids
  18. Fibonacci Numbers
  19. Throwing Dice
  20. Graph Paths I
  21. Graph Paths II
  22. Dice Probability
  23. Moving Robots
  24. Candy Lottery
  25. Inversion Probability
  26. Stick Game  (1)
  27. Nim Game I  (1)
  28. Nim Game II  (1)
  29. Stair Game  (1)
  30. Grundy's Game
  31. Another Game 

 

CSES Problem Set 소개 ( link )

'CSES' 카테고리의 다른 글

CSES 7. Nim Game II (1098)  (0) 2020.01.05
CSES 7. Nim Game I (1730)  (0) 2020.01.05
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Array Description (1746)  (0) 2019.12.31
CSES 3. Book Shop (1158)  (0) 2019.12.28

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


문제 설명

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 연산으로 일정하게 만든다.

프로그램 내용

더보기
...
for (int i = 1; i < n; i++)
{
	if( x_i == 0 )	/// update all possible numbers 
	{
		for (int j = 1; j <= m; j++)
		{
			k = min(1, j);
			dp[i][k] += (dp[i-1][k-1] + dp[i-1][k] + dp[i-1][k+1]) % MOD;
		}
	}
	else	/// update x_i
	{
		dp[i][x_i] += (dp[i-1][x_i-1] + dp[i-1][x_i] + dp[i-1][x_i+1]) % MOD;
	}
}
...      

 

Dynamic Programming link )

'CSES' 카테고리의 다른 글

CSES 7. Mathematics  (0) 2020.01.01
CSES 7. Stair Game(1099)  (0) 2020.01.01
CSES 3. Book Shop (1158)  (0) 2019.12.28
CSES 3. Grid Paths (1638)  (0) 2019.12.28
CSES 2. Sliding Cost (1077)  (0) 2019.12.28

+ Recent posts