AtCoder Grand Contest 018
Updated:
Source codes
Solutions
A - Getting Difference
$\mathrm{gcd}(a_1, \dots, a_N) | K$ かつ $\mathrm{max}(a_1, \dots, a_N) \geq K$ が必要十分条件．
B - Sports Festival
まず全部の競技を開催する．一番参加者が多い競技を取りやめる．その繰り返し．今の状態より小さい答えがあるとするならば，今ボトルネックとなっている最大の参加者を擁する競技は取りやめるしかない．削除を決めた時点で，既に最小値を達成しているか，今後最小値を達成するならばその競技は使わない．
最小値がもとまる理由
競技を，削除する順番に $A_0, \dots, A_{N-1}$ とする． $A_i$ を削除する際に $a_i$ 人の参加者がいたとする． この時点で，以下の事実が従う．
- 参加者の最大値が $M = \min \{ a_i \mid 0 \leq i < N \}$ 人であるような開催競技の集合が存在する．
$S$ を任意の開催する競技の集合とする．$j = \min \{ 0 \leq i < N \mid A_i \in S \}$ とする．先に削除された競技をもう一度復活させても，取りやめる前の参加者は必ず参加するので，参加者数が小さくなることはありえない．したがって， $S$ を開催した際に参加者の最大値は，$a_j \geq M$ 人以上である．すなわち，以下が従う．
- 任意の開催競技の集合 $S$ に対し，参加者の最大値は $M$ 人以上である．
以上より，答えは $M$ 人である．
ポイント
DP のように見えて，貪欲法だった．
間違えたところ：すでに取りやめている競技は set または配列で記録して おき ， queue の中から while 文で削除 する．メモとして queue を使うなら pop は根こそぎやる．
C - Coins
最大値を求めるならば，シフトすることにより $C_i = 0$ として良い． また，入力を $A_i - B_i$ の昇順にソートしておく． このとき，ある $K$ があって， $i < K$ のとき 銀 or 銅， $i \geq K$ のとき 金 or 銅を選ぶことになる．
区切り位置 $K$ が決まっているならば， $i < K$ のとき $Y$ 個の $B_i$ とその他は $0$ を選ぶので， $B_i$ を大きい方から順に選べばよろしい． $i \geq K$ も下からやれば同様である．
今回は区切り位置を全て試すことはできないが， priority_queue を使えば問題ない． priority_queue に push していき，和を管理， $Y$ 個を超えたら一番小さい top を引いてから pop する．これで $K$ ごとに最大値がもとまる．
実装
前から，後ろから総和を取るので，植木算的ミスが出る．
for 文は無理せず普通のやつで回す．普通のやつで回すことで，配列外参照をせずに済む．
priority_queue の size に毎回アクセスして pop すると事故がない．
ll sum = 0;
priority_queue<ll, vector<ll>, greater<ll> > Q;
for (auto i = 0; i < N; ++i) {
sum += B[i];
Q.push(B[i]);
while ((ll)Q.size() > Y) {
sum -= Q.top();
Q.pop();
}
silver[i] = sum;
}
あとで $\pm 1$ を調整するようにした方が，事故が少ないように思う． 今回は以下の通り．
for (auto i = Y-1; i <= Y+Z-1; ++i) {
maxi = max(maxi, gold[i+1]+silver[i]);
}
D - Tree and Hamilton Path
木の重心の知識がないと解答に至らないので，まず定義とその周辺を述べる．
重心の基礎知識
定義： $T = (V, E)$ をサイズ $n$ の木とする． $v \in V$ が $T$ の 重心 であるとは， $T$ から $v$ を除いた全ての部分木のサイズが $n/2$ 以下であることをいう．
初等的性質： $T$ には重心が $1$ つまたは $2$ つ存在する． 後者の場合， $n$ は偶数であり，サイズ $n/2$ の部分木が辺で繋がっている構造になっている．
記号
$a_0, \dots, a_{N-1}$ を，頂点 $0, \dots, N-1$ の順列とする． これで訪れるルートを表すものとする． $T$ は $a_0$ を根とする． $f(a_i)$ で $a_0$ と $a_i$ の距離を表す．つまり深さである．
$\mathrm{lca}(a_i, a_j)$ を $a_i, a_j$ の最小共通祖先とする． この問題では最小共通祖先を効率的に求める必要は実はない．
本編
最適解が最適であるための証明はめんどい．コンテスト中に重要なのは最適解を思いつくことであり，その正確な証明ではない．解説は editorial がわかりやすい．結論を言うと，以下の通り．
- 重心が $2$ 個の場合， $a_0$ と $a_{N-1}$ を重心とする．
- 重心が $1$ 個の場合， $a_0$ を重心とし， $a_{N-1}$ を重心から直接辺が出ている頂点のうち最も距離が近いものとする．
こうすると，最長が実現できる． $a_0$ と $a_{N-1}$ の間の辺だけ上限だけ通れないが残りは上限まで通っている．それ以外の辺を削ろうとすると，終点が重心でないゆえに，この辺を含めてもっと損をする(と想像できる)．
具体的に答えの数値はどうなるか．$a_i, a_{i+1}$の距離は，
\[ f(a_i) + f(a_{i+1}) - 2 f(\mathrm{lca}(a_i, a_{i+1})) \]
であるから，パスの長さは
\[
\begin{align}
L & = \sum_{i=0}^{N-2} \left(
f(a_i) + f(a_{i+1}) - 2 f(\mathrm{lca}(a_i, a_{i+1}))
\right) \
& =
2 \sum_{i = 0}^{N-1} f(a_i) - f(a_0) - f(a_{N-1})
- 2 \sum_{i=0}^{N-2} f(\mathrm{lca}(a_i, a_{i+1}))
\end{align}
\]
である． $f(a_0) = 0$ であり，解説にある通り全ての $0 \leq i < N-1$ に対し $\mathrm{lca}(a_i, a_{i+1}) = a_0$ である．したがって答えは
\[
L = 2 \sum_{i = 0}^{N-1} f(a_i) - f(a_{N-1})
\]
と求まる．
ポイント
入力の辺は for 文で受け取るが， 木の辺の数は $N-1$ 本 だからうっかり $N$ にしないように．私は cin で受け取るので，最後が 0 になってしまう恐ろしいことに．
重心の知識がないとなんともしようがない．仮にひねり出したとしても，場合分けに気づかないまま終わるだろう．重心の求め方は，とりあえず適当にとった根で dfs をし，上の定義をチェックし，サイズが $n/2$ より大きい部分木が見つかったらそっちに移って行くのを繰り返すと $O(N)$ で見つかる．
E - Sightseeing Plan
解法はわかったが，これも植木算的ミスが出そうなので，あとで書く．
F - Two Trees
疲れたのであとでやる．
ポイント
前者の解答はすごすぎる．後者の解答が現実的だが， 1700 点で出題されてこれを時間内に考察するのは無理があるように思う．私のような凡人には，どちらも観賞用である．
Others
気づけば全て DP でないというセットだった．
小さいサイズに分割できない時は貪欲法，具体的構成ということでした．