競プロチャレンジ供養会場: AtCoder Regular Contest 126 C - Maximize GCD

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

問題

Difficulty: 1824 (記事作成時点)

供養

解法

• $\max(A_{1}, \dots, A_{N}) = A_{\max}$ とする
• $A_{1}, \dots, A_{N}$ を $K$ 回の操作で $x$ の倍数にできるかを以下の方法で判定する
  • $x \gt A_{\max}$ のとき
    • $Nx - \sum A_{i} \le K$ ならば可能
  • $x \le A_{\max}$ のとき
    • $a_{i} \le A$ であるような $a_{i}$ の個数およびそれらの合計を累積和で求めておくと、$(k - 1)x \lt a_{i} \le kx$ であるような $a_{i}$ を $x$ の倍数にするための操作回数をまとめて求めることができる
      • $a_{i} \le A$ であるような $a_{i}$ の個数の累積和を $C_{A}$、合計を $S_{A}$ とすると、$( C_{kx} - C_{ (k - 1)x } )kx - ( S_{kx} - S_{ (k - 1)x} ) $
    • よって、$O(\lceil \frac{A_{\max}}{x} \rceil)$ で操作回数の総和を求めることができるので、それが $K$ 以下か判定
• $\lfloor \frac{K+\sum A_{i}}{N} \rfloor \gt A_{\max} $ ならばそれが最大値となる
• $x = 1, \dots, A_{\max}$ について上記の計算をすると、全体で $\sum \lceil \frac{A_{\max}}{x} \rceil = O(A_{\max} \log A_{\max})$ で計算可能

実装

計算量は $O(N + A_{\max} \log A_{\max})$

公式解説

躓いた点

• 累積和で計算時間の削減をする部分が思いつかなかった

競プロチャレンジ供養会場: AtCoder Regular Contest 126 B - Cross-free Matching

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

問題

Difficulty: 1370 (記事作成時点)

供養

解法

• $( (a_{i}, 0), (b_{i}, 1) )$ について、$a_{i} \le A$ であるような線分のみ使用することを考える
  • 簡単のため線分 $( (a_{i}, 0), (b_{i}, 1) )$ を $(a_{i}, b_{i})$ と表記する
• $a_{j} \le A$ である線分のみでちょうど $k$ 個選択したときに、$k$ 個目の $b_{j}$ が最も小さくなるような選び方した場合の $k$ 個目の $b_{j}$ を $B_{A, k}$ とする
  • このとき、存在する範囲において $B_{A, 1} \lt B_{A, 2} \lt \dots \lt B_{A, k}$ である
• $(A, b_{i})$ を選び、かつ最も多く選ぶには、$a_{j} \lt A$ かつ $b_{j} \lt b_{i}$ であるような線分についての最も多い選び方をする必要がある
  • すなわち、$B_{A - 1, k - 1} \lt b_{i}$ であるような最大の $k$ について、$k$ 個選ぶのが最大
  • したがって、$B_{A, k} = \min (b_{i}, B_{A, k})$ となる
  • $a_{i} = A$ であるような $(a_{i}, b_{i})$ を $b_{i}$ について降順に見ていけば、その時点において $B_{A, k - 1} \lt b_{i}$ であるような最大の $k$ について、$B_{A, k} = b_{i}$ に更新できる
    • 更新対象は二部探索で求められる
• $(a_{i}, b_{i})$ を $a_{i}$ について昇順、同値の時は $b_{i}$ について降順に上記の方法で $B_{A, k}$ を更新していき、$B_{N, k}$ が存在する最大の $k$ が答
  • 端的には、ソートした順に $b_{i}$ を並べた数列の LIS の長さ

実装

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

公式解説

躓いた点

• 問題を複雑に考えすぎた

競プロチャレンジ供養会場: サイシードプログラミングコンテスト2021 (AtCoder Beginner Contest 219) G - Propagation

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

問題

Difficulty: 2287 (記事作成時点)

供養

解法

• 各点 $u$ について、クエリ $i$ の時点での色が $x$ であったとする $C_{u} = (x, i)$ と、クエリ $i$ で隣接点に伝搬させた色が $x$ であったとする $X_{u} = (x, i)$ を持っておく
• クエリ $i$ において、点 $u = x_{i}$ がその時点で何色であったかを確定させるには、$C_{u}$ および $u$ の各隣接点 $v$ の $X_{v}$ のうち、もっとも新しい情報 i.e. 最大の $i$ を持つ $(x, i)$ を採用すればよい
• 比較対象とする $X_{v}$ を、$v$ の次数が一定数以上のものに限定する
  • $v$ の次数が一定数以下であった場合、$v$ の評価時点で（$u$ を含む）$v$ の各隣接点 $w$ の $C_{w}$ を更新してしまい、改めて $u$ を評価する機会が訪れた場合に $X_{v}$ と比較させない
  • $v$ の次数が一定以上の場合は $X_{v}$ だけ更新し、隣接点の $C_{w}$ は更新しない
• 次数の閾値を $B$ とすると、$u$ の周囲で比較対象となりうる点の数は高々 $\frac{2M}{B}$ であり、周囲の $C_{v}$ を更新する回数も高々 $B$
  • $B = \sqrt{M}$ とすると、$C_{u}$ の更新も伝搬も $O(\sqrt{M})$ で実施できる

実装

計算量は $O(N + M + Q \sqrt{M})$

公式解説

躓いた点

• 比較方法を次数で分ける発想が出なかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 218 F - Blocked Roads

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

問題

Difficulty: 1753 (記事作成時点)

供養

解法

• 点 $N$ までの任意の最短パス $P$ を求め、$P$ を構成する辺を覚えておく
• 除外する辺が $P$ に含まれる場合、その辺を除いたグラフで再計算する
  • $P$ の長さは高々 $N - 1$ なので、再計算も高々 $N - 1$ 回
