Atcoder Beginner Contest 333 （A - F 题）

A - Three Threes

Problem Statement

You are given an integer $N$ between $1$ and $9$, inclusive, as input.
Concatenate $N$ copies of the digit $N$ and print the resulting string.

Constraints

$N$ is an integer between $1$ and $9$, inclusive.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer.

Sample Input 1

3

Sample Output 1

333

Concatenate three copies of the digit $3$ to yield the string 333.

Sample Input 2

9

Sample Output 2

999999999

Solution

具体见文后视频。

---

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int N;

	cin >> N;

	for (int i = 1; i <= N; i ++)
		cout << N;

	return 0;
}

---

B - Pentagon

Problem Statement

A regular pentagon $P$ is shown in the figure below.

Determine whether the length of the line segment connecting points $S_1$ and $S_2$ of $P$ equals the length of the line segment connecting points $T_1$ and $T_2$.

Constraints

Each of $S_1$, $S_2$, $T_1$, and $T_2$ is one of the characters A, B, C, D, and E.
$S_1\ne S_2$
$T_1\ne T_2$

Input

The input is given from Standard Input in the following format:

$S_1{S}_2$
$T_1{T}_2$

Output

If the length of the line segment connecting points $S_1$ and $S_2$ of $P$ equals the length of the line segment connecting points $T_1$ and $T_2$, print Yes; otherwise, print No.

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of $P$ equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of $P$ does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Solution

具体见文后视频。

---

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	string A, B;

	cin >> A >> B;

	int L1 = (A[0] - 1 + 5) % 5 + 'A', R1 = (A[0] + 1) % 5 + 'A';
	int L2 = (B[0] - 1 + 5) % 5 + 'A', R2 = (B[0] + 1) % 5 + 'A';
	// cout << char(L1) << " " << char(R1) << " " << char(L2) << " " << char(R2) << endl;
	if (A[1] != L1 && A[1] != R1 && B[1] != L2 && B[1] != R2) cout << "Yes" << endl;
	else if ((A[1] == L1 || A[1] == R1) && (B[1] == L2 || B[1] == R2)) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

---

C - Repunit Trio

Problem Statement

A repunit is an integer whose digits are all $1$ in decimal representation. The repunits in ascending order are $1,11,111,\dots$.
Find the $N$-th smallest integer that can be expressed as the sum of exactly three repunits.

Constraints

$N$ is an integer between $1$ and $333$, inclusive.

Input

The input is given from Standard Input in the following format:
$N$

Output

Print the answer.

Sample Input 1

5

Sample Output 1

113

The integers that can be expressed as the sum of exactly three repunits are $3,13,23,33,113,\dots$ in ascending order. For example, $113$ can be expressed as $113=1+1+111$.
Note that the three repunits do not have to be distinct.

Sample Input 2

19

Sample Output 2

2333

Sample Input 3

333

Sample Output 3

112222222233

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define int long long

using namespace std;

typedef pair<int, int> PII;

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int X = 0, N;

	cin >> N;

	std::vector<int> Num(18);
	for (int i = 1; i <= 17; i ++)
		Num[i] = X * 10 + 1, X = X * 10 + 1;

	std::set<int> V;
	for (int i = 1; i <= 17; i ++)
		for (int j = 1; j <= 17; j ++)
			for (int k = 1; k <= 17; k ++)
				V.insert(Num[i] + Num[j] + Num[k]);

	for (auto c : V)
	{
		N --;
		if (!N)
		{
			cout << c << endl;
			return 0;
		}
	}

	return 0;
}

---

D - Erase Leaves

Problem Statement

You are given a tree with $N$ vertices: vertex $1,$ vertex $2$, $\dots$, vertex $N$.
The $i$-th edge $(1\le i<N)$ connects vertex $u_i$ and vertex $v_i$.
Consider repeating the following operation some number of times:
Choose one leaf vertex $v$ and delete it along with all incident edges.
Find the minimum number of operations required to delete vertex $1$.

What is a tree? A tree is an undirected graph that is connected and has no cycles. For more details, see: Wikipedia "Tree (graph theory)". What is a leaf? A leaf in a tree is a vertex with a degree of at most $1$. ### Constraints

