# AtCoder Beginner Contest 158

Updated:

AtCoder Beginner Contest 158

# Solutions

## A - Station and Bus

If the string is “AAA” or “BBB”, the answer is No. Otherwise, Yes.

## B - Count Balls

Let $C = A + B$. The answer is given by $A \cdot (N / C) + \min(N \% C, A).$

## C - Tax Increase

Try all possibility. Roughly, it is suffice to try $N \leq 10000$.

## D - String Formation

We cannot reverse the string for each step. It will result in $O(Q (\lvert S \lvert + Q))$-time. Instead of reversing the string itself, we possess the direction of the string in the viewpoint of the original string. Let bool reversed; to be this direction.

Let stringstream prefix; be the reversed prefix and stringstream suffix; be the suffix. We add $C _ i$s into these stringstream. Let $A$ be the non-reversed prefix + $S$ + the suffix. If reversed, the answer is the reversed $A$. Otherwise, $A$ itself.

## E - Divisible Substring

Let $X _ i = S[N - i, N)$ for $1 \leq i \leq N$ and $X _ 0 = 1$. We have to count $(i, j)$ so that $0 \leq i < j \leq N$ and $\frac{X _ j - X _ i}{10 ^ i} = 0 \text{ in } \mathbb{Z} / P \mathbb{Z}. \tag{E.1}$

If $P = 2$ or $5$, this problem is easily solved since whether a number can be divided by $P$ or not depends only on the last digit.

If $P \neq 2, 5$, (E.1) is equivalent to $X _ j = X _ i$ in $\mathbb{Z}/P\mathbb{Z}$. Thus we just possess the table between the remainder and its count.

# Others

A - sample: 3, tle: 2.000, time: 01:18, from_submit: 98:01
B - sample: 3, tle: 2.000, time: 01:37, from_submit: 96:24
C - sample: 3, tle: 2.000, time: 02:35, from_submit: 93:49
D - sample: 3, tle: 2.000, time: 11:49, from_submit: 82:00
E - sample: 3, tle: 2.000, time: 43:00, from_submit: 39:00
F - sample: 4, tle: 2.000, time: 39:00, from_submit: 00:00


Tags:

Categories: