AtCoder Grand Contest 034
更新日時:
寝る時間があるので D までとします。
ソースコード
解法のメモ
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$ である。
ポイント
全く見なかった問題だが、最小費用流の問題は美しい問題が多いなぁ。