$2\le N\le 3\times 10^5$
$1\le u_i<v_i\le N(1\le i<N)$
The given graph is a tree.
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$?$
$u_{N?1}$ $v_{N?1}$

Output

Print the answer in a single line.

Sample Input 1

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

Sample Output 1

5

The given graph looks like this:

For example, you can choose vertices $9,8,7,6,1$ in this order to delete vertex $1$ in five operations.

Vertex $1$ cannot be deleted in four or fewer operations, so print $5$.

Sample Input 2

6
1 2
2 3
2 4
3 5
3 6

Sample Output 2

1

In the given graph, vertex $1$ is a leaf.
Hence, you can choose and delete vertex $1$ in the first operation.

Sample Input 3

24
3 6
7 17
7 20
7 11
14 18
17 21
6 19
5 22
9 24
11 14
6 23
8 17
9 12
4 17
2 15
1 17
3 9
10 16
7 13
2 16
1 16
5 7
1 3

Sample Output 3

12

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <vector>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 3e5 + 10;

int N;
std::vector<int> G[SIZE];
int Sz[SIZE];

void DFS(int u, int fa)
{
	Sz[u] = 1;
	for (auto c : G[u])
	{
		if (c == fa) continue;
		DFS(c, u);
		Sz[u] += Sz[c];
	}
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;

	int u, v;
	for (int i = 1; i < N; i ++)
		cin >> u >> v, G[u].push_back(v), G[v].push_back(u);

	DFS(1, -1);

	if (G[1].size() == 1)
	{
		cout << 1 << endl;
		return 0;
	}

	int Result = -1e18;
	for (auto c : G[1])
		Result = max(Result, Sz[c]);

	cout << N - Result << endl;

	return 0;
}

---

E - Takahashi Quest

Problem Statement

Takahashi will embark on an adventure.
During the adventure, $N$ events will occur.
The $i$-th event $(1\le i\le N)$ is represented by a pair of integers $(t_i,x_i)$ $(1\le t_i\le 2,1\le x_i\le N)$ and is as follows:
If $t_i=1$, he finds one potion of type $x_i$. He can choose to pick it up or discard it.
If $t_i=2$, he encounters one monster of type $x_i$. If he has a potion of type $x_i$, he can use one to defeat the monster. If he does not defeat it, he will be defeated.
Determine whether he can defeat all the monsters without being defeated.
If he cannot defeat all the monsters, print -1.
Otherwise, let $K$ be the maximum number of potions he has at some point during the adventure.
Let $K_{\min }$ be the minimum value of $K$ across all strategies where he will not be defeated.
Print the value of $K_{\min }$ and the actions of Takahashi that achieve $K_{\min }$.

Constraints

$1\le N\le 2\times 10^5$
$1\le t_i\le 2(1\le i\le N)$
$1\le x_i\le N(1\le i\le N)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$t_1$ $x_1$
$t_2$ $x_2$
$?$
$t_N$ $x_N$

Output

If Takahashi cannot defeat all the monsters, print -1.
If he can, print the value of $K_{\min }$ in the first line, and in the second line, for each $i$ such that $t_i=1$ in ascending order, print 1 if he picks up the potion found at the $i$-th event, and 0 otherwise, separated by spaces.
If multiple sequences of actions achieve $K_{\min }$ and allow him to finish the adventure without being defeated, you may print any of them.

Sample Input 1

13
1 2
1 3
1 1
1 3
1 2
2 3
1 3
1 3
2 3
1 3
2 2
2 3
2 1

Sample Output 1

3
1 1 1 0 0 1 0 1

The sample output corresponds to the following actions:
Find potions of types $2,3,1$ in this order. Pick up all of them.
Find potions of types $3,2$ in this order. Do not pick up any of them.
Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
Find a type-$3$ potion. Pick it up.
Find a type-$3$ potion. Do not pick it up.
Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
Find a type-$3$ potion. Pick it up.
Encounter a type-$2$ monster. Use one type-$2$ potion to defeat it.
Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.
Encounter a type-$1$ monster. Use one type-$1$ potion to defeat it.
In this sequence of actions, the value of $K$ is $3$.
There is no way to avoid defeat with $K\le 2$, so the sought value of $K_{\min }$ is $3$.
There are multiple sequences of actions that satisfy $K=3$ and allow him to avoid defeat; you may print any of them.

Sample Input 2

