gyouzasushi’s diary

競プロとか

今日の競プロ(2020/5/1) + Codeforces Round #638 (Div. 2)

Codeforces : 2014 → 2081 (+67)

Codeforces Round #570 (Div. 3) F - Topforces Strikes Back

三つのうち最大を決め打つと貪欲でいける。

$a_i$ の約数の個数は $a_i$ に比べてはるかに小さい
$a_i$ より小さい $a_i$ の約数は全部 $\frac{a_i}{2}$ 以下

がポイント。

JOI2014春合宿 M - ストラップ

端子の数でソートして、「 $dp[i][j]=i$ 個目までみて、端子の数が $j$ となるつけ方の嬉しさの最大値」。

yukicoder No.1040 垂直大学

yukicoder No.1041 直線大学

yukicoder No.1042 愚直大学

Desmosを睨んだら $N \geq 1$ で単調性がありそうに見えたので、信じて二分探索した。

yukicoder No.1043 直列大学

乾電池と豆電球それぞれについてナップザックDPしたあと、条件を満たす組み合わせを数え上げる。割り算が苦手すぎて一時間半くらいかけてもうた…。

Codeforces Round #638 (Div. 2) A - Phoenix and Balance

実験した。 $2^{\frac{n}{2}+1}-2$ 。

Codeforces Round #638 (Div. 2) B - Phoenix and Beauty

数列 $a$ を $k$ の周期をもつ数列にすることができれば十分。

Codeforces Round #638 (Div. 2) C - Phoenix and Distribution

$s$ はソートしておく。

$s_1 \neq s_k$ のとき

$s_1+s_{k+1}+s_{k+2}+\ldots+s_n, s_2, s_3,\ldots,s_k$ みたいにするのが最適で、答えは $s_k$ 。

$s_1 = s_k$ かつ $s_{k+1} \neq s_n$ のとき

このときも $s_1+s_{k+1}+s_{k+2}+\ldots+s_n, s_2, s_3,\ldots,s_k$ みたいにするのが最適。ただし答えは $s_1+s_{k+1}+s_{k+2}+\ldots+s_n$ 。

$s_1 = s_k$ かつ $s_{k+1}=s_n$ のとき

$s_{k+1}$ から $s_n$ までをできるだけ均等に使うのが最適。答えは $s_1+s_{k+1}*\lceil \frac{n-k}{k} \rceil$ 。

Codeforces Round #638 (Div. 2) D - Phoenix and Science

$1$ 個、 $2$ 個、 $4$ 個、 $8$ 個… みたいに殖えるのが最速。あまりは適当に調整できて、例えば $n=18$ なら $1,2,3,4,8$ 、 $n=25$ なら $1,2,4,8,10$ みたいな。