コンテストでの時間切れや解けなかった過去問を振り返って供養していく
01/23: AtCoder Beginner Contest 189 C - Mandarin Orange
Difficulty: 565 (記事作成時点)
供養
解法1
- $i = 1, \dots, N$ について、皿 $i$ を含み $A_{i}$ を最小値とするような選び方を考える
- 各 $i$ について、左右それぞれに $A_{i}$ 以上の $A_{j}$ を $i$ からどれだけ連続して選べるかを計算することで上記を求められる
- 左側の連続数 $L_{i}$ についてはスタックで $\lbrace (A_{j}, j) | \text{for all}\; j \lt k \lt i, A_{j} \le A_k \rbrace$ を管理していれば、最初に $A_{j} \lt A_{i}$ となる $j$ で求められる
- $A_{j} \ge A_{i}$ であるような $(A_{j}, j)$ をスタックから除いていき、$L_{i}$ の計算後に $(A_{j}, j)$ をスタックに積む
- 右側についても左右を反転して同様に計算できる
実装
計算量は $O(N)$
解法2
この問題に関しては愚直にやっても間に合う
- $X = 0$ とする
- $s = 1, \dots, N$ について、以下の計算を実施する
- $m = A_{s}$ とする
- $t = s, \dots, N$ について、以下の計算を実施する
- $m = \mathrm{min}(A_{t}, m)$ とする
- $X = \mathrm{max}(m \times (t - s + 1), X)$ とする
- $X$ を出力する
計算量は $O(N^{2})$
公式解説
躓いた点
- 解法をド忘れしていた
- 愚直にやったら間に合わないと思っていた
01/24: AtCoder Beginner Contest 189 F - Sugoroku2
Difficulty: 2154 (記事作成時点)
供養
解法
- ゴールできないマスの条件は以下
- 自身が振出しに戻るマス
- 自身の先 ${M}$ マスがすべてゴールできないマス
- マス $i$ からゴールするまでの期待値を $E_{i}$ とすると、$E_{i}$ は以下の式で求められる
\begin{align}
E_{i} =
\begin{cases}
0 & (i = N) \\
E_{0} & (\text{マス}\;i\;\text{がゴール不可能}) \\
\frac{\sum_{j = 1}^{M}E_{\mathrm{min}(i + j, N)}}{M} + 1 & (\text{マス}\;i\;\text{がゴール可能})
\end{cases}
\end{align}
- マス $0$ がゴール可能な場合、$E_{0} = aE_{0} + b$ の形式で表現されることになるので、$E_{0} = \frac{b}{1 - a}$ となる
実装
計算量は $O(N)$
公式解説
躓いた点
01/30: AtCoder Beginner Contest 190 E - Magical Ornament
Difficulty: 1645 (記事作成時点)
供養
解法
- 列を作れるかどうかは $(A_{i}, B_{i})$ を同じ集合とするUnion-Findなどですべての $C_{i}$ が同じ集合に属するかを調べればよい
- 長さの最小化は $(A_{i}, B_{i})$ を辺とするグラフについて、任意の $C_{i}, C_{j}$ 間の距離を求めた $K \times K$ 行列から巡回サラリーマン問題をbitDPで解けばよい
- 今まで巡回した集合 $S$、現在の位置 $u$ についての $2^{K} \times K$ のDPを作成し、次に $v$ を訪れるときは $\mathit{DP}_{S \cup v, v}$ を $\mathit{DP}_{S, u} + d_{u, v}$ で更新可能か調べればよい
実装
計算量は作成可能かの判定で $O(N + M)$、距離行列の作成が $O(K(N + M))$、bitDPが $O(2^{K}K^{2})$ なので、合計で $O(K(N + M) + 2^{K}K^{2})$
公式解説
躓いた点
01/31: AtCoder Beginner Contest 190 F - Shift and Inversions
Difficulty: 1321 (記事作成時点)
供養
解法
- $k = 0$ のときは単純に $A$ の転倒数を求めればよい
- $k \ge 1$ のときは、直前の時点で先頭にいた $A_{k}$ が最後尾に行くので、$A_{k}$ より大きな数は転倒数にカウントされるようになり、小さな数はカウントされなくなるので $I_{k} = I_{k - 1} + N - 1 - 2A_{k}$ で計算できる
実装
計算量は $O(N \mathrm{log} N)$
公式解説
躓いた点
