gyouzasushi’s diary

競プロとか

今日の競プロ(2020/4/15) + Codeforces Round #635 (Div. 2)

Codeforces 10問
JOI 2問

Codeforces Round #624 (Div. 3) A - Add Odd or Subtract Even

バチャ。

Codeforces Round #624 (Div. 3) B - WeirdSort

Codeforces Round #624 (Div. 3) C - Perform the Combo

Codeforces Round #624 (Div. 3) D - Three Integers

3つについて考えるときに真ん中を固定すると見通しがよくなるやつ！この問題では $B$ を固定。そうすると $A$ の候補は $B$ の約数だけ、 $C$ の候補は $C$ 以上最小の $B$ の倍数か $C$ 以下最大の $B$ の倍数だけになる。 $B$ を $2000$ くらいまで調べて $\min$ をとる。

Codeforces Round #624 (Div. 3) F - Moving Points

Eより解かれていたのでFからやった。 $x_i \lt x_j$ とすると
$d(i,j) = \begin{cases} {x_j-x_i} & (v_i \leq v_j) \\ 0 & (v_i \gt v_j) \end{cases}$
なので、 $v$ が小さい順に見ていって $x$ の差を足していく。

Codeforces Round #624 (Div. 3) E - Construct the Binary Tree

バチャ中には解けず。
まず深さの和が最小のグラフをつくる（完全二分木の作りかけみたいなやつ）。そこから

葉をひとつえらぶ

えらんだ葉を、子が一つ以下かつ同じ深さの頂点にくっつける

という操作を繰り返す。一回の操作で深さの和はちょうど $1$ 増えるから、 $d$ になるまでこれを続けたらいける。

JOI2008春合宿 Day1 committee - 委員会 (Committee)

「 $dp[i]=i$ を根とするの部分木で、 $i$ を必ず選んだときのやる気の合計の最大値」をする。

JOI2008春合宿 Day1 sheet - 色紙 (Sheet)

あらかじめ各色紙の四隅の座標（の候補のうち一番内側）を求めておく。

Codeforces Round #635 (Div. 2) A - Ichihime and Triangle

$b,c,c$ 。

Codeforces Round #635 (Div. 2) B - Kana and Dragon Quest game

シミュレーション。

Codeforces Round #635 (Div. 2) C - Linova and Kingdom

ある頂点を工業都市にしたとき happiness の総和は（深さ）-（子孫の数）だけ増えるので、この値が大きい方から $k$ 都市を選べばいい。

Codeforces Round #635 (Div. 2) D - Xenia and Colorful Gems

$r,g,b$ の値が近いセットをいくつか調べたら通った。もしかしたら嘘解法かも…。