競プロチャレンジ供養会場: AtCoder Beginner Contest 214 E - Packing Under Range Regulations

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

問題

Difficulty: 1835 (記事作成時点)

供養

解法

• $x = 1, \dots , 10^{9}$ について、まだ箱に入れておらず $L_{i} \le x$ であるようなボールの集合を $B$ とする
• このとき、箱 $x$ に入れるべきボールは $B$ のうち $R_{i}$ が最小のもの
  • ここで選んだボールが $R_{i} \lt x$ の場合は条件を満たす入れ方は存在しない
• PriorityQueue を用いて以下の操作をする
  • $B$ が空の場合、箱に入っていないボールの $L_{i}$ のうち最小の $L_{i}$ まで $x$ をとばす
  • $L_{i} = x$ であるようなボールをすべて $B$ に追加する
  • まだ $B$ に含まれていないボールの $L_{i}$ のうち最小の $L_{i}$ について $x \lt L_{i}$ である間、以下の操作を実施する
    • $B$ に含まれるボールのうち、$R_{i}$ が最小のボールを選ぶ
    • 選んだボールを $k$ としたとき、$x \le R_{k}$ ならば $k$ を $B$ から除外する
      • 除外できないときは $x \ge R_{k}$ なので、条件を満たす入れ方は存在しない
    • $x$ を1増加させる
  • 最初に戻る
• 上記の操作を最後まで実施できれば Yes、そうでなければ No が答え

実装

計算量はテストケースごとに $O(N \log N)$

公式解説

躓いた点

• AVL木を使おうとして実装が間に合わなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 214 D - Sum of Maximum Weights

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

問題

Difficulty: 1341 (記事作成時点)

供養

解法

• ある連結成分で最も重みの大きな辺を $uv$、重みを $w$ として、連結成分を $uv$ で分割したときに $u$ が所属する側の点集合を $U$、$v$ が所属する側の点集合を $V$ とすると、任意の $u^{'} \in U, v^{'} \in V$ の組合せについて $f(u^{'}, v^{'}) = w$ となる
• よって、$\sum_{u^{'} \in U}\sum_{v^{'} \in V}f(u^{'}, v^{'}) = |U| \times |V| \times w$
• 上記を再帰的に適用することで重みの合計を得ることができる
• 適用を逆から見ていくと、最も重みの小さな辺を使って連結成分を結合していき、その時の結合する連結成分の大きさと重みの積の和が答えとなることがわかる

実装

計算量は $O(N \log N)$

公式解説

躓いた点

• 小さい順に見る発想が出なかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 212 F - Greedy Takahashi

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

問題

Difficulty: 2332 (記事作成時点)

供養

解法

• 時刻 $t$ に起こりうるアクションとその順番を固定するために以下のように時刻を変更した操作列を作る
  • 時刻 $3S_{i} + 2$ にバス $i$ が発車する
  • 時刻 $3T_{i} + 1$ にバス $i$ が到着する
  • 時刻 $3X_{j}$ に行動 $j$ を開始する
  • 時刻 $3Z_{j}$ に行動 $j$ における現在地を出力する
• 同時刻に同じ場所にいる2つの行動パターンは以後異なる地点に行くことはないので、代表点を使って集団を考える
  • 行動パターン $k$ が代表となる集合を $U_{i}$ とする
  • $R_{c} = k$ のとき、都市 $c$ に $U_{k}$ がいるものとする
    • $R_{c} = 0$ ならばその時点において都市 $c$ にいる行動パターンは存在しないとする
  • $C_{i} = k$ のとき、その時刻においてバス $i$ に $U_{k}$ が乗っているものとする
• 現時点での $U_{k}$ の状態を $V_{k}$ とする
• ある $u$ が属する集合の代表点を返す関数を $\mathit{Find}(u)$、$u, v$ がそれぞれ属する2つの集合を結合して新たな集合を作り、その代表点を返す関数を $\mathit{Unite}(u, v)$ とする
  • $u = 0$ のとき（属する集合が空集合のとき）$\mathit{Unite}(u, v) = \mathit{Find}(v)$
• 変更後の時刻の早い順に以下のように操作を実施する
  • バス $i$ が発車する場合
    • $R_{A_{i}} = k \neq 0$ のとき、$R_{A_{i}} = 0, C_{i} = k, V_{k} = \lbrack A_{i}, B_{i} \rbrack$ とする
  • バス $i$ が到着する場合
    • $C_{i} = k \neq 0$ のとき、$R_{B_{i}} = \mathit{Unite}(R_{B_{i}}, k), V_{R_{B_{i}}} = B_{i}$ とする
  • 行動 $j$ を開始する場合
    • $V_{j} = Y_{j}, R_{Y_{j}} = \mathit{Unite}(R_{Y_{j}}, j)$ とする
  • 行動 $j$ における現在地を出力する場合
    • $V_{\mathit{Find}(j)}$ をクエリ $j$ の答えとして記憶しておく
• 操作を実施後、記憶していたクエリの答えを順に出力していく

