# AtCoder Grand Contest 034

Updated:

AtCoder Grand Contest 034

# Solutions

## A - Kenken Race

### 解答

$A < B < C < D$ と $A < C < B < D$ と $A < B < D < C$ が考えられる。 $B \to D$ の方から考慮すれば、最初の $2$ つは独立に考えることができる。

$A < B < D < C$ の場合は、すぬけ君はふぬけ君を飛び越せるようにする必要がある。この条件は $B \leq x \leq D$ が存在し $S[x - 1], S[x], S[x + 1]$ が空白であることと同値である。

### ポイント

$[B, D]$ を $(B, D)$ として 3WA を食らった。

## B - ABC

### 解答

“ABC” を “BCA” に変えるということは、 “A” が “BC” を飛び越えるということである。よって BC 列を持っておき、どれだけの BC を A が飛び越えるか見ていけばよろしい。

### ポイント

これは気づけばわかった。ただ間違った解法をやってしまった。

## C - Tests

### 解答

$K = A - B$ とする。仮に高橋くんの点数 $a _ i$ がわかっていれば、係数 $c _ i$ の決め方は自明である。

• $a _ i \geq b _i$ ならば $c _ i = u _ i$ とするべきであり、 $K$ への寄与は $u _ i(a _ i - b _ i)$ である。
• $a _ i \leq b _i$ ならば $c _ i = l _ i$ とするべきであり、 $K$ への寄与は $l _ i(a _ i - b _ i)$ である。

これは $x = a _ i$ について下に凸の折れ線グラフになる。ここで勉強時間 $T$ を二分探索することにし、 $K$ の最大値を求めることを考える。すると $x$ 座標の与え方は、 $X, X, \dots, X, T \% X, 0, \dots, 0$ ということになる。最初の $X$ の個数に応じて前処理 $O(N)$ をしておくと各回 $O(1)$ で出力できる。 $T \% X$ に関する寄与については全探索するとよろしい。計算量は $O(N \log NX)$ である。

### 実装

めぐる式二分探索をすればよろしい。

  ll ok = N * X + 1;
ll ng = -1;
while (abs(ok - ng) > 1)
{
ll t = (ok + ng) / 2;
if (solve(t))
{
ok = t;
}
else
{
ng = t;
}
}
cout << ok << endl;


$sum[i] = [0, i)$ 番目に $t = lb + u(X - b)$ の大きいものから順に取ってきた和から、全ての $-lb$ を引いたもの、
$V[i] =$ テストを $t = lb + u(X - b)$ の大きい順に並べたもの。

また、以下の通りに $f _ i$ を定義する。

$f _ i (x) = \begin{cases} l _ i x & x \leq b _ i, \\ l _ i b _ i + r _ i (x - b _ i) & x \geq b _ i \end{cases}$

• $x _ 0 = 0$ のとき、最大値は $sum[cnt]$ である。
• $x _ 0 > 0$ のとき、 $i = 0, \dots, N - 1$ の $f _ i$ について $x _ 0$ での値を求めるものとする。すると求める最大値は、以下の最大値である。
• $i < cnt$ のとき、 $sum[cnt + 1] - t _ i + f _ i (x)$
• $i \geq cnt$ のとき、 $sum[cnt] + f _ i (x)$

## D - Manhattan Max Matching

### 解答