4
2 3
1 4
2 1
1 2

Sample Output 2

-1

He will inevitably be defeated by the first monster he encounters.

Sample Input 3

30
1 25
1 2
1 10
1 18
2 18
1 11
2 11
1 21
1 6
2 2
2 10
1 11
1 24
1 11
1 3
1 2
1 18
2 25
1 8
1 10
1 11
2 18
2 10
1 10
2 2
1 24
1 10
2 10
1 25
2 6

Sample Output 3

4
1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0

Solution

具体见文后视频。

---

Code

#include <iostream>
#include <vector>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10;

int N;
std::vector<PII> OP[SIZE], TOP;
int Result[SIZE];

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;

	int idx = 0;
	for (int i = 1; i <= N; i ++)
	{
		int T, X;
		cin >> T >> X;
		TOP.push_back({T, X});
		if (T == 1)
			OP[X].push_back({1, ++ idx});
		else
			OP[X].push_back({-1, 0});
	}

	for (int i = 1; i <= N; i ++)
	{
		vector<int> Ones;
		for (auto c : OP[i])
			if (c.first == -1)
			{
				if (!Ones.size())
				{
					cout << -1 << endl;
					return 0;
				}
				Result[Ones.back()] = 1;
				Ones.pop_back();
			}
			else
				Ones.push_back(c.second);
	}

	int Now = 0, Answer = 0, j = 1;
	for (int i = 1; i <= N; i ++)
	{
		if (TOP[i - 1].first == 2)
			Now --;
		else if (Result[j] == 1)
		{
			Now ++;
			j ++;
			Answer = max(Answer, Now);
		}
		else
			j ++;
		// cout << i << ":" << Now << endl;
	}

	cout << Answer << endl;
	for (int i = 1; i <= idx; i ++)
		cout << Result[i] << " ";

	return 0;
}

---

F - Bomb Game 2

Problem Statement

There are $N$ people standing in a line, with person $i$ standing at the $i$-th position from the front.
Repeat the following operation until there is only one person left in the line:
Remove the person at the front of the line with a probability of $\frac{1}{2}$, otherwise move them to the end of the line.
For each person $i=1,2,\dots ,N$, find the probability that person $i$ is the last person remaining in the line, modulo $998244353$. (All choices to remove or not are random and independent.)

How to find probabilities modulo $998244353$ The probabilities sought in this problem can be proven to always be a rational number. Furthermore, the constraints of this problem guarantee that if the sought probability is expressed as an irreducible fraction $\frac{y}{x}$, then $x$ is not divisible by $998244353$. Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Report this $z$. ### Constraints

$2\le N\le 3000$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer for people $i=1,2,\dots ,N$, separated by spaces.

Sample Input 1

2

Sample Output 1

332748118 665496236

Person $1$ will be the last person remaining in the line with probability $\frac{1}{3}$.
Person $2$ will be the last person remaining in the line with probability $\frac{2}{3}$.

Sample Input 2

5

Sample Output 2

235530465 792768557 258531487 238597268 471060930

Solution

具体见文后视频。

---

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int MOD = 998244353;

const int SIZE = 3e3 + 10;

int N;
int F[SIZE][SIZE];

int qmi(int a, int b, int p)
{
	int Result = 1;
	while (b)
	{
		if (b & 1) Result = Result * a % p;
		a = a * a % p;
		b >>= 1;
	}

	return Result;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> N;

	F[1][1] = 1;
	for (int i = 2; i <= N; i ++)
	{
		int Tmp = qmi(2, i, MOD);
		for (int j = i - 1, k = 2; j >= 1; j --, k ++)
			F[i][1] = (F[i][1] + qmi(qmi(2, k, MOD), MOD - 2, MOD) * F[i - 1][j] % MOD) % MOD;
		F[i][1] = F[i][1] * Tmp % MOD * qmi(Tmp - 1, MOD - 2, MOD) % MOD;

		for (int j = 2; j <= i; j ++)
			F[i][j] = (qmi(2, MOD - 2, MOD) * F[i][j - 1] % MOD + qmi(2, MOD - 2, MOD) * F[i - 1][j - 1] % MOD) % MOD;
	}

	for (int i = 1; i <= N; i ++)
		cout << F[N][i] << " ";

	return 0;
}

视频题解

---

最后祝大家早日