AtCoder Beginner Contest 164
Updated:
Source codes
Solutions
A - Sheep and Wolves
Determine whether $W \geq S$ or not.
B - Battle
Solution #1
Just do simulation.
Solution #2
Let $f(a, h) = (h + a - 1) / a$ be the number of attacks we need to beat the opponent. If $f(B, C) \leq f(D, A)$, the answer is “Yes”; otherwise, “No”.
C - gacha
Just use set<string> ss;.
D - Multiple of 2019
Let $N = \lvert S \rvert$. We reverse $S$. Let $A _ i$ be the number generated by $S[0, i)$. If $(i, j)$ with $0 \leq i < j < N$ satisfies the condition, it means $2019$ can divide $A _ j - A _ i$, since $10 ^ i$ and $2019$ are coprime.
Let $C = 2019$. We hold the counts of $A _ i$s modulo $C$ by vector<ll> v(C, 0).For $i = 0, \dots, N$, we calculate $A _ i$ and execute $ans \mathbin{ {+} {=} } v[A _ i \% C]{+ +}$;.
E - Two Currencies
Assume $0$-indexed.
Observation
This is an extended Dijkstra problem.
If we have $N \max A _ i$ silver coins, we don’t have to exchange gold coins with silver coins any more. Thus we regard $(vertex, coins)$ as an extended vertex and we round up $coins \leq N \max A _ i$.
Let $C = 51$. We will make $NC \approx 2500$ vertexes and $MC \approx 5000$ edges. We can obtain answer by Dijkstra’s method.
DP part (Dijkstra)
Definition
using Info = tuple<ll, ll, ll>;(time, vertex, coins).
vector<vector<ll>>$dp[v][c] = $ the minimum time to travel from $(0, S)$ to $(v, c)$.
min_heap<Info>$h$.
Initial State
We push $h \gets (0, 0, S)$. $dp[v][c] = \infty$.
Answer
For $i = 1, \dots, N - 1$, flush $\min _ {0 \leq j < NC} dp[i][j]$.
Transition
While $h$ is not empty, we try $(t _ s, s, c _ s) \gets Q$. If $dp[s][c _ s] \neq \infty$, continue; otherwise $dp[s][c _ s] \gets t _ s$.
There are two types of transitions.
For each edge $e \in v[s]$, let $c _ d = c _ s - e.cost$. If $c _ s \geq NC$, we let $c _ s \gets NC - 1$. If $c _ s < 0$, it means we cannot travel this way; otherwise, we execute the following if $dp[e.dst][c _ s + e.cost] = \infty$. \[ Q \gets (t _ s + e.time, e.dst, c _ s - e.cost). \]
For exchange, letting $c _ n = \min(NC - 1, c _ s + C[s])$, we also execute the following if $dp[s][c _ n] = \infty$. \[ Q \gets (t _ s + D[s], s, c _ n). \]
F - I hate Matrix Construction
Solution
This is a bitwise problem. Thus we separate this problem into $64$ problems with $0$ and $1$.
Then, each constraints becomes either of the followings: AllZero, AllOne, AnyZero, AnyOne.
We initialize the resulting matrix by $0$.
First, we put $1$ on AllOne rows. Same for the columns.
After finishing this, we also check AllOne constrains and AllZero constrains. We confirm that they don’t break each other.
Second, we check AnyOne rows. We think of $i$-th row. If its row already has $1$, we don’t have to change anything. Otherwise, it means each columns has either AllZero or AnyZero constraints. We can change $(i, j)$ if $j$-th column is AnyZero and it has more than or equal to $2$ zeros. If we cannot find such $j$, the answer is -1.
We do the same thing for the columns. After finishing this, we also check AnyOne constrains and AnyZero constrains.
The total time complexity is $O(C N ^ 3)$, where $C = 64$.
Implement
This is a difficult problem from the viewpoint of implementation.
Initialize by $0$.
If our algorithm is good, we don’t have to use $-1$ for the dummy. If we initialize the resulting matrix by $0$, we obtain short-cut.
Use enum class to manege the constraints
We define enum class State as follows.
enum class State
{
AllZero,
AllOne,
AnyZero,
AnyOne
};
We convert $s$ and $u$ into vector<State> xAxis as follows.
if (!s[i] && !u[i])
{
ans[i] = State::AnyZero;
}
else if (!s[i] && u[i])
{
ans[i] = State::AllOne;
}
else if (s[i] && !u[i])
{
ans[i] = State::AllZero;
}
else
{
ans[i] = State::AnyOne;
}
Then, the implementation becomes cleaner after this.
Transpose the resulting matrix
Not to copy and paste the same codes for $x$-axis and $y$-axis, we transpose the matrix and swap xAxis and yAxis.
template <typename T>
void Transpose(vector<vector<T>> &mat)
{
int n = mat.size();
for (auto i{0}; i < n; ++i)
{
for (auto j{i + 1}; j < n; ++j)
{
swap(mat[i][j], mat[j][i]);
}
}
}
class Solve
{
int n;
vector<State> xAxis, yAxis;
vector<vector<bool>> res;
public:
// constructors
private:
void ChangeAxis()
{
Transpose(res);
swap(xAxis, yAxis);
}
}
Use any_of and all_of for checker functions
If we use for-loop and if-breaks, the code becomes fat. We use std::any_of and std::all_of as follows.
bool CheckAll(int i, bool b)
{
return all_of(res[i].begin(), res[i].end(), [&b](auto v) { return v == b; });
}
Checker functions becomes cleaner.
void CheckAll()
{
for (auto i{0}; i < n; ++i)
{
switch (xAxis[i])
{
case State::AllOne:
if (!CheckAll(i, 1))
{
No();
}
break;
case State::AllZero:
if (!CheckAll(i, 0))
{
No();
}
break;
default:
continue;
}
}
}