$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);

Kazune Takahashi

AtCoder Grand Contest 034

Source codes

Solutions

A - Kenken Race

解答

ポイント

B - ABC

解答

ポイント

C - Tests

解答

実装

ポイント

D - Manhattan Max Matching

解答

頂点

辺

ポイント

E - Complete Compress

Observation

Solution

F - RNG and XOR

Observation

Recursive presentation

XOR sum

Convert (F.1) into XOR sum

Solution

Time complexity

Others

You May Also Enjoy

好きな言葉について

日記

学生時代にやらずに後悔していること

未練なき人生の地点で