# AtCoder Beginner Contest 164

Updated:

AtCoder Beginner Contest 164

# 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$.

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;
}
}
}


Tags:

Categories: