Atcoder Beginner Contest 332

A - Online Shopping

Problem Statement

AtCoder Inc. sells merchandise through its online shop.

Takahashi has decided to purchase $N$ types of products from there.
For each integer $i$ from $1$ to $N$, the $i$-th type of product has a price of $P_i$ yen each, and he will buy $Q_i$ of this.

Additionally, he must pay a shipping fee.
The shipping fee is $0$ yen if the total price of the products purchased is $S$ yen or above, and $K$ yen otherwise.

He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.

Constraints

• $1\le N\le 100$
• $1\le S\le 10000$
• $1\le K\le 10000$
• $1\le P_i\le 10000$
• $1\le Q_i\le 100$
• All input values are integers.

Input

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

$N$ $S$ $K$
$P_1$ $Q_1$
$P_2$ $Q_2$
$?$
$P_N$ $Q_N$

Output

Print the amount Takahashi will pay for online shopping.

Sample Input 1

2 2000 500
1000 1
100 6

Sample Output 1

2100

Takahashi buys one product for $1000$ yen and six products for $100$ yen each.
Thus, the total price of the products is $1000\times 1+100\times 6=1600$ yen.
Since the total amount for the products is less than $2000$ yen, the shipping fee will be $500$ yen.
Therefore, the amount Takahashi will pay is $1600+500=2100$ yen.

Sample Input 2

3 2000 500
1000 1
100 6
5000 1

Sample Output 2

6600

The total price of the products is $1000\times 1+100\times 6+5000\times 1=6600$ yen.
Since the total amount for the products is not less than $2000$ yen, the shipping fee will be $0$ yen.
Therefore, the amount Takahashi will pay is $6600+0=6600$ yen.

Sample Input 3

2 2000 500
1000 1
1000 1

Sample Output 3

2000

There may be multiple products with the same price per item.

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, S, K;

	cin >> N >> S >> K;

	int Sum = 0, P, Q;
	for (int i = 1; i <= N; i ++)
		cin >> P >> Q, Sum += P * Q;

	if (Sum < S) cout << Sum + K << endl;
	else cout << Sum << endl;

	return 0;
}

B - Glass and Mu

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of $G$ milliliters and a mug with a capacity of $M$ milliliters.
Here, $G<M$.

Initially, both the glass and the mug are empty.
After performing the following operation $K$ times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly $G$ milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• $1\le K\le 100$
• $1\le G<M\le 1000$
• $G$, $M$, and $K$ are integers.

Input

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

$K$ $G$ $M$

Output

Print the amounts, in milliliters, of water in the glass and the mug, in this order, separated by a space, after performing the operation $K$ times.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has $0$ milliliters, and the mug has $500$ milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has $300$ milliliters, and the mug has $200$ milliliters of water.
• Discard all the water from the glass. The glass has $0$ milliliters, and the mug has $200$ milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has $200$ milliliters, and the mug has $0$ milliliters of water.
• Fill the mug with water. The glass has $200$ milliliters, and the mug has $500$ milliliters of water.

Thus, after five operations, the glass has $200$ milliliters, and the mug has $500$ milliliters of water. Hence, print $200$ and $500$ in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

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 K, M, G;

	cin >> K >> G >> M;

	int A = 0, B = 0;
	while (K --)
	{
		if (A == G) A = 0;
		else if (B == 0) B = M;
		else
		{
			int Push = min(G - A, B);
			A += Push, B -= Push;
		}
	}

	cout << A << " " << B << endl;

	return 0;
}

C - T-shirts

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi’s schedule for $N$ days as a string $S$ of length $N$ consisting of 0, 1, and 2.
Specifically, for an integer $i$ satisfying $1\le i\le N$,

• if the $i$-th character of $S$ is 0, he has no plan scheduled for the $i$-th day;
• if the $i$-th character of $S$ is 1, he plans to go out for a meal on the $i$-th day;
• if the $i$-th character of $S$ is 2, he plans to attend a competitive programming event on the $i$-th day.

Takahashi has $M$ plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the $N$ days. If he does not need to buy new T-shirts, print $0$.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• $1\le M\le N\le 1000$
• $S$ is a string of length $N$ consisting of 0, 1, and 2.
• $N$ and $M$ are integers.

Output

Print the minimum number of T-shirts Takahashi needs to buy to be able to satisfy the conditions in the problem statement.
If he does not need to buy new T-shirts, print $ 0$.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print $2$.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

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, M;
	string S;

	cin >> N >> M >> S;

	S = ' ' + S;
	int Plain = M, Logo = 0, TL = 0;
	for (int i = 1; i <= N; i ++)
		if (S[i] == '1')
		{
			if (Plain)
				Plain --;
			else
				if (Logo) Logo --;
				else TL ++;
		}
		else if (S[i] == '2')
		{
			if (Logo) Logo --;
			else TL ++;
		}
		else
			Plain = M, Logo = TL;

	cout << TL << endl;

	return 0;
}

D - Swapping Puzzle

Problem Statement

You are given two grids, A and B, each with $H$ rows and $W$ columns.

For each pair of integers $(i,j)$ satisfying $1\le i\le H$ and $1\le j\le W$, let $(i,j)$ denote the cell in the $i$-th row and $j$-th column. In grid A, cell $(i,j)$ contains the integer $A_{i,j}$. In grid B, cell $(i,j)$ contains the integer $B_{i,j}$.

You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:

• Choose an integer $i$ satisfying $1\le i\le H?1$ and swap the $i$-th and $(i+1)$-th rows in grid A.
• Choose an integer $i$ satisfying $1\le i\le W?1$ and swap the $i$-th and $(i+1)$-th columns in grid A.

Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.

Here, grid A is identical to grid B if and only if, for all pairs of integers $(i,j)$ satisfying $1\le i\le H$ and $1\le j\le W$, the integer written in cell $(i,j)$ of grid A is equal to the integer written in cell $(i,j)$ of grid B.

Constraints

• All input values are integers.
• $2\le H,W\le 5$
• $1\le A_{i,j},B_{i,j}\le 10^9$

Input

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

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $?$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $?$ $A_{2,W}$
$?$
$A_{H,1}$ $A_{H,2}$ $?$ $A_{H,W}$
$B_{1,1}$ $B_{1,2}$ $?$ $B_{1,W}$
$B_{2,1}$ $B_{2,2}$ $?$ $B_{2,W}$
$?$
$B_{H,1}$ $B_{H,2}$ $?$ $B_{H,W}$

Output

If it is impossible to make grid A identical to grid B, output -1. Otherwise, print the minimum number of operations required to make grid A identical to grid B.

Sample Input 1

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

Sample Output 1

3

Swapping the fourth and fifth columns of the initial grid A yields the following grid:

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

Then, swapping the second and third rows yields the following grid:

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

Finally, swapping the second and third columns yields the following grid, which is identical to grid B:

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

You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print $3$.

Sample Input 2

2 2
1 1
1 1
1 1
1 1000000000

Sample Output 2

\-1

There is no way to perform the operation to make grid A match grid B, so print -1.

Sample Input 3

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

Sample Output 3

0

Grid A is already identical to grid B at the beginning.

Sample Input 4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

Sample Output 4

20

Solution

具体见文后视频。

---

Code

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

using namespace std;

typedef pair<int, int> PII;
typedef vector<vector<int>> VVI;

int N, M;
VVI A, B;
map<VVI, int> Vis, Dist;

int BFS()
{
	queue<VVI> Q;
	Q.push(A), Vis[A] = 1;

	while (Q.size())
	{
		auto T = Q.front();
		Q.pop();

		if (T == B) return Dist[T];

		VVI Source = T;
		for (int i = 1; i < N; i ++)
		{
			for (int j = 1; j <= M; j ++)
				swap(T[i][j], T[i + 1][j]);
			if (!Vis.count(T)) Q.push(T), Vis[T] = 1, Dist[T] = Dist[Source] + 1;
			T = Source;
		}
		for (int j = 1; j < M; j ++)
		{
			for (int i = 1; i <= N; i ++)
				swap(T[i][j], T[i][j + 1]);
			if (!Vis.count(T)) Q.push(T), Vis[T] = 1, Dist[T] = Dist[Source] + 1;
			T = Source;
		}
	}

	return -1;
}

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

	cin >> N >> M;

	A.resize(N + 1), B.resize(N + 1);
	for (int i = 1; i <= N; i ++)
		A[i].resize(M + 1), B[i].resize(M + 1);
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			cin >> A[i][j];
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= M; j ++)
			cin >> B[i][j];

	cout << BFS() << endl;

	return 0;
}

