AtCoder Beginner Contest 174

Updated:

AtCoder Beginner Contest 174

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.

Others