実装

計算量は $O( (M + Q)\log (M + Q) )$

公式解説

躓いた点

• 同時刻でもバスが到着してから出発するよう順序を固定することの考慮漏れ

競プロチャレンジ供養会場: AtCoder Regular Contest 124 C - LCM of GCDs

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

問題

Difficulty: 1495 (記事作成時点)

供養

解法

• $a_{1}, b_{1}$ が入った集合の約数をそれぞれ $x, y$ と決め打った時に、それらを約数とするような集合を作れるかは $O(N)$ で計算できる
  • 各 $i$ について、$x$ が $a_{i}$ の約数かつ $y$ が $b_{i}$ の約数であるか、$x$ が $b_{i}$ の約数かつ $y$ が $a_{i}$ の約数であるかを調べればよい
• 集合を作れるような $x, y$ の最小公倍数の最大値を答えとすればよい
• $x, y$ はそれぞれ $a_{1}, b_{1}$ の約数を全列挙して調査しても十分間に合う

実装

計算量は $a_{1}, b_{1}$ の約数の数をそれぞれ $d(a_{1}), d(b_{1})$ として $O(d(a_{1})d(b_{1})N)$

公式解説

躓いた点

• 約数の全列挙を思いつかなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 211 F - Rectilinear Polygons

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

問題

Difficulty: 2350 (記事作成時点)

供養

解法

• 簡単のため多角形がすべて長方形の場合を考えると、長方形が $(x_{i, 1}, y_{i, 1}), (x_{i, 1}, y_{i, 2}), (x_{i, 2}, y_{i, 1}), (x_{i, 2}, y_{i, 2})$ の4点からなるとき、$(x_{j}, y_{j})$ がいくつの長方形に含まれるかという問題になる
  • $x_{i, 1} \lt x_{i, 2}, y_{i, 1} \lt y_{i, 2}$ とする
• 2次元区間和を使って $x = 0, 1, \dots$ のときに $y = 0, 1, \dots$ にいくつの長方形が重なっているかを区間和を更新しながら求める
  • $x = x_{i, 1}$ のときに $y = y_{i, 1}$ で $+1$、$y = y_{i, 2}$ で $-1$
  • $x = x_{i, 2}$ のときに $y = y_{i, 1}$ で $-1$、$y = y_{i, 2}$ で $+1$
  • $x = x_{j}$ のときに、その時点まで操作をした後の $\lbrack 0, y_{j} \rbrack$ の区間和がクエリの答えとなる
  • 区間和はBITで持っておくと任意の $y$ についての計算ができる
• 多角形が長方形でない場合の処理を考える
  • 多角形を $x$ 軸に平行にスライスすると長方形の集合となる
  • このとき、各長方形の操作を合算すると元の多角形で頂点ではない部分の操作は打ち消しあう
    • $(x, y)$ が左下（右下）の場合の操作と左上（右上）の場合の操作が打ち消しあう関係にある
  • 残った操作は長方形の左下もしくは右上に相当する操作と左上もしくは右下に相当する操作が元の多角形の頂点順に交互に現れる
  • $x$ について最小な頂点集合の中で $y$ について最小な頂点 $(x_{i, j}, y_{i, j})$ は必ず長方形の左下に相当する
  • $(x_{i, j}, y_{i, j})$ から順にどちらの操作かを決めていき、対応する位置での操作となるよう操作列に組み込んでいけばよい

実装

計算量は $y$ 軸方向の最大値を $U$ として $O((\sum M+Q)\log U)$

公式解説

躓いた点

• 多角形の場合の処理が時間内に思いつかなかった

競プロチャレンジ供養会場: AtCoder Regular Contest 123 D - Inc, Dec - Decomposition

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

問題

Difficulty: 2143 (記事作成時点)

供養

解法