E - Lucky bag

Problem Statement

AtCoder Inc. sells merchandise on its online shop.

There are $N$ items remaining in the company. The weight of the $i$-th item $(1\le i\le N)$ is $W_i$.

Takahashi will sell these items as $D$ lucky bags.
He wants to minimize the variance of the total weights of the items in the lucky bags.
Here, the variance is defined as $V=\frac{1}{D}\sum _{i=1}^D(x_i?\bar{x}{)}^2$, where $x_1,x_2,\dots ,x_D$ are the total weights of the items in the lucky bags, and $\bar{x}=\frac{1}{D}(x_1+x_2+?+x_D)$ is the average of $x_1,x_2,\dots ,x_D$.

Find the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
It is acceptable to have empty lucky bags (in which case the total weight of the items in that bag is defined as $0$),
but each item must be in exactly one of the $D$ lucky bags.

Constraints

• $2\le D\le N\le 15$
• $1\le W_i\le 10^8$
• All input values are integers.

Input

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

$N$ $D$
$W_1$ $W_2$ $\dots$ $W_N$

Output

Print the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
Your output will be considered correct if the absolute or relative error from the true value is at most $10^{?6}$.

Sample Input 1

5 3
3 5 3 6 3

Sample Output 1

0.888888888888889

If you put the first and third items in the first lucky bag, the second and fifth items in the second lucky bag, and the fourth item in the third lucky bag, the total weight of the items in the bags are $6$, $8$, and $6$, respectively.

Then, the average weight is $\frac{1}{3}(6+8+6)=\frac{20}{3}$,
and the variance is $\frac{1}{3}\left\{{\left(6?\frac{20}{3}\right)}^2+{\left(8?\frac{20}{3}\right)}^2+{\left(6?\frac{20}{3}\right)}^2\right\}=\frac{8}{9}=0.888888\dots$, which is the minimum.

Note that multiple items may have the same weight, and that each item must be in one of the lucky bags.

Solution

具体见文后视频。

---

Code

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

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 17;

int N, D;
int W[SIZE], Sum[1ll << SIZE];
double F[SIZE][1ll << SIZE];

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

	cin >> N >> D;

	for (int i = 1; i <= N; i ++)
		cin >> W[i];

	for (int i = 0; i < 1 << N; i ++)
		for (int j = 0; j < N; j ++)
			if (i >> j & 1)
				Sum[i] += W[j + 1];

	double Ave = Sum[(1 << N) - 1] * 1.0 / D;
	for (int i = 0; i <= D; i ++)
		for (int j = 0; j < 1 << N; j ++)
			F[i][j] = 1e18;
	F[0][0] = 0;
	for (int i = 1; i <= D; i ++)
		for (int j = 0; j < 1 << N; j ++)
			for (int k = j; k; k = k - 1 & j)
			{
				int Left = j ^ k;
				if (F[i - 1][Left] == 1e18) continue;
				F[i][j] = min(F[i][j], F[i - 1][Left] + 1.0 * (Sum[k] * 1.0 - Ave) * (Sum[k] * 1.0 - Ave));
			}

	printf("%.8lf\n", F[D][(1 << N) - 1] * 1.0 / D);

	return 0;
}
}

F - Random Update Query

Problem Statement

You are given an integer sequence $A=(A_1,A_2,\dots ,A_N)$ of length $N$.

We will perform the following operation on $A$ for $i=1,2,\dots ,M$ in this order.

• First, choose an integer between $L_i$ and $R_i$, inclusive, uniformly at random and denote it as $p$.
• Then, change the value of $A_p$ to the integer $X_i$.

For the final sequence $A$ after the above procedure, print the expected value, modulo $998244353$, of $A_i$ for each $i=1,2,\dots ,N$.

How to print expected values modulo $998244353$

It can be proved that the expected values sought in this problem are always rational. Furthermore, the constraints of this problem guarantee that if each of those expected values 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(\mathrm{mod}998244353)$. Report this $z$.

Constraints

• All input values are integers.
• $1\le N,M\le 2\times 10^5$
• $0\le A_i\le 10^9$
• $1\le L_i\le R_i\le N$
• $0\le X_i\le 10^9$

Input

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

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$?$
$L_M$ $R_M$ $X_M$

Output

Print the expected values $E_i$ of the final $A_i$ for $i=1,2,\dots ,N$ in the format below, separated by spaces.

$E_1$ $E_2$ $\dots$ $E_N$

Sample Input 1

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

Sample Output 1

499122179 1 665496238 665496236 5

We start from the initial state $A=(3,1,4,1,5)$ and perform the following two operations.

• The first operation chooses $A_1$ or $A_2$ uniformly at random, and changes its value to $2$.
• Then, the second operation chooses one of $A_2,A_3,A_4$ uniformly at random, and changes its value to $0$.

As a result, the expected values of the elements in the final $A$ are $(E_1,E_2,E_3,E_4,E_5)=(\frac{5}{2},1,\frac{8}{3},\frac{2}{3},5)$.

Sample Input 2

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

Sample Output 2

5 6

Sample Input 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

Sample Output 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158

Solution

具体见文后视频。

---

Code

#include <iostream>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int SIZE = 2e5 + 10, MOD = 998244353;

int N, M;
int A[SIZE];
struct Node
{
    int l, r;
    int sum, add, mul;
}Tree[SIZE * 4];

void Pushup(int u)
{
    Tree[u].sum = (Tree[u << 1].sum + Tree[u << 1 | 1].sum) % MOD;
}

void Eval(Node &tree, int add, int mul)
{
    tree.sum = (tree.sum * mul + (tree.r - tree.l + 1) * add) % MOD;
    tree.mul = (tree.mul * mul) % MOD;
    tree.add = (tree.add * mul + add) % MOD;
}

void Pushdown(int u)
{
    Eval(Tree[u << 1], Tree[u].add, Tree[u].mul);
    Eval(Tree[u << 1 | 1], Tree[u].add, Tree[u].mul);
    Tree[u].add = 0, Tree[u].mul = 1;
}

void Build(int u, int l, int r)
{
    if (l == r) Tree[u] = {r, r, A[r], 0, 1};
    else
    {
        Tree[u] = {l, r, 0, 0, 1};
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        Pushup(u);
    }
}

void Modify(int u, int l, int r, int add, int mul)
{
    if (Tree[u].l >= l && Tree[u].r <= r) Eval(Tree[u], add, mul);
    else
    {
        Pushdown(u);
        int mid = Tree[u].l + Tree[u].r >> 1;
        if (l <= mid) Modify(u << 1, l, r, add, mul);
        if (r > mid) Modify(u << 1 | 1, l, r, add, mul);
        Pushup(u);
    }
}

int Query(int u, int l, int r)
{
    if (Tree[u].l >= l && Tree[u].r <= r) return Tree[u].sum;

    Pushdown(u);
    int mid = Tree[u].l + Tree[u].r >> 1, sum = 0;
    if (l <= mid) sum = Query(u << 1, l, r);
    if (r > mid) sum = (sum + Query(u << 1 | 1, l, r)) % MOD;
    return sum;
}
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 >> M;

	for (int i = 1; i <= N; i ++)
		cin >> A[i];

	Build(1, 1, N);

	while (M --)
	{
		int l, r, x;

		cin >> l >> r >> x;

		Modify(1, l, r, 0, (r - l) * qmi(r - l + 1, MOD - 2, MOD) % MOD);
		Modify(1, l, r, x * qmi(r - l + 1, MOD - 2, MOD) % MOD, 1);
	}

	for (int i = 1; i <= N; i ++)
		cout << Query(1, i, i) % MOD << " ";

	return 0;
}

视频题解

---

最后祝大家早日