AtCoder Regular Contest 179 （ABC题）视频讲解

A - Partition

Problem Statement

You are given integers $N$ and $K$ .
The cumulative sums of an integer sequence $X=(X_1,X_2,\dots ,X_N)$ of length $N$ is defined as a sequence $Y=(Y_0,Y_1,\dots ,Y_N)$ of length $N + 1$ as follows:
$Y_0=0$
$Y_i=\displaystyle\sum_{j=1}^{i}X_j\ (i=1,2,\dots ,N)$
An integer sequence $X=(X_1,X_2,\dots ,X_N)$ of length $N$ is called a good sequence if and only if it satisfies the following condition:
Any value in the cumulative sums of $X$ that is less than $K$ appears before any value that is not less than $K$ .
Formally, for the cumulative sums $Y$ of $X$ , for any pair of integers $(i, j)$ such that $\le i,j \le N$ , if $KaTeX parse error: Expected 'EOF', got '&' at position 6: (Y_i &̲lt; K$ and $Y_j \ge K)$ , then $KaTeX parse error: Expected 'EOF', got '&' at position 3: i &̲lt; j$ .
You are given an integer sequence $A=(A_1,A_2,\dots ,A_N)$ of length $N$ . Determine whether the elements of $A$ can be rearranged to a good sequence. If so, print one such rearrangement.

Constraints

$\leq N \leq 2 \times 10^5$
$-10^9 \leq K \leq 10^9$
$-10^9 \leq A_i \leq 10^9$
All input values are integers.

Input

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

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

If the elements of $A$ can be rearranged to a good sequence, print the rearranged sequence $(A^{\prime}_1,A^{\prime}_2,\dots ,A^{\prime}_N)$ in the following format:

Yes
$A^{\prime}_1$ $A^{\prime}_2$ $\cdots$ $A^{\prime}_N$

If there are multiple valid rearrangements, any of them is considered correct.
If a good sequence cannot be obtained, print No.

Sample Input 1

4 1
-1 2 -3 4

Sample Output 1

Yes
-3 -1 2 4

If you rearrange $A$ to $(- 3, - 1, 2, 4)$ , the cumulative sums $Y$ in question will be $(0, - 3, - 4, - 2, 2)$ . In this $Y$ , any value less than $1$ appears before any value not less than $1$ .

Sample Input 2

4 -1
1 -2 3 -4

Sample Output 2

No

Sample Input 3

10 1000000000
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

Yes
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

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

	int n, k, sum = 0;
	cin >> n >> k;

	std::vector<int> a(n);
	for (int i = 0; i < n; i ++)
		cin >> a[i], sum += a[i];

	if (sum < k	&& k <= 0) {
		cout << "No" << endl;
		return 0;
	}

	if (k > 0) sort(a.begin(), a.end());
	else sort(a.begin(), a.end(), greater<int>());
	cout << "Yes" << endl;
	for (int i = 0; i < n; i ++)
		cout << a[i] << " ";
	cout << endl;

	return 0;
}

B - Between B and B

Problem Statement

You are given a sequence $(X_1, X_2, \dots, X_M)$ of length $M$ consisting of integers between $1$ and $M$ , inclusive.
Find the number, modulo $998244353$ , of sequences $(A_1, A_2, \dots, A_N)$ of length $N$ consisting of integers between $1$ and $M$ , inclusive, that satisfy the following condition:
For each $\dots, M$ , the value $X_B$ exists between any two different occurrences of $B$ in $A$ (including both ends).
More formally, for each $\dots, M$ , the following condition must hold:
For every pair of integers $(l, r)$ such that $KaTeX parse error: Expected 'EOF', got '&' at position 10: 1 \leq l &̲lt; r \leq N$ and $A_l = A_r = B$ , there exists an integer $m$ ( $\leq m \leq r$ ) such that $A_m = X_B$ .

Constraints

$\leq M \leq 10$
$\leq N \leq 10^4$
$\leq X_i \leq M$
All input values are integers.

Input

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

$M$ $N$
$X_1$ $X_2$ $\cdots$ $X_M$

Output

Print the answer.

Sample Input 1

3 4
2 1 2

Sample Output 1

Here are examples of sequences $A$ that satisfy the condition:
$(1, 3, 2, 3)$
$(2, 1, 2, 1)$
$(3, 2, 1, 3)$
Here are non-examples:
$(1, 3, 1, 3)$
There is no $X_3 = 2$ between the $3$ s.
$(2, 2, 1, 3)$
There is no $X_2 = 1$ between the $2$ s.

Sample Input 2

4 8
1 2 3 4

Sample Output 2

All sequences of length $8$ consisting of integers between $1$ and $4$ satisfy the condition.
Note that when $X_B = B$ , there is always a $B$ between two different occurrences of $B$ .

Sample Input 3

4 9
2 3 4 1

Sample Output 3

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 1e4 + 10, M = 11, mod = 998244353;

int n, m;
int a[M], f[N][1 << M], mask[M];

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

	cin >> m >> n;

	for (int i = 1; i <= m; i ++)
		cin >> a[i], mask[a[i]] |= 1ll << i - 1;

	f[0][(1 << m) - 1] = 1;
	for (int i = 0; i < n; i ++)
		for (int j = 1; j <= m; j ++)
			for (int k = 0; k < 1 << m; k ++)
				if ((k >> j - 1) & 1)
					f[i + 1][(k ^ (1 << j - 1)) | mask[j]] = (f[i + 1][(k ^ (1 << j - 1)) | mask[j]] + f[i][k]) % mod;

	int res = 0;
	for (int i = 0; i < 1 << m; i ++)
		res = (res + f[n][i]) % mod;

	cout << res << endl;

	return 0;
}

C - Beware of Overflow

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).
You are given a positive integer $N$ .
The judge has a hidden positive integer $R$ and $N$ integers $A_1, A_2, \dots, A_N$ . It is guaranteed that $|A_i|\le R$ and $\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R$ .
There is a blackboard on which you can write integers with absolute values not exceeding $R$ . Initially, the blackboard is empty.
The judge has written the values $A_1, A_2, \dots, A_N$ on the blackboard in this order. Your task is to make the blackboard contain only one value $\displaystyle\sum_{i=1}^{N}A_i$ .
You cannot learn the values of $R$ and $A_i$ directly, but you can interact with the judge up to $25000$ times.
For a positive integer $i$ , let $X_i$ be the $i$ -th integer written on the blackboard. Specifically, $X_i = A_i$ for $i=1,2,\dots,N$ .
In one interaction, you can specify two distinct positive integers $i$ and $j$ and choose one of the following actions:
Perform addition. The judge will erase $X_i$ and $X_j$ from the blackboard and write $X_i + X_j$ on the blackboard.
$|X_i + X_j| \leq R$ must hold.
Perform comparison. The judge will tell you whether $KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j$ is true or false.
Here, at the beginning of each interaction, the $i$ -th and $j$ -th integers written on the blackboard must not have been erased.
Perform the interactions appropriately so that after all interactions, the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$ .
The values of $R$ and $A_i$ are determined before the start of the conversation between your program and the judge.

Constraints

$\leq N \leq 1000$
$\leq R \leq 10^9$
$|A_i| \leq R$
$\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R$
$N$ , $R$ , and $A_i$ are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).
First, read $N$ from Standard Input.

$N$

Next, repeat the interactions until the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$ .
When performing addition, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

$i$ $j$

The response from the judge will be given from Standard Input in the following format:

$P$

Here, $P$ is an integer:
If $\geq N + 1$ , it means that the value $X_i + X_j$ has been written on the blackboard, and it is the $P$ -th integer written.
If $P = - 1$ , it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$ .
When performing comparison, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

? $i$ $j$

The response from the judge will be given from Standard Input in the following format:

$Q$

Here, $Q$ is an integer:
If $Q = 1$ , it means that $KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j$ is true.
If $Q = 0$ , it means that $KaTeX parse error: Expected 'EOF', got '&' at position 5: X_i &̲lt; X_j$ is false.
If $Q = - 1$ , it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$ .
For both types of interactions, if the judge’s response is $- 1$ , your program is already considered incorrect. In this case, terminate your program immediately.
When the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$ , report this to the judge in the following format. This does not count towards the number of interactions. Then, terminate your program immediately.

If you make an output in a format that does not match any of the above, -1 will be given from Standard Input.

-1

In this case, your program is already considered incorrect. Terminate your program immediately.

Notes

For each output, append a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
Terminate your program immediately after outputting the result (or receiving -1). Otherwise, the verdict will be indeterminate.
Extra newlines will be considered as malformed output.

Sample Input and Output

Here is a possible conversation with $N=3, R=10, A_1=-1, A_2=10, A_3=1$ .

Input	Output	Explanation
`3`		First, the integer $N$ is given.
	`? 1 2`	Perform a comparison.
`1`		The judge returns $1$ because $X_1\lt X_2\ (-1\lt 10)$.
	`+ 1 3`	Perform an addition.
`4`		The judge erases $X_1 = -1$ and $X_3 = 1$ from the blackboard and writes $X_1 + X_3 = 0$. This is the fourth integer written.
	`+ 2 4`	Perform an addition.
`5`		The judge erases $X_2 = 10$ and $X_4 = 0$ from the blackboard and writes $X_2 + X_4 = 10$. This is the fifth integer written.
	`!`	The blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$, so report this to the judge.

Solution

具体见文末视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

bool cmp(int a, int b) {
	cout << "? " << a << " " << b << endl;
	int ok;
	cin >> ok;
	return ok;
}

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

	int n;
	cin >> n;

	std::vector<int> id;
	for (int i = 1; i <= n; i ++)
		id.push_back(i);
	sort(id.begin(), id.end(), cmp);
	while (n > 1) {
		cout << "+ " << id[0] << " " << id.back() << endl;
		int p;
		cin >> p;
		id.erase(id.begin()), id.pop_back();
		n --;
		if (n == 1) break;
		int l = 0, r = id.size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (cmp(p, id[mid])) r = mid;
			else l = mid + 1;
		}
		if (!cmp(p, id[r])) r ++;
		id.insert(id.begin() + r, p);
	}

	cout << "!\n";

	return 0;
}