• 除外する辺が $P$ に含まれない場合、$P$ の長さを出力すればよい

実装

計算量は $O(N(N+M))$

公式解説

躓いた点

• 再計算の回数が高々 $N - 1$ 回であることに気づかなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 217 F - Make Pair

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

問題

Difficulty: 1954 (記事作成時点)

供養

解法

• $N$ 組のペアを作ったとき、各ペアは必ず偶数と奇数の組である
  • 以降は $A_{i}, B_{i}$ の偶奇が異なることを前提に進める
• $u$ から始まる連続する $2n$ 人について $n$ 組のペアを作る手順の場合の数を $\mathit{DP}_{u, n}$ とする
  • 任意の $u$ について $\mathit{DP}_{u, 0} = 1$ とする
• $n = 1, \dots, N$ について以下のようにDP表を更新する
  • $u = 1, \dots, 2N - 2n + 1$ について、$u \lt v \le u + 2n$ かつ $(A_{i}, B_{i}) = (u, v)$ なる $i$ が存在するような $v$ とペアとなるような組み方と、$v + 1, \dots, u + 2n$ までの任意の組み方を考える
    • $u, v$ をペアにするには $u + 1, \dots, v - 1$ を全てペアにしてから最後に $u, v$ をペアにするので、$k = \frac{v - u + 1}{2}$ として $\mathit{DP}_{u + 1, k - 1}$ 通り
    • $u, \dots, v$ のペアの作り方と $v + 1, \dots, u + 2n$ のペアの作り方は独立なので、$_{n}\mathrm{C}_{k}$ 通り
    • 上記より、$_{n}\mathrm{C}_{k} \times \mathit{DP}_{u + 1, k - 1} \times \mathit{DP}_{v + 1, n - k}$ 通りの作り方が存在する
    • 上記を合計することで $\mathit{DP}_{u, n}$ を求めることができる
• $\mathit{DP}_{1, N}$ が答えとなる

実装

計算量は $O(NM)$

公式解説

躓いた点

• DFSで求めようとして実装が悪くエラー

競プロチャレンジ供養会場: AtCoder Regular Contest 125 D - Unique Subsequence

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

問題

Difficulty: 2187 (記事作成時点)

供養

解法

• 取り出し方が一意に定まるような長さ $k$ の部分列の添字列を $x_{1} \lt \dots \lt x_{k}$ としたとき、先頭と最後に $x_{0} = 0, x_{k + 1} = N + 1$ を追加した$0 = x_{0}, x_{1}, \dots, x_{k}, x_{k + 1} = N + 1$ について考える
  • このとき、部分列の取り出し方が一意であるためには $1 \le i \le k$ について、$A_{x_{i - 1} + 1}, \dots, A_{x_{i + 1} - 1}$ の中で $A_{x_{i}}$ と同値の要素は $A_{x_{i}}$ 以外に存在しないことが必要
• $A$ の先頭から $i$ 番目の要素まで見たときに、$A_{i}$ を含み、かつ取り出し方が一意に定まる部分列の種類数を $P_{i}$ とする
• $A_{i}$ と同値の要素で、$A_{i}$ 以前に最後に登場した位置を $i^{'}$ とすると、$i^{'} \le j \lt i$ のうち $j + 1, \dots, i - 1$ に $A_{j}$ と同値のものは存在しないような $j$ について $P_{j}$ を合計したものが $P_{i}$ となる
• 上記を求める手法は以下の通り
  • $C_{A_{i}}$ を値が $A_{i}$ の要素が $i$ より前に最後に登場した位置とする
    • 初期値はすべて $0$ とする
  • $P_{0} = 1$ とする
  • $P_{i} = \sum_{j = C_{A_{i}}}^{i - 1}P_{j}$ とする
    • BITで管理すれば高速に求められる
  • $P_{C_{A_{i}}} = 0$ とする
    • $i$ より後のsumに含まれないようにする
• 最終的に $\sum_{i = 1}^{N}P_{i}$ が答え

実装

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

公式解説

躓いた点

• BITで管理する発想が出てこず、DPで解こうとして失敗

競プロチャレンジ供養会場: AtCoder Beginner Contest 215 F - Dist Max 2

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

問題

Difficulty: 1853 (記事作成時点)

供養

解法

• ある数 $K$ について、異なる2点の距離の最大値 $D$ が $K$ 以上であるかを考える
  • 2点 $i, j$ の距離が $K$ 以上であるということは $|x_{i} - x_{j}| \ge K$ かつ $|y_{i} - y_{j}| \ge K$ である
    • $(i, j)$ の組が存在するかの判定なので、$x_{i} \ge x_{j}$ を仮定してよい
  • ある点 $i$ について、$x_{j} \le x_{i} - K$ であるようなすべての $j$ のうち、$y_{j} \ge y_{i} + K$ もしくは $y_{j} \le y_{i} - K$ であるような $j$ が存在すれば $D \ge K$ である
  • 点を $x$ についてソートし、$i = 2, \dots$ について $x_{j} \le x_{i} - K$ であるような $j$ のうち $y_{j}$ の最大値と最小値をそれぞれ求め、$y_{i}$ との差が $K$ 以上か判定すればよい
    • $i = k$ のとき $i = k - 1$ のときの最大値と最小値を使って、$x_{j} = x_{i} - K$ であるような $j$ のみで最大値と最小値を更新すればよいので、$O(N)$ で判定可能
• $K$ について二部探索すれば答えが出る

実装

計算量は $x_{i}$ の最大値を $X$ として $O(N \log N + N \log X)$

公式解説

躓いた点

• 最大値と最小値だけ持っておけばいいということに気付かなかった