• ある最適解は、任意の $1 \le i \lt N$ について $B_{i} = B_{i + 1}$ もしくは $C_{i} = C_{i + 1}$ の少なくとも一方が成り立っている
  • ある $1 \le i \lt N$ について $B_{i} \lt B_{i + 1}$ かつ $C_{i} \gt C_{i + 1}$ であるような解の数列 $B, C$ があったとする
  • このとき、以下のように作成した数列 $B^{'}, C^{'}$ を考える
    • $B_{i} \lt 0$ ならば $j \le i$ について $B_{j}$ を $1$ 増加、$C_{j}$ を $1$ 減少させる
    • $B_{i + 1} \gt 0$ ならば $j \ge i + 1$ について $B_{j}$ を $1$ 減少、$C_{j}$ を $1$ 増加させる
  • 各 $1 \le i \le N$ について $B^{'}_{i} + C^{'}_{i} = A_{i}$ は維持されている
  • $B_{i} \lt 0$ のとき、$\sum_{j = 1}^{i}|B^{'}_{j}| = \sum_{j = 1}^{i}|B_{j}| - i$ であり、$\sum_{j = 1}^{i}|C^{'}_{j}| \le \sum_{j = 1}^{i}|C_{j}| + i$ である
    • $B_{j} \lt 0$ なので $|B^{'}_{j}| = |B_{j} - 1| = |B_{j}| - 1$
    • $|C^{'}_{j}|$ は $C_{j}$ の値によって以下のようになる \begin{align} |C^{'}_{j}| = \begin{cases} |C_{j}| + 1 & \mathrm{if}\;C_{j} \ge 0 \\ |C_{j}| - 1 & \mathrm{if}\;C_{j} \lt 0 \end{cases} \end{align}
  • $B_{i + 1} \gt 0$ のとき、$\sum_{j = i + 1}^{N}|B^{'}_{j}| = \sum_{j = i + 1}^{N}|B_{j}| - (N - i)$ であり、$\sum_{j = i + 1}^{N}|C^{'}_{j}| \le \sum_{j = 1}^{N}|C_{j}| + (N - i)$ である
  • よって、どちらの場合においても $\sum_{j}(|B^{'}_{j}| + |C^{'}_{j}|) \le \sum_{j}(|B_{j}| + |C_{j}|)$ であることから、同等以上によい解である $B^{'}, C^{'}$ が存在する
  • これを繰り返すことで、任意の $1 \le i \lt N$ について $B_{i} = B_{i + 1}$ もしくは $C_{i} = C_{i + 1}$ の少なくとも一方が成り立つような $B, C$ まで局所最適化を実行できる
• 上記の性質を踏まえると、$i \gt 1$ について $B_{i} = B_{i - 1} + \max(A_{i} - A_{i - 1}, 0), C_{i} = C_{i - 1} + \min(A_{i} - A_{i - 1}, 0)$ であるような数列が存在する
  • $A_{i} \gt A_{i - 1}$ のとき、$B_{i} = B_{i - 1}$ だと $C_{i} \gt C_{i - 1}$ となってしまうため、$B_{i} = B_{i} + (A_{i} - A_{i - 1}), C_{i} = C_{i - 1}$
  • $A_{i} \lt A_{i - 1}$ のときも同様に考えることができる
  • $A_{i} = A_{i - 1}$ ならば変化させる必要なし
• また、$C_{1} = A_{1} - B_{1}$ であることから上記の性質をもった数列は $B_{1}$ を決めるとすべての値を一意に決めることができる
• よって、$|B_{i}|, |C_{i}|$ は $B_{1}$ を用いて $|B_{1} - d|$ の形式で表現できる
• 上記より、$\sum_{i}(|B_{i}| + |C_{i}|)$ を最小化する問題は $2N$ 個の $d_{j}$ が与えられたときに $\sum_{j}|B_{1} - d_{j}|$ を最小化する $B_{1}$ を選ぶ問題と等しくなる
  • その問題については $B_{1}$ が $B_{1}, d_{1}, \dots, d_{2N}$ の $2N$ 個のなかで中央値となるようにすればよい
• 選んだ $B_{1}$ から $\sum_{i}(|B_{i}| + |C_{i}|)$ を計算して出力すればよい

実装

計算量は $O(N)$

公式解説

躓いた点

• 中央値を選べばよいというところまで到達できなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 210 D - National Railway

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

問題

Difficulty: 1570 (記事作成時点)

供養

解法

• 自明な上界として、隣接する2地点に駅を建て、距離1の線路で繋いだものの最小値がある
  • $U$ とする
• 距離2以上の線路を、点 $(h, w)$ から東西南北のうち2方向に伸びた線路とその先に建った駅と考える
• $(h, w)$ から東方向に線路を伸ばして駅を建てる場合を考える
  • $1 \le j \le W - w$ について、$(h, w + j)$ まで線路を伸ばして駅を建てる場合のコストは $A_{h, w + j} + jC$ である
  • よって、東方向に伸ばした場合の最小コスト $E_{h, w}$ は $\min_{j = 1}^{W - w}(A_{h, w + j} + jC) = \min_{j = w + 1}^{W}(A_{h, j} + jC) - wC$
    • $E_{h, W} = \infty$ とする
  • $\min_{j = w + 1}^{W}(A_{h, j} + jC)$ の部分を $E^{'}_{h, w}$ とすると、$E^{'}_{h, w}$ は $E^{'}_{h, w + 1}$ の結果を使えるので $w = W - 1, \dots, 1$ の順番で効率的に求めることができる
• 同様に西、南、北に線路を伸ばした場合の最小コストをそれぞれ $W_{h, w}, S_{h, w}, N_{h, w}$ と求めることができる
• $\min_{h, w}\left(\min(E_{h, w} + W_{h, w}, E_{h, w} + S_{h, w}, E_{h, w} + N_{h, w}, W_{h, w} + S_{h, w}, W_{h, w} + N_{h, w}, S_{h, w} + N_{h, w})\right)$ と $U$ を比較して小さいほうが答え

実装

計算量は $O(HW)$

公式解説

躓いた点

• 各方向絵の最短距離を毎回探索で求めようとしてTLE