第11回アルゴリズム実技検定

114:52 で全完しました。

A

うさぎは $\dfrac{X}{A} + C$ 秒、かめは $\dfrac{X}{B}$ 秒掛かるので分母を払って整数で比較。

B

連想配列に入れてカウント。

C

$10 ^ 9$ より大きい値は $10 ^ 9 + 1$ に潰してもよいので、$\min(N ^ k, 10 ^ 9 + 1)$ を前から求めていくと overflow しない。

D

Union Find で同一視されるグループを求めておく。すべての $i$ に対して $S_i$ と $T_i$ が同じグループに属しているなら Yes で、それ以外は No。

E

$(v,\ldots,2,1,2,\ldots,v)$ は $2v - 1$ 項なので、操作 $v$ が終わった時点での数列 $A$ の長さは $\sum _ {i = 1} ^ v (2 i-1) = v ^ 2$ と分かる。

従って、$N$ 項目は操作 $\lfloor \sqrt{N-1} \rfloor + 1$ で追加されることが分かるので、あとは添え字を合わせれば OK。

F

愚直にシミュレートして $O (H (W+N) )$ で間に合う。

G

Union Find で連結成分数を求めて、これがちょうど $1$ なら Yes で、それ以外は No。

H

$\mathrm{dp}[i][w_a][w_b]$ を「$1,\ldots, i$ 番目までのお菓子を見て、$1$ つめのナップサックに入れたお菓子の重さの合計が $w_a$ 以下、$2$ つめのナップサックに入れたお菓子の重さの合計が $w_b$ 以下となるように詰める場合の価値の最大値」として定めれば状態数 $O(NAB)$、遷移 $O(1)$ なので十分高速。

I

すぬけ君の位置が $\mathrm{pos} _ s$、荷物の位置が $\mathrm{pos} _ a$ の状態 $(\mathrm{pos} _ s, \mathrm{pos} _ a)$ を頂点にしたグラフで BFS をすればよい。

J

Python の datetime モジュールを使うとよい。

K

$\# \{S \text{の部分列} \} + \# \{T \text{の部分列} \} - \# \{S \text{と} T \text{の共通部分列} \}$ として計算する。

$\# \{S \text{の部分列} \}$ は https://judge.yosupo.jp/problem/number_of_subsequences をやればよく、共通部分列の場合はこれを拡張して状態を添え字のペアにすれば OK。

L

最長共通部分列の DP に文字を変更した回数を追加で状態として持てばよい。

M

$2$ 人のスコアが両方とも $i\; (0 \lt i \lt N)$ となった次のゲームで $\dfrac{1}{2}$ の確率で逆転が起こる。従って、求める答えは次で表される。

$$ \sum _ {i = 1} ^ {N - 1} \binom{2i}{i} \cdot \dfrac{1}{2 ^ {2i + 1}} $$

N

最小カットなので、頂点を in と out に分けて最大流。

O

点 $p_i = (x_i ,y_i)$ の寄与を考える。$\arg p _ j \in [\arg p _ i, \arg p _ i + \pi)$ なる $j$ の集合を $S$、それ以外の $j$ の集合を $T$ とすれば、点 $p _ i$ の寄与は次のように書ける。

$$\begin{aligned} \sum _ {j \in S \sqcup T} \vert x _ i y _ j - y _ i x _j \vert &= x_i \left(\sum _ {j\in S} y _ j \right) - y _ i \left(\sum _ {j\in S} x _ j \right) \\ & - x_i \left(\sum _ {j\in T} y _ j \right) + y _ i \left(\sum _ {j\in T} x _ j \right) \end{aligned}$$

偏角ソートしておけば $S, T$ はそれぞれ定数個の区間の和となるので、予め偏角を座圧して BIT に $x _ j$ や $y _ j$ の和を乗せることで答えを差分更新できる。