エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）のきろく

エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）参加!

A - Four Digits (100点)
B - Failing Grade (200点)
C - Swiss-System Tournament (300点)
D - Between Two Arrays (400点)
E - Red and Blue Tree (500点)
F - Expensive Expense (500点、実行時間制限: 4 sec)
G - 222 (600点): 未提出
H - Beautiful Binary Tree (600点、実行時間制限: 3 sec): 未提出
結果、感想

A - Four Digits (100点)

$999$ 以下なら先頭に0を追加して...という風にもできますが、やることはゼロ埋め4桁出力なので、printfやマニピュレータによるフォーマット出力で対応できます。

printf("%04d\n", N);
cout << setw(4) << setfill('0') << N << endl;

B - Failing Grade (200点)

for文を用いて各 $i$ について $a_i \lt P$ であるかを調べればいいです。

C - Swiss-System Tournament (300点)

各回毎に前の順位から今回の順位を求まられればいいです。
前回の順位で、上位からどのプレイヤーかが分かれば各試合する組み合わせが分かるので、各プレイヤーがその時点で何勝しているかが分かるので、それを勝数毎のバケツに入れて、各勝数について大きい順に、中のプレイヤーをインデックスの小さい順に取ってやれば、その試合の後の順位が上位から順に求まります。

D - Between Two Arrays (400点)

次のようなDPがまず思いつきます。

${\mathrm{dp}}_{i,j} = (\text{$c_i = j$ であるような $C$ の長さ $i$ の接頭辞(prefix)の個数})$

として、

${\mathrm{dp}}_{1,j}=\left\{ \begin{array}{ll} 1 & (a_1 \leq j \leq b_1)\\ 0 & (\mathrm{othrewise}) \end{array} \right.$

において $2 \leq i \leq N$ について

${\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} \displaystyle\sum_{k = 0}^{j} {\mathrm{dp}}_{i-1,k} & (a_i \leq j \leq b_i)\\ 0 & (\mathrm{othrewise}) \end{array} \right.$

という遷移で答えが $\displaystyle \sum_{k=0}^{\infty} {\mathrm{dp}}_{N,k}$ (範囲は $a_N \leq k \leq b_N$ で十分) と求まりますが、このままでは $M = \displaystyle\max_{1 \leq i \leq N} b_i$ として計算量が $O(NM^2)$ となってしまうので間に合いません。
ここで $\displaystyle\sum_{k = 0}^{j} {\mathrm{dp}}_{i-1,k}$ の部分について累積和を利用することで $O(NM)$ にでき、これでACをとることができます。
また、

${\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\mathrm{othrewise}) \end{array} \right.$

として遷移式を $i=1$ のときにも適応させることで場合分けや初期化を減らすこともできます。

E - Red and Blue Tree (500点)

各辺を通る回数の配列 $p = (p_1,\,p_2,\,\dots,\,p_{N-1})$ が求まれば、 $S = \displaystyle \sum_{i=1}^{N-1} p_i$ として部分和を $\displaystyle \frac{K + S}{2}$ とするような要素の選び方の数としてDPなどで求まります。

このときのDPは

${\mathrm{dp}}_{i,j} = (\text{$p$ の長さ $i$ のprefixについて部分和を $j$ とする場合の数})$

として、

${\mathrm{dp}}_{0,j}=\left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\mathrm{othrewise}) \end{array} \right.$

において $1 \leq i \leq N$ について

${\mathrm{dp}}_{i,j}=\left\{ \begin{array}{ll} {\mathrm{dp}}_{i-1,j} + {\mathrm{dp}}_{i-1,j-p_i} & (0 \leq j-p_i)\\ {\mathrm{dp}}_{i-1,j} & (\mathrm{othrewise}) \end{array} \right.$

という遷移で答えを $O(NS) = O(N^2M)$ で求めることができます。

$p$ を求めるのは、DFS等で $O(NM)$ で求めることができるので、全体として $O(N^2M)$ で答えが求まりました。

F - Expensive Expense (500点、実行時間制限: 4 sec)

制約より与えられたグラフは木であることが分かります。全方位木DPで答えは求まるそうですが、私は書けないです。ここでコンテスト終了後に直径を利用する解き方でACしました。

もともとの木に頂点 $1',\,2',\,\dots,\,N'$ と $1 \leq i \leq N$ の各 $i$ について頂点 $i$ と $i'$ を結ぶコスト $D_i$ の辺を追加します。この追加後も木の儘です。頂点 $u,\,v$ 間の距離を $\mathrm{dist}(u,\,v)$ と書きます。また、 $a=\{1,\,2,\,\dots,\,N\},$ $a'=\{1',\,2',\,\dots,\,N'\}$ とします。

ここで頂点の組 $(s,\,t)$ が直径をなす、即ち $\mathrm{dist}(s,\,t) = \displaystyle\max_{u,v \in a \cup a'} \mathrm{dist}(u,\,v)$ であるように取ります。このとき任意の頂点 $v$ について $\displaystyle \max_{u \in a \cup a'} \mathrm{dist}(u,\,v) = \max\{\mathrm{dist}(v,\,s),\,\mathrm{dist}(v,\,t)\}$ が成立します。

先ずはこれを証明します。
$\mathrm{dist}(a,\,b) \gt \max\{\mathrm{dist}(a,\,s),\,\mathrm{dist}(a,\,t)\}$ となるような頂点の組 $(a,\,b)$ が存在すると仮定します。このとき、 $a$ も $b$ も $s$ や $t$ でないことは自明です。また、 $s - t$ のパス上で $a$ から最も近い点を $c$ とすると $\mathrm{dist}(s,\,t) = \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) - 2\mathrm{dist}(a,\,c)$ となります。

$a-b$ と $s-t$ の2つのパスが交わらない場合:

$\mathrm{dist}(s,\,b) = \mathrm{dist}(s,\,a) + \mathrm{dist}(a,\,b) \gt \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) \geq \mathrm{dist}(s,\,t)$ より $\mathrm{dist}(s,\,t)$ が直径であることに反します。

$a-b$ と $s-t$ の2つのパスが交わる場合:

$s,\,t$ のうち、 $b$ に近い方が $t$ であるように仮定します(そうでない場合は $s,\,t$ を入れ替える)。このとき $\mathrm{dist}(s,\,b) = \mathrm{dist}(s,\,a) + \mathrm{dist}(a,\,b) - 2\mathrm{dist}(a,\,c) \gt \mathrm{dist}(a,\,s) + \mathrm{dist}(a,\,t) - 2\mathrm{dist}(a,\,c) = \mathrm{dist}(s,\,t)$ となりこちらでも $\mathrm{dist}(s,\,t)$ が直径であることに反します。

よってこの二つより、背理法により示したことが示されました。
ここまで来れれば、double-sweep等によって $(s,\,t)$ を求め、 $1 \leq i \leq N$ の各 $i$ について $\max\{\mathrm{dist}(s,\,i),\,\mathrm{dist}(t,\,i)\}$ を求めればよいと思ってしまいますが、最初の街では観光しないので、例えば $s = i'$ のときは $\max\{\mathrm{dist}(s,\,i),\,\mathrm{dist}(t,\,i)\}$ ではなく $\mathrm{dist}(t,\,i)$ が答えとなります。