コンテストでの時間切れや解けなかった過去問を振り返って供養していく

8/2: AtCoder beginner Contest 174 F - Range Set Query

供養

問題

Difficulty: 1575 (記事作成時点)

$i = 1, \dots, N$ の順に見ていき、各色 $c$ について最後に登場した位置 $\mathit{LA}_{c}$ を記録しておく
BITを用いて $\mathit{LA}_{c}$ が更新されるたびに
クエリを先読みして $R$ の昇順でソートしておき、 $i \ge R_{j}$ となったときに $\lbrack L_{j}, R_{j} \rbrack$ の区間和を求める

実装は

長さ $N + 1$ の配列 $\mathit{LA}$ を用意する
区間の区間和が求められるBIT を用意する
- $\mathit{Query}(l, r)$ で $\lbrack l, r \rbrack$ の区間和を求められるとする
をについて昇順にソートする
- ソート後の値を $(L_{j}, R_{j}, q_{j})$ とする
長さ $Q$ の配列 $A$ を用意し、 $j = 0$ とする
について、以下の操作を実施する
- $B_{i + 1} = 1$ とする
- $\mathit{LA}_{c_{i}} \gt 0$ ならば $B_{\mathit{LA}_{c_{i}}}$ をデクリメントする
- $\mathit{LA}_{c_{i}} = i + 1$ とする
- である間、以下の操作を実施する
  - $A_{q_{j}} = \mathit{Query}(L_{j}, R_{j})$ とする
  - $j = j + 1$ とする
$0 \le j \lt Q$ について、 $A_{j}$ を出力していく

計算量は $O(N\mathrm{log}N + Q\mathrm{log}N + Q\mathrm{log}Q)$

供養

Difficulty: 1456 (記事作成時点)

$i \to P_{i}$ を辺とすると1つ以上のサイクルからなるグラフができる
各点 $i$ について、 $i$ を始点にグラフ上を周回したときに得られるスコアの最大値を求める
が属するサイクルの長さをとすると、最大でもステップまで考えればよい
- サイクルを1周して得られるスコアが正ならば、サイクルを可能な限り周回した後のスコアで考える

実装は

計算量は $O(N^{2})$

供養

Difficulty: 1187 (記事作成時点)

$x$ 座標と $y$ 座標を独立に爆破できる建物の数を数えておく
それぞれの方向で最大に爆破できる座標の集合を $X, Y$ 、爆破できる建物の数をそれぞれ $R, C$ とする
$(x \in X, y \in Y)$ を見ていき、1つでも爆破対象が存在しない座標があれば最大値は $R + C$ 、そうでなければ $R + C - 1$ となる