ARC104 题解
目录ARC回来了？！
A - Plus Minus
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100 points
Problem Statement
Takahashi has two integers X and Y.He computed \(X + Y\) and \(X - Y\), and the results were A and B, respectively.
Now he cannot remember what X and Y were. Find X and Y for him.
Constraints
- \(-100 \leq A, B \leq 100\)
- For the given integers A and B, there uniquely exist integers X and Y such that \(X + Y = A\) and \(X - Y = B\).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print X and Y.
Samples
Sample Input 1
2 -2
Sample Output 1
0 2
If X = 0 and Y = 2, they match the situation: \(0 + 2 = 2 \ \ \operatorname{and}\ \ 0 - 2 = -2\).
Sample Input 2
3 1
Sample Output 2
2 1
题面
高桥有两个整数X和Y，他计算了\(X+Y\)和\(X-Y\)，结果分别是A和B。
现在他不记得X和Y是什么了。为他找到X和Y。
解题思路
\[\begin{align} (A\ge B) \begin{cases} A+B=C\\ A-B=D \end{cases} \Rightarrow \begin{cases} A=\dfrac{C+D}2\\ B=\dfrac{C-D}2 \end{cases} \end{align} \]AC Code
#include<iostream>
using namespace std;
int main(){
int c,d;
cin>>c>>d;
cout<<(c+d)/2<<endl<<(c-d)/2<<endl;
return 0;
}
A, B = map(int, input().split())
print((A + B) // 2, (A - B) // 2)
B - DNA Sequence
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 400 points
Problem Statement
We have a string S of length N consisting of A, T, C, and G.
Strings \(T_1\) and \(T_2\) of the same length are said to be complementary when, for every \(i (1 \leq i \leq l)\), the i-th character of \(T_1\) and the i-th character of \(T_2\) are complementary. Here, A and T are complementary to each other, and so are C and G.
Find the number of non-empty contiguous substrings T of S that satisfies the following condition:
- There exists a string that is a permutation of T and is complementary to T.
Here, we distinguish strings that originate from different positions in S, even if the contents are the same.
Constraints
- \(1 \leq N \leq 5000\)
- S consists of
A,T,C, andG.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of non-empty contiguous substrings T of S that satisfies the condition.
Samples
Sample Input 1
4 AGCT
Sample Output 1
2
The following two substrings satisfy the condition:
-
GC(the 2-nd through 3-rd characters) is complementary toCG, which is a permutation ofGC. -
AGCT(the 1-st through 4-th characters) is complementary toTCGA, which is a permutation ofAGCT.
Sample Input 2
4 ATAT
Sample Output 2
4
The following four substrings satisfy the condition:
-
AT(the 1-st through 2-nd characters) is complementary toTA, which is a permutation ofAT. -
TA(the 2-st through 3-rd characters) is complementary toAT, which is a permutation ofTA. -
AT(the 3-rd through 4-th characters) is complementary toTA, which is a permutation ofAT. -
ATAT(the 1-st through 4-th characters) is complementary toTATA, which is a permutation ofATAT.
题面
我们有一个长度为N的字符串S，由A, T, C, 和G组成.
当对于每一个\(i（1\leq i\leq l）\)，\(T_1\)的第i个字符和\(T_2\)的第i个字符"互补"，长度相同的字符串\(T_1\)和\(T_2\)称为互补字符串。在这里，A和T是互补的，C和G也是互补的。
求满足以下条件的S的非空连续子串T的个数：
- 有一个字符串，它是T的一个排列，与T“互补”。
这里，我们区分来自S中不同位置的字符串，即使内容相同。
解题思路
First, let us consider what kinds of strings satisfy the condition.
-
Ais complementary toT -
Tis complementary toA -
Cis complementary toG -
Gis complementary toC
Thus, it is necessary and sufficient that:
- (the number of
A) = (the number ofT) - (the number of
C) = (the number ofG)
To check if each segment satisfies these conditions, we can, for example, process the segments with the same left end together to solve the problem in a total of \(\mathrm{O}(N^2)\) time.
只要保证在这个字符串s中，A的数量=T的数量，C的数量=G的数量。为了检查每个段是否满足这些条件，我们可以，例如，将具有相同左端的段一起处理以在总计\(\mathrm{O}（N^2）\)时间内解决问题。
$ N \leq 2 \times 10^5 $
AC Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
string S;
cin >> N >> S;
int ans = 0;
for (int i = 0; i < N; ++i) {
int c1 = 0, c2 = 0;
for (int j = i; j < N; ++j) {
if (S[j] == 'A')
c1++;
else if (S[j] == 'T')
c1--;
else if (S[j] == 'C')
c2++;
else
c2--;
if (c1 == 0 && c2 == 0) ans++;
}
}
cout << ans << endl;
return 0;
}
n, s = input().split()
n = int(n)
at = 0
cg = 0
from collections import Counter
d = Counter([(0, 0)])
ans = 0
for ss in s:
if ss == 'A': at += 1
if ss == 'T': at -= 1
if ss == 'C': cg += 1
if ss == 'G': cg -= 1
ans += d[(at, cg)]
d[(at, cg)] += 1
print(ans)
C - Fair Elevator
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 600 points
Problem Statement
There is a building with 2N floors, numbered $1, 2, \ldots, 2N $from bottom to top.
The elevator in this building moved from Floor 1 to Floor 2N just once.
On the way, N persons got on and off the elevator. Each person \(i (1 \leq i \leq N)\) got on at Floor \(A_i\) and off at Floor \(B_i\). Here, \(1 \leq A_i < B_i \leq 2N\), and just one person got on or off at each floor.
Additionally, because of their difficult personalities, the following condition was satisfied:
Let \(C_i (= B_i - A_i - 1)\) be the number of times, while Person i were on the elevator, other persons got on or off. Then, the following holds:
- If there was a moment when both Person i and Person j were on the elevator, \(C_i = C_j\).
We recorded the sequences A and B, but unfortunately, we have lost some of the records. If the record of \(A_i\) or \(B_i\) is lost, it will be given to you as -1.
Additionally, the remaining records may be incorrect.
Determine whether there is a pair of A and B that is consistent with the remaining records.
Constraints
- \(1 \leq N \leq 100\)
- \(A_i = -1 \ \ or \ \ 1 \leq A_i \leq 2N.\)
- \(B_i = -1\ \ or\ \ 1 \leq B_i \leq 2N\).
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
:
A_N B_N
Output
If there is a pair of A and B that is consistent with the remaining records, print Yes; otherwise, print No.
Samples
Sample Input 1
3
1 -1
-1 4
-1 6
Sample Output 1
Yes
For example, if \(B_1 = 3, A_2 = 2\), and \(A_3 = 5\), all the requirements are met.
In this case, there is a moment when both Person 1 and Person 2 were on the elevator, which is fine since \(C_1 = C_2 = 1\).
Sample Input 2
2
1 4
2 3
Sample Output 2
No
There is a moment when both Person 1 and Person 2 were on the elevator. Since \(C_1 = 2, C_2 = 0\), some of the information is incorrect.
Sample Input 3
2
4 1
2 4
Sample Output 3
No
The records are seemingly intact but clearly are incorrect.
题面
There is a building with 2N2N floors, numbered 1,2,…,2N1,2,…,2N from bottom to top.
有一个2N 层的建筑，从下到上编号为1,2，点，2 n。
The elevator in this building moved from Floor 11 to Floor 2N2N just once.
这栋楼里的电梯只从一层搬到了二层 n。
On the way, NN persons got on and off the elevator. Each person ii (1≤i≤N)(1≤i≤N) got on at Floor AiAi and off at Floor BiBi. Here, 1≤Ai<Bi≤2N1≤Ai<Bi≤2N, and just one person got on or off at each floor.
在路上，有 n 个人进出电梯。每个人在 a _ i 层上车，在 b _ i 层下车。在这里，每层楼只有一个人上下车。
Additionally, because of their difficult personalities, the following condition was satisfied:
此外，由于他们的性格特点，下列条件得到了满足:
- Let \(C_i (= B_i - A_i - 1)\) be the number of times, while Person i were on the elevator, other persons got on or off. Then, the following holds:
- If there was a moment when both Person i and Person j were on the elevator, \(C_i = C_j\).
我们记录了 a 和 b 序列，但不幸的是，我们丢失了一些记录。如果 a _ i 或 b _ i 的记录丢失，它将作为 -1给你。
此外，其余的记录可能是不正确的。
确定是否存在一对与其余记录一致的 a 和 b。
解题思路
https://atcoder.jp/contests/arc104/editorial/162
First, let us sort out the conditions. Assume that:
- \(A_i < B_i\)
- \(A_1, B_1, A_2, B_2 \cdots, A_N, B_N\) are all different.
Let us say that the person who got on at Floor 1 gets off at Floor x. Then, we can see that the persons who got on at Floor \(2, 3, \cdots, x-1\) get off at Floor \(x + 1, x + 2, \cdots, 2x-2\).
By repeating this argument, we can see that the condition is satisfied if and only if it is possible to divide the 2N floors into segments where the persons with \((A, B) = (x, x+k), (x+1, x+k+1), \cdots, (x+k-1, x+2k-1)\) get on and off.
Now, let us think of a way to determine, for a fixed division, if it is possible to fill in A and B so that the above holds.
Let us make an array that stores (left/right, the person's ID) for each floor if there is a person bound to get on/off on that floor.
For each segment, the following is necessary:
- There is no person with fixed A and B such that only one of them is contained in the segment. If a person has both A and B in the segment, they are in the correct positions.
- If the persons who got on/off at Floor x+i/x+k+i are both already fixed, they are the same person.
- There is no pair of floors (x+i, x+k+i) such that the person at Floor x+i is "left."
- There is no pair of floors (x+i, x+k+i) such that the person at Floor x+k+i is "right."
On the other hand, if the above is satisfied for every segment, we can find one correct record by filling in A and B properly.
Thus, the problem can be solved by DP. Let \(dp[i]:= (\texttt{true if a segment ends exactly at Floor i and there is no contradiction until Floor i, false otherwise})\), and make dp[r] true when a new segment [i+1, r] has no contradiction.
The time complexity is \(\mathrm{O}(N^3)\).
AC Code
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n;
bool f[N];//[1, i] 是否恰好能合法填充
int com[N];//配对位置
int id[N];//此位置对应的人的编号
int g[N];//此位置是左 1 / 右 0 端点
int vis[N];//此位置是否被占
bool ok = true;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
if (a != -1) {
if (vis[a]) ok = false;
vis[a] = 1, id[a] = i, g[a] = 1;
}
if (b != -1) {
if (vis[b]) ok = false;
vis[b] = 1, id[b] = i, g[b] = 0;
}
if (a != -1 && b != -1) {
if (a > b) ok = false;
com[a] = b, com[b] = a;
}
}
if (!ok) {
puts("No");
return 0;
}
n <<= 1;
f[0] = 1;
for (int i = 0; i <= n; i += 2) {//奇数必定不是结尾, 故 += 2
if (!f[i]) continue;//此状态不合法, 自然无法用它推别人
for (int j = i+2; j <= n; j += 2) {//更新 f[j]
ok = 1;
for (int p = i+1, q = i+1+(j-i)/2; q <= j; p++, q++) {//枚举 [i+1, j] 中需要配对的点对;可以不考虑间距不为 (j-i)/2 的点对, 因为在(j-i)/2为相应的值时会更新
if (vis[p] && vis[q]) {//两位置均有定好的值
if (id[p] != id[q]) {
ok = false;
break;
}
//不用判断是否满足左右关系, 因为输入时已经判过了
}
else if (vis[p]) {//p 有定好的值
if (com[p] || g[p] == 0) {//p有对应的值, 那么必定不是 q ; p是定好的右端点, 那必定不符
ok = false;
break;
}
}
else if (vis[q]) {
if (com[q] || g[q] == 1) {
ok = false;
break;
}
}
}
if (ok)
f[j] = 1;
}
}
puts(f[n] ? "Yes" : "No");
return 0;
}
D - Multiset Mean
Time Limit: 4 sec / Memory Limit: 1024 MB
Score : 700 points
Problem Statement
Given positive integers N, K and M, solve the following problem for every integer x between 1 and N (inclusive):Find the number, modulo M, of non-empty multisets containing between 0 and K (inclusive) instances of each of the integers \(1, 2, 3 \cdots, N\) such that the average of the elements is x.
Constraints
- \(1 \leq N, K \leq 100\)
- \(10^8 \leq M \leq 10^9 + 9\)
- M is prime.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K M
Output
Use the following format:
c_1
c_2
:
c_N
Here, c_x should be the number, modulo M, of multisets such that the average of the elements is x.
Samples
Sample Input 1
3 1 998244353
Sample Output 1
1
3
1
Consider non-empty multisets containing between 0 and 1 instance(s) of each of the integers between 1 and 3. Among them, there are:
- one multiset such that the average of the elements is \(k = 1: \{1\}\);
- three multisets such that the average of the elements is \(k = 2: \{2\}, \{1, 3\}, \{1, 2, 3\}\);
- one multiset such that the average of the elements is \(k = 3: \{3\}\).
Sample Input 2
1 2 1000000007
Sample Output 2
2
Consider non-empty multisets containing between 0 and 2 instances of each of the integers between 1 and 1. Among them, there are:
- two multisets such that the average of the elements is \(k = 1: \{1\}, \{1, 1\}.\)
Sample Input 3
10 8 861271909
Sample Output 3
8
602
81827
4054238
41331779
41331779
4054238
81827
602
8
解题思路
https://atcoder.jp/contests/arc104/editorial/163
A naive DP would have the count of each number and the sum as the states, but its time complexity would be \mathrm{O}(N^4K^2) even after optimization, which is too slow, so we need to exploit the particular setting.
Let us say we want to count sets whose average is m.
We can consider it as the number of balanced states where there is a straight bar that pivots on a fulcrum at coordinate m, and we attach at most K objects of weight 1 at coordinates 1, 2, \cdots, N. (This is because we can transform (\sum_{x \in S}x ) / |S| = m to (\sum_{x \in S} (x - m) ) = 0.)
An easy-to-implement solution
Let us divide the bar at the fulcrum into the left and right parts. Now we have to choose two subsets from $S = {1,2,\cdots,m-1}, T = {1,2,\cdots,N-m} $so that the sums are equal. Thus, if we precompute \(dp[i][j] := (\texttt{the number of sets totaling j considering} 1,2,\cdots,i)\) for every i and j, we can process the queries in$ \mathrm{O}(N^2K)$ time on average per query. For the precomputation, it is \(dp[i-1][j], dp[i-1][j - i], \cdots, dp[i-1][j - i * K]\) that transition to dp[i][j] above, so we can optimize it by maintaining the sum while "sliding" within each \mod i, and the time complexity will be \(\mathrm{O}(N^3K)\).
AC Code
A solution using Formal Power Series
Even if we do not notice the use of precomputation, we can still maintain the distribution of sums in the left and right parts while shifting the average one by one. (Since the counts are fixed, the relative distribution only changes at both ends.)
If we think of the DP above as maintaining \prod(1 + x^i + x^{2i} + \cdots + x^{Ki}), since (1 + x^i + x^{2i} + \cdots + x^{Ki}) = (1 - x^{(K+1)i})/(1-x^i), the addition and removal at both ends can be regarded as multiplying or dividing this formula.
This solution has the same time complexity as the solution above and an improved space complexity.