AtCoder Beginner Contest 174
Updated:
Source codes
Solutions
A - Air Conditioner
Flush whether $X \geq 30$ or not.
B - Distance
Count the number of such points $(x, y)$ that $x ^ 2 + y ^ 2 \leq d ^ 2$.
C - Repsept
Let $a _ n = 7 (10 ^ n - 1) / 9$.
Solution
Try $a _ n$ for $n = 1, \dots, 2 \times 10 ^ 7$.
Verification
Let $L = 9K$. If $L$ divides $10 ^ n - 1$, then $K$ divides $a _ n$. We see that, if $K = 2$ or $5$, the answer is -1. Hereinafter, we assume that $L$ and $10$ are coprime. Then, by well-known argument, it follows that $\{ 10 ^ n \in \mathbb{Z} / L \mathbb{Z} \mid 1 \leq n \leq L \} = \mathbb{Z} / L \mathbb{Z}$. Apply brute-force method for it.
D - Alter Altar
Assume $1$-indexed.
Solution
The final state will be $RRR \dots RWWW \dots W$. Let $0 \leq k \leq N$ be the index of the last $R$. We fix $k$. Then, the minimum cost is the maximum number of the followings.
- The number of whites in the red area.
- The number of reds in the white area.
This is calculated by cumulated sum in $O(1)$-time for each $k$. The total time complexity is $O(N + N \cdot 1) = O(N)$.
E - Logs
Solution
This is done by binary search for the targeted answer.
We consider how many times we have to cut the logs to have an situation where all of them are the length of less than $X$. This is calculated by the following. \[ f(X) = \sum _ {i \in N} \left( \frac{A _ i + (X - 1)}{X} - 1 \right). \] We determine $f(X) \leq K$ or not.
F - Range Set Query
Assume $0$-indexed.
Solution
We sort the queries in $r$’s ascending order and we consider $r = 0, 1, \dots, N - 1$. Then, we just keep the rightmost balls for each color and just count up for those balls for $[l, r]$.
We use $memo[color]$ to denote the index of the rightmost ball of the color $color$ so far. We define $tree[index] = 1$ if the ball of $index$ is of the balls we are now considering or $0$ if not. We maintain $tree$ with updates of $memo$ and take the sum in $tree$ for the range of $[l, r]$ for each query. Thus, we use $tree$ for segment tree or binary indexed tree.