AtCoder Beginner Contest 152
Updated:
- Review: 2020-06-16
Source codes
Solutions
A - AC or WA
Flush Yes if $N = M$; otherwise No.
B - Comparing Strings
Just do as they indicate us to. We can use the constructor of std::string.
int main()
{
int a, b;
cin >> a >> b;
string s(b, '0' + a);
string t(a, '0' + b);
cout << min(s, t) << endl;
}
C - Low Elements
We hold int mini; as the minimum value of the passed $P _ i$’s. We reset $mini \gets \min(mini, P[i])$. If $mini = A[i]$, we execute ans++;.
D - Handstand 2
We define
$C[i][j] = $ the number of the positive numbers less than or equal to $N$ which starts by $i$ and ends by $j$.
We can compute $C$ by running on $[1, N]$. The answer is \[ \sum _ {i = 1} ^ 9 \sum _ {j = 1} ^ 9 C[i][j] C[j][i]. \]
E - Flatten
$X$ is a multiple of $A _ i$ for all $i$. Therefore $X$ is a multiple of the LCM of $A _ i$’s. Therefore the minimum is achieved when $X$ is LCM.
We can compute LCM directly by cpp_int or we can execute it by prime factorization.
F - Tree and Constraints
This is a problem solved by inclusive-exclusive principle.
Let $m _ j$ be the condition satisfying that all the edges on the pass $(u _ j, v _ j)$ are white-colored. For $i \in 2 ^ N$, let $f(i)$ be the number of the coloring which satisfies all $m _ j$ for $j \in i$. Then, we see that $f(i) = 2 ^ {N - 1 - w _ i}$, where $w _ i$ is the number of the fixed white edges determined by the conditions $m _ j$.
Then, the answer is
\[
A = \sum _ {i \in 2 ^ M} (-1) ^ {\lvert i \rvert} f(i) = \sum _ {i \in 2 ^ M} (-1) ^ {\lvert i \rvert} 2 ^ {N - 1 - w _ i}.
\]
Thus what we have to do is calculate $w _ i$ for each $i$. First we calculate the mask for $m _ j$ for each $j$ by DFS. Fix $i$. Then we merge these masks by bit operations. we can compute $w _ i$ by popcount. We also use it to calculate $(-1) ^ {\lvert i \rvert}$. To compute $2 ^ {N - 1 - w _ i}$, we just use 1 << (N - 1 - w);.
Others
Assignments:
A - sample: 3, tle: 2.000, time: 01:05, from_submit: 54:07
B - sample: 2, tle: 2.000, time: 01:22, from_submit: 52:45
C - sample: 5, tle: 2.000, time: 02:54, from_submit: 49:51
D - sample: 5, tle: 2.000, time: 04:10, from_submit: 45:41
E - sample: 3, tle: 2.000, time: 14:17, from_submit: 31:24
F - sample: 4, tle: 4.000, time: 31:25, from_submit: 00:00