AtCoder Beginner Contest 139
Updated:
- Review: 2020-06-02
Source codes
Solutions
A - Tenki
Just compare $S$ and $T$.
B - Power Socket
First, we have $1$ sockets. We add a power strip to gain $A - 1$ sockets. Therefore we continue to add power strip $t$ times to gain $t(A - 1) + 1$. Then, we have \[ t (A - 1) + 1 \geq B. \] The answer is $((B - 1) + (A - 1) - 1)/(A - 1)$.
C - Lower
We reverse the order of $H$. We define a $DP$ table as follows.
$DP[i] = $ the length of the increasing sequence that starts the $i$-th element to the right.
The initial state: $DP[i] = 0$ for $i = 0, \dots, H - 1$. The answer: $\max _ i DP[i]$. The transition: For $i = 1, \dots, H - 1$,
\[
DP[i] =
\begin{cases}
DP[i - 1] + 1 & H[i] \geq H[i - 1], \
0 & \text{otherwise}.
\end{cases}
\]
D - ModSum
Answer
The answer is $N(N - 1)/2$.
Reasoning
We assume $1$-indexed. We define $f \colon \mathfrak{S} _ N \to \mathbb{N}$ as follows.
\[
f(\sigma) = \sum _ {i = 1} ^ N \sigma(i) \% i.
\]
Here, we have $(\sigma(i) \text{ mod } i) \leq i - 1$. Then, for $\sigma \in \mathfrak{S} _ N$, it follows that
\[
f(\sigma) \leq \sum _ {i = 1} ^ N (i - 1) = \frac{N(N - 1)}{2}.
\]
Thus we have the upper bound of the answer as the right hand side above. In fact, this bound actually attains by the following permutation.
\[
\sigma =
\begin{pmatrix}
1 & 2 & 3 & \dots & N \
N & 1 & 2 & \dots & N - 1
\end{pmatrix}.
\]
E - League
Assume $0$-indexed.
Answer #1
We can solve this problem by a greedy algorithm as follows.
We hold the information of $A$ by vector<queue> A; Player $i$ and player $j$ can be matched if and only if $A[i].front() = j \land A[j].front() = i$. We have to spend one day to match all of these and that’s the best way. If there is no matches but there remains competition, the answer is -1.
The important thing is time complexity. If you check all players every day, the total time complexity would be $O(N^3)$, which cannot work in this problem. Consider that new matches $(i, j)$ will occur if either $i$ or $j$ would match the day before. So keeping who matched today will reduce time complexity. With this trick, the solution works in $O(N^2)$-time.
Answer #2
We convert the each matches $(i, j)$ into $\mathbb{N}$-numbered vertexes. Then, the constraints of $A$ will be the order of the vertexes. Let’s consider them into edges. Then, the problem becomes as follows. Given this graph $G$, we will flush -1 if there is a loop. If not, we will flush the maximum length of this DAG $G$. This is just calculated by topological sort and it can be solved by DFS.
To implement topological sort, we take care of the exiting time for each vertex.
int dfs(int src)
{
if (ans[src] >= 0)
{
return ans[src];
}
if (ans[src] == -2)
{
No();
}
ans[src] = -2;
int res{0};
for (auto dst : V[src])
{
ch_max(res, dfs(dst) + 1);
}
return ans[src] = res;
}
F - Engines
Answer
Assume $0$-indexed. Let $V = \{ v _ 0, v _ 1, \dots, v _ {N - 1} \} \subset \mathbb{R}^2$. The problem requires that we make $w = \sum _ { i \in {I} } v _ i$ for some $I \subset N$ to attain the maximum of the Euclid norm $\lvert \cdot \rvert$. This problem is equivalent to the following problem.
Find the pair of $I \subset N$ and $e \in \mathbb{R} ^ 2$ with $\lvert e \rvert = 1$ that attains the maximum of $(w, e)$.
This equivalence can be easily seen because for any $w \in \mathbb{R} ^ 2 \setminus \{ 0 \}$ we set $e = w/\lvert w \rvert$ to maximize $(w, e)$ and then it follows that $\lvert w \rvert = (w, e)$.
We have the following equation. \[ (w, e) = \sum _ {i \in I} (v _ i, e). \] This equation tells us how to make $I \subset N$. Fix $e \in \mathbb{R}^2$. Then, for $i \in N$, if $(v _ i, e) > 0$, we take $i$ into $I$; otherwise not.
Therefore, if $w$ attains its maximum norm, there exists $e \in \mathbb{R}^2$ with $\lvert e \rvert = 1$ so that for any $i \in I$, it follows that $(v _ i, e) > 0$ and for any $i \in N \setminus I$, it follows that $(v _ i, e) \leq 0$.
Hence, after we sort $V$ by $\arg$, we only consider some range of $V$. We can try all of them in $O(N ^ 3)$ time or $O(N ^ 2)$ time.