# AtCoder Beginner Contest 152

Updated:

AtCoder Beginner Contest 152

• Review: 2020-06-16

# 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


Tags:

Categories: