AtCoder Grand Contest 034
Updated:
Source codes
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;
問題は $cnt = T / X$, $x _ 0 = T \% X$ の処理である。これは $3$ パターンに分かれる。以下を定義する。
$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)$
ポイント
二分探索がポイント である。よく考えて見れば勉強時間 $\nearrow$ なら点数 $\nearrow$ である基準を超えるまでの最小の勉強時間を問うているのだからそりゃ二分探索だわ。
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$ を張る。
容量 $S$ を流すときの最小費用を $K$ とすると、答えは $2SC - K$ である。
ポイント
全く見なかった問題だが、最小費用流の問題は美しい問題が多いなぁ。
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.
- \[ \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). \]
- \[ (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}). \]
- \[ \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);