AtCoder Beginner Contest 240のきろく - Flkanjin’s 競プロ録

A - Edge Checker (100点)
B - Count Distinct Integers (200点)
C - Jumping Takahashi (300点)
D - Strange Balls (400点)
E - Ranges on Tree (500点)
F - Sum Sum Max (500点)
G - Teleporting Takahashi (600点、実行時間制限: 3 sec): 未提出
Ex - Sequence of Substrings (600点、実行時間制限: 5 sec): 未提出
結果、感想

A - Edge Checker (100点)

隣同士の点の番号の差は $1$ か $9$ なので、それをif文で条件分岐します。

B - Count Distinct Integers (200点)

色々解法がありますが、std::setに突っ込んで解きました。

C - Jumping Takahashi (300点)

DPです。

${\mathrm{dp}}_{i,j} = (\text{$i$ 回のジャンプをした後に座標 $j$ の位置にいるようにできるか})$

としたとき、初期状態

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

で、 $0 \lt i \leq N$ について

${\mathrm{dp}}_{i,j}={\mathrm{dp}}_{i-1,j-a_i} \lor {\mathrm{dp}}_{i-1,j-b_i}$

という遷移で答えを求めることができます。実際には貰うDPではなく配るDPで実装しました。
また、公式解説にもあるようにstd::bitsetを用いることで若干の高速化を実現することができます。

問題文の通りのことをそのまま実装すると $O(N^2)$ となりますが、C++ではそれでもギリギリ通るそうですが、私は想定解の方法で通しました。
同じ整数のボールについて $($ 整数 $,\,$ 個数 $)$ の組で表し、これをスタックで管理することで計算量を $O(N)$ に落とすことができます。
C++ではスタックのためのデータ構造としてstd::stackがありますが、std::vectorやstd::dequeを使うことが殆どです。

E - Ranges on Tree (500点)

与えられた木の葉を $v_1,\,v_2 ,\dots,\,v_n$ とすると、任意の異なる2つの葉 $v_i,\,v_j$ について $S_{v_i} \cap S_{v_j} = \emptyset$ であるため、それに対応する集合 $[L_{v_i},\,R_{v_i}],$ $[L_{v_j},\,R_{v_j}]$ が互いに素でなければならず、 $\displaystyle\max\left\{\max_i L_i,\,\max_j R_i\right\} \geq n$ であることが分かります。

一方で、各葉に対応する集合を上手く構築し、その他の頂点についてはその子頂点に対応する集合の和集合にすることで $\displaystyle\max\left\{\max_i L_i,\,\max_j R_i\right\} = n$ を達成することができ、解のうちの1つとなります。それはDFSでの到達順に葉に1から順に番号を付け、その番号を対応する集合の唯一の要素とすることです。これで解を構築することができました。

F - Sum Sum Max (500点)

$C$ で同じ値が続く区間ごとに考えます。
$\displaystyle \sum_{i = 1}^{k} y_k = Y$ とします。

$A_{Y + j} = \displaystyle A_{Y} +j \sum_{i = 1}^{k} x_i y_i + y_{k+1} \sum_{i = 1}^{j} i = A_{Y} +j \sum_{i = 1}^{k} x_i y_i + \frac{j(j+1)}{2} x_{k+1}$

が成り立ちます。
$\displaystyle \sum_{i = 1}^{k} x_i y_i \leq 0$ または $x_{k+1} \geq 0$ のときはその区間について単調であるか、下に凸であるため、最大値をとる可能性があるのは両端のときだけであるが、そうでないときは、上に凸であるため、途中で最大値をとる可能性があります。そのとき最大値をとるのは $j =\displaystyle\left\lfloor -\frac{ \sum_{i = 1}^{k} x_i y_i}{x_{k+1}}\right\rfloor$ のときであるため、それを個別に計算すればいいです。

G - Teleporting Takahashi (600点、実行時間制限: 3 sec): 未提出

ちょっと思いつきませんでした...

Ex - Sequence of Substrings (600点、実行時間制限: 5 sec): 未提出

うむ、分からん

結果、感想

f:id:Flkanjin:20220222164317p:plain
久しぶりの黄パフォで青に復帰することができました。ちゃんとこのままレートを増やしていきたいですね。