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=\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 $0\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

$1\le N\le 2\times 10^5$
$-10^9\le K\le 10^9$
$-10^9\le A_i\le 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_1^{\prime },A_2^{\prime },\dots ,A_N^{\prime })$ in the following format:

Yes
$A_1^{\prime }$ $A_2^{\prime }$ $\cdots$ $A_N^{\prime }$

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 
#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=(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 $B=1,2,\dots ,M$, the value $X_B$ exists between any two different occurrences of $B$ in $A$ (including both ends).
More formally, for each $B=1,2,\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$ ($l\le m\le r$) such that $A_m=X_B$.

Constraints

$1\le M\le 10$
$1\le N\le 10^4$
$1\le X_i\le 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

14

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

65536

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

628

Solution

具体见文末视频。

Code

#include 
#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|\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 $\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|\le 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 $\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

$2\le N\le 1000$
$1\le R\le 10^9$
$|A_i|\le R$
$\left|\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 $\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 $P\ge 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 $\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$.

Solution

具体见文末视频。

---

Code

#include 
#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;
}

---

视频题解

---

最后祝大家早日