まず以下の式に注意する。 $k, l \in \mathbb{R}$ に対し、 $\lvert k - l \rvert = \max(k - l, l - k).$ すると $(x, y)$ と $(X, Y)$ のマンハッタン距離は、次式で表示される。 \lvert x - X \rvert + \lvert y - Y \rvert = \max \left\{ \begin{aligned} (x + y) - (X + Y), \\ (- x + y) - (- X + Y), \\ (x - y) - (X - Y), \\ (- x - y) - (- X - Y). \end{aligned} \right.

したがって、最小費用流を使うとこの問題は解ける。

#### 頂点

それぞれ「同じ形のもの」が「同数」あることに注意して、中間地点を設ける。

• $2000$: 始点である。
• $i = 0, \dots, N - 1$ に対し $i$: 赤いボールである。
• $2001, 2002, 2003, 2004$: 上の $4$ パターンを吸収するための中間地点。
• $i = 0, \dots, N - 1$ に対し $1000 + i$: 青いボールである。
• $2005$: 終点である。

#### 辺

$C = 10^{12} + 10$ とする。コストは何も書かなければ $0$ とする。

• $i = 0, \dots, N - 1$ に対し、容量 $RC _ i$ の辺 $2000 \to i$ を張る。
• $i = 0, \dots, N - 1$ に対し、容量 $RC _ i$ 、
• コスト $C - (RX _ i + RY _ i)$ の辺 $i \to 2001$ を張る。
• コスト $C - (- RX _ i + RY _ i)$ の辺 $i \to 2002$ を張る。
• コスト $C - (RX _ i - RY _ i)$ の辺 $i \to 2003$ を張る。
• コスト $C - (- RX _ i - RY _ i)$ の辺 $i \to 2004$ を張る。
• $i = 0, \dots, N - 1$ に対し、容量 $BC _ i$ 、
• コスト $C + (BX _ i + BY _ i)$ の辺 $2001 \to 1000 + i$ を張る。
• コスト $C + (- BX _ i + BY _ i)$ の辺 $2002 \to 1000 + i$ を張る。
• コスト $C + (BX _ i - BY _ i)$ の辺 $2003 \to 1000 + i$ を張る。
• コスト $C + (- BX _ i - BY _ i)$ の辺 $2004 \to 1000 + i$ を張る。
• $i = 0, \dots, N - 1$ に対し、容量 $BC _ i$ の辺 $1000 + i \to 2005$ を張る。

## E - Complete Compress

Assume $0$-indexed. Hereinafter we fix the root of the tree. We try all the possibilities and calculate the answer in $O(N)$-time. Thus the entire time complexity will be $O(N ^ 2)$.

Our goal is to determine whether we can reduce the sum of the depth to $0$.

### Observation

There are two types of the manipulations. It reduces the sum of the depth by $2$ or not.

First we prove the next lemma.

Lemma E.1: If we can achieve our goal, the manipulations that does not reduce the sum of the depth will not be needed.

Proof. We promise that we call a manipulation meaningless if it does not reduce the sum of the depth. Suppose that we can achieve the goal, and have a meaningless manipulation $u = (A, B)$, where $A$ is deepened and $B$ is upped. Note that $A$ is on an ancestor of $B$. Without loss of generalities, we can assume that there is no meaningless manipulation after $u$. Since we can achieve our goal, there must be at least one manipulation including $A$ after $u$. We use $v = (A, C)$ to denote it. We separate the cases into two.

• The depth of $B$ is smaller than or equal to that of $A$ when we execute $v$: We have executed $u$, but we should have skipped it. Then, we execute $v’ = (B, C)$ instead of $v$ to have the same situation.
• The depth of $B$ is bigger than that of $A$ when we execute $v$: There is at least one situation $B$ is on the parent of $A$. If we have skipped $u$, the result would be tha $A$ is on the parent of $B$. These two situation is regarded as the same since we don’t have to distinguish the pieces to determine whether we can achieve the goal.

Corollary E.2: If we can achieve the goal, the minimum number of the manipulations is $r / 2$, where $r$ is the sum of the depth.

It is easy to see the next lemma. It is hard to come up with this, though.

Lemma E.3: In addition to the assumptions of Lemma E.1, we can assume that all manipulations included in a subtree be executed before its parent-tree’s manipulations.

Proof. Just changing the order is suffice.

### Solution

Lemma E.4 assures us that we can consider DFS. We calculate $c$, $l$ and $r$ for each vertex, where $c$ is the number of the pieces on the subtree and $[l, r]$ are the range of the sum of the depth. We can gather all pieces on the root if the root’s $l$ is $0$.

Let $\{ (c _ i , l _ i, r _ i) \}$ be the set of the children’s triples. First we add up the $l _ i \mathbin{ {+} {=} } c _ i$ and $r _ i \mathbin{ {+} {=} } c _ i$ to consider the effect on $l$. Then let $c = \sum _ i c _ i + \delta$ where $\delta = 1$ when a piece is already put on its vertex and $r = \sum _ i r _ i$. Then, what is $l$?

Each subtree has its depth on the range $l _ i, l _ i + 2, \dots, r _ i$. For each manipulation, we choose two subtrees and we reduces the depth of both. We want to minimize the sum of the depth. Note that the possible minimum is $M = (\sum _ i l _ i) \% 2$.

If there exists $l _ j$ that satisfies $l _ j > \sum _ {i \neq j} l _ i$, the best strategy is to beat $l _ j$ by the others. Note that this $j$ is unique if exists. If $l _ j > \sum _ {i \neq j} r _ i$, the answer is $l _ j - \sum _ {i \neq j} r _ i$. Otherwise the answer is $M$.

If not, we can achieve the minimum $M$ by letting the first and the second largest vertexes fight with others for each manipulation. (This needs a proof, but it is almost obvious without proof. So I omit the proof.)

## F - RNG and XOR

### Observation

#### Recursive presentation

Let $x _ i$ be the expected value of the count to gain $i$ starting from $0$. Let $p _ i = A _ i / S$. Then, we see that $x _ 0 = 0$ and $x _ i = \sum _ {j = 0} ^ {2 ^ N - 1} p _ j x _ {i \oplus j} + 1,$ which is equivalent to $\sum _ {j = 0} ^{2 ^ N - 1} x _ j p _ {i \oplus j} = x _ i - 1. \tag{F.1}$ for all $1 \leq i \leq 2 ^ N - 1$.

To solve (F.1), we usually use a matrix in $O(B^3)$-time. But it will be TLE. Thus we use XOR sum to come up with a good idea.

#### XOR sum

Definition F.1 (XOR sum): Let $R$ be a ring. Let $N \in \mathbb{N}$. We define XOR sum $\bigoplus \colon R ^ {2 ^ N} \times R ^ {2 ^ N} \to R ^ {2 ^ N}$ as follows. $(c _ 0, \dots, c _ {2 ^ N - 1}) = (a _ 0, \dots, a _ {2 ^ N - 1}) \bigoplus (b _ 0, \dots, b _ {2 ^ N - 1}), \tag{F.2}$ where $c _ i = \sum _ {j = 0} ^ {2 ^ N - 1} a _ j b _ {i \oplus j}.$

In this problem, we use the following lemma.

Lemma F.2: Suppose (F.2). Then, we have the followings.

1. $\sum _ {i = 0} ^ {2 ^ N - 1} c _ i = \left( \sum _ {i = 0} ^ {2 ^ N - 1} a _ i \right) \left( \sum _ {i = 0} ^ {2 ^ N - 1} b _ i \right).$
2. $(a _ 0, \dots, a _ {2 ^ N - 1}) \bigoplus (b _ 0 - 1, \dots, b _ {2 ^ N - 1}) = (c _ 0 - a _ 0, \dots, c _ {2 ^ N - 1} - a _ {2 ^ N - 1}).$
3. \begin{align} (a _ 0 + a _ 1, \dots, a _ {2 ^ N - 2} + a _ {2 ^ N - 1}) \bigoplus (b _ 0 + b _ 1, \dots, b _ {2 ^ N - 2} + b _ {2 ^ N - 1}) &= (c _ 0 + c _ 1, \dots, c _ {2 ^ N - 2} + c _ {2 ^ N - 1}), \\ (a _ 0 - a _ 1, \dots, a _ {2 ^ N - 2} - a _ {2 ^ N - 1}) \bigoplus (b _ 0 - b _ 1, \dots, b _ {2 ^ N - 2} - b _ {2 ^ N - 1}) &= (c _ 0 - c _ 1, \dots, c _ {2 ^ N - 2} - c _ {2 ^ N - 1}) \end{align}

Proof. 1. and 2. are straightforward. To see the first line of 3., Let $a _ i ‘ = a _ {2i} + a _ {2i + 1}$ and $b _ i ‘ = b _ {2i} + b _ {2i + 1}$ and $c _ i’ = \sum _ {j = 0} ^ {2 ^ {N - 1} - 1} a _ i’ b _ {i \oplus j}’ = \sum _ {j = 0} ^ {2 ^ {N - 1} - 1} \left( a _ {2i} + a _ {2i + 1} \right) \left( b _ {2(i \oplus j)} + b _ {2(i \oplus j) + 1} \right).$ Note that \begin{align} c _ {2i} &= \sum _ {j = 0} ^ {2 ^ N - 1} a _ j b _ {2i \oplus j}, \\ c _ {2i + 1} &= \sum _ {j = 0} ^ {2 ^ N - 1} a _ j b _ {(2i + 1) \oplus j}. \end{align} We see that \begin{align} 2(i \oplus j) &= 2i \oplus 2j = (2i + 1) \oplus (2j + 1), \\ 2(i \oplus j) + 1 &= (2i + 1) \oplus 2j = (2i + 1) \oplus 2j. \end{align} Thus we have the first line. The second line is seen by almost the same way.

#### Convert (F.1) into XOR sum

(F.1) is presented as the following equation. $(x _ 0, \dots, x _ {2 ^ N - 1}) \bigoplus (p _ 0, \dots, p _ {2 ^ N - 1}) = (X, x _ 1 - 1, \dots, x _ {2 ^ N - 1} - 1),$ where $X$ is unknown yet. To determine $X$, we apply Lemma F.2.1 for it. Since $\sum _ {i = 0} ^ {2 ^ N - 1} p _ i = 1$ We have $X + \sum _ {i = 1} ^ {2 ^ N - 1} x _ i - (2 ^ N - 1) = \sum _ {i = 0} ^ {2 ^ N - 1} x _ i.$ Thus we have $X = x _ 0 + 2 ^ N - 1$. Then, by Lemma F.2.2, it follows that $(x _ 0, \dots, x _ {2 ^ N - 1}) \bigoplus (p _ 0 - 1, p _ 1, \dots, p _ {2 ^ N - 1}) = (2 ^ N - 1, - 1, \dots, - 1). \tag{F.3}$

### Solution

We describe the algorithm in the case $N = 2$, though general cases are the same. To solve $(x _ 0, x _ 1, x _ 2, x _ 3) \bigoplus (p _ 0 - 1, p _ 1, p _ 2, p _ 3) = (3, -1, -1, -1),$ we apply Lemma F.2.3 for it. Then, we have \begin{align} (x _ 0 + x _ 1, x _ 2 + x _ 3) \bigoplus (p _ 0 - 1 + p _ 1, p _ 2 + p _ 3) = (2, -2), \\ (x _ 0 - x _ 1, x _ 2 - x _ 3) \bigoplus (p _ 0 - 1 - p _ 1, p _ 2 - p _ 3) = (4, 0). \end{align} Again apply Lemma F.2.3 for them to have \begin{align} (x _ 0 + x _ 1 + x _ 2 + x _ 3) \bigoplus (p _ 0 - 1 + p _ 1 + p _ 2 + p _ 3) = (0), \\ (x _ 0 + x _ 1 - x _ 2 - x _ 3) \bigoplus (p _ 0 - 1 + p _ 1 - p _ 2 - p _ 3) = (4), \\ (x _ 0 - x _ 1 + x _ 2 - x _ 3) \bigoplus (p _ 0 - 1 - p _ 1 + p _ 2 - p _ 3) = (4), \\ (x _ 0 - x _ 1 - x _ 2 + x _ 3) \bigoplus (p _ 0 - 1 - p _ 1 - p _ 2 + p _ 3) = (4). \end{align} These equations are just the form $XP = N$ in $\mathbb{Z}/998244353 \mathbb{Z}$, so we can solve $X$ immediately except the first equation. The first equation means $(x _ 0 + x _ 1 + x _ 2 + x _ 3) 0 = 0$. It does not provide any information.

Fortunately, this exception occurs only on the first equation since $0 < p _ i < 1$ with $\sum p _ i = 1$. Therefore we can assume $\sum x _ i = 0$ temporarily. Then, we calculate the solution $(x _ 0, \dots, x _ {2 ^ N - 1})$. Here we know that $x _ 0 = 0$. Let $C$ be the initial $x _ 0$. We subtract all $x _ i$ by $C$ to have the correct value of $x _ i$.

### Time complexity

The total time complexity is $O(NB) = O(N 2 ^ N)$. The time limit is enough: $3$ seconds. We can use vector<vector<vector<mint>>> a(N + 1), b(N + 1), c(N + 1);

Tags:

Categories: