2024-11-18

Codeforces Round 988 (Div. 3)に参加した

競プロアルゴCodeforces

Codeforces Div. 3の参加記．

11月17日に開催されたCodeforces Round 988 (Div. 3)に参加し，ABCDの4完で2304位だった．

久しぶりに出たら大失敗回になってしまって悲しい．Eを飛ばしてFに行ったら変な沼にはまった．

A - Twice

問題概要

長さ $n$ の数列 $a=(a_1,\cdots, a_n)$ が与えられる．この数列に対し， $a_i=a_j$ であるような異なる要素 $a_i, a_j\;(i < j)$ を選んで削除するという操作は最大で何回行うことができるか？

制約

$1\leq n\leq 20$
$1\leq a_i\leq n$

考えたこと

数列 $a$ の中に $a_i=x$ であるような要素がちょうど $c_x$ 個あったとすると，その要素からは $\lfloor c_x/2\rfloor$ 回の操作をすることができ，それ以上の回数の操作はできない．よって答えは

\sum_{x=1}^n c_x

である．

提出：https://codeforces.com/contest/2037/submission/291949756

B - Intercepted Inputs

問題概要

問題文

長さ $k$ の数列 $a=(a_1,\cdots,a_k)$ が与えられる．正の整数 $n, m$ であって以下の条件を満たすものをひとつ出力せよ．

ある $nm$ 個の整数と $n, m$ をある順に並べた数列が $a$ に一致する．

制約

$3\leq k\leq 2\times 10^5$
$1\leq a_i\leq k$
$a_i=n, a_j=m$ となる $i,j\,(i\neq j)$ が存在する
条件を満たす $n, m$ が存在する

考えたこと

要素数の関係から， $n, m$ と $k$ の間には $nm+2=k$ という等式が成り立つ．

$n$ の候補を全探索する． $n=a_i$ であると仮定すると， $k-2$ が $n$ の倍数ならば $m=(k-2)/n$ と決まる．よってあとは数列 $a$ （から $a_i$ を除いたもの）の中に $m$ が存在するかを調べればよい．

存在判定は $O(1)$ でできるので全体の計算量は $O(k)$ である．

提出：https://codeforces.com/contest/2037/submission/291961821

C - Superultra’s Favorite Permutation

問題概要

問題文

正の整数 $n$ が与えられる． $1,\cdots, n$ の順列 $p=(p_1,\cdots,p_n)$ であって，任意の $i=1,\cdots, n-1$ に対して $p_i+p_{i+1}$ が合成数であるものが存在するか判定し，存在するならばひとつ出力せよ．

制約

$2\leq n\leq 2\times 10^5$

考えたこと

こういうシンプルな発想力を要する問題は楽しい！

実は， $n$ が大きいとき条件を満たす順列は必ず構成できる．

まず，異なる正の奇数の和と異なる正の偶数の和はそれぞれ必ず偶数であり，しかも $2$ より大きいからこれは合成数である．よって $1,\cdots, n$ を奇数どうし，偶数どうし連続させるとよさそうである．奇数と偶数の境界が問題となるが， $4+5=9=3\times 3$ でこれは合成数だから，境界では $4, 5$ を隣接させればよい．

したがって $n\geq 5$ のときは「 $1,\cdots,n$ のうち奇数であるもの（ $5$ 以外）」， $5, 4$ ，「 $1,\cdots,n$ のうち偶数であるもの（ $4$ 以外）」を順に並べたものが条件を満たす順列になる．

$n<5$ のときは $n$ が小さいので $n!$ 通りを全探索しても間に合う．コンテスト中はこの方針で実装したが，よく考えると $n<5$ のときに条件を満たす順列が存在しないことはちょっと考察すると分かるのでその必要はなかった．

提出：https://codeforces.com/contest/2037/submission/291983215

D - Sharky Surfing

問題概要

問題文

無限に長い数直線上を，Mualaniは以下の条件を満たしながら位置 $1$ から位置 $L$ まで移動する．

はじめ，Mualaniは位置 $1$ におり，Mualaniのジャンプ力は $1$ である．
Mualaniが位置 $x$ におり，ジャンプ力が $k$ であるとき，Mualaniは $y\in [x, x+k]$ なる任意の整数 $y$ の位置へ移動することができる．
$n$ 個の閉区間 $[l_i, r_i]\;(1\leq i\leq n)$ で表される「ハードル」があり，この区間に属する座標には移動することができない．
$m$ 個の座標 $x_j\;(1\leq j\leq m)$ があり，Mualaniは位置 $x_j$ にいるときに自分のジャンプ力を $v_j$ だけ増加（パワーアップ）させることができる（しなくてもよい）．この操作は各 $j$ に対してそれぞれ $1$ 回までしか行うことはできない．

このとき，Mualaniが $0$ 回以上の移動を繰り返して位置 $L$ に到達することが可能かどうかを判定し，可能である場合はパワーアップ回数の最小値を求めよ．

制約

$1\leq n, m\leq 2\times 10^5$
$3\leq L\leq 10^9$
$1 < l_i\leq r_i < L\;(1\leq i\leq n)$
$1\leq x_j, v_j\leq L\;(1\leq j\leq m)$
任意の $1\leq i\leq n$ に対して $r_i+1 < l_{i+1}$
$x_1\leq x_2\leq \cdots\leq x_m$
$x_j\in [l_i, r_i]$ となる $1\leq i\leq n, 1\leq j\leq m$ は存在しない

考えたこと

はじめにDP方針をとって迷走してしまったが，実は貪欲に移動方法を選んでいくことができる．

まず，移動回数を最小化する必要はないから，基本的には $1$ ずつ移動するとしても損しない．しかし，ハードル上に移動することはできないから，長さ $d$ のハードルを超えるためにはその直前までにジャンプ力を $d+1$ 以上にしておく必要がある．

ここで，パワーアップが以下のような設定であるとしても答えは変わらない．

$m$ 個の座標 $x_j\;(1\leq j\leq m)$ があり，Mualaniは位置 $x\geq x_j$ にいるときに自分のジャンプ力を $v_j$ だけ増加させることができる（しなくてもよい）．この操作は各 $j$ に対してそれぞれ $1$ 回までしか行うことはできない．

このような設定のもとでは，パワーアップは必要になったタイミング（＝ハードルの直前）でまとめて行えばよい．さらに，パワーアップの選択肢が複数ある場合には，ジャンプ力の増分が最も大きいものを選ぶとしても損しない．

ここまで考えれば，以下のようなアルゴリズムによって貪欲に移動していくことができる．

現在実行可能なジャンプ力増加操作について，その増分を要素にもつような多重集合を $S$ ，Mualaniの現在位置を $x$ ，ジャンプ力を $p$ ，ジャンプ力の増加操作回数を ${\rm cnt}$ とする．
はじめ $S$ を空集合で， $x\leftarrow 1$ で初期化する．
$x_1,\cdots, x_m$ および $l_1,\cdots, l_n$ をまとめて昇順にソートし，順に以下を行う：

ジャンプ力増加位置 $x_j$ $x_{j}$ の場合：
- $S$ に $v_j$ を追加する．
ハードル $l_i$ $l_{i}$ の場合：
- $p < r_i-l_i+2$ $p < r_{i} - l_{i} + 2$ である限り以下を繰り返す．
  - $S$ が空の場合は処理を終了する（このとき位置 $L$ に到達することが不可能）．
  - そうでない場合， $S$ から最大の要素 $v_{\rm max}$ を取り出し $p\leftarrow p+v_{\rm max}$ および ${\rm cnt}\leftarrow {\rm cnt}+1$ とする．

最終的な ${\rm cnt}$ が求める最小の操作回数である．

$S$ として優先度付きキューを用いれば計算量は $O((n+m)\log (n+m))$ である．

提出：https://codeforces.com/contest/2037/submission/292010358

F - Ardent Flames

問題概要

問題文

整数 $n, m, k$ が与えられる．数直線上に $n$ 体の敵が並んでおり，敵 $i$ の位置は $x_i$ ，強さは $h_i$ である．

はじめに整数 $p$ を選び固定する．このとき，以下の操作を $0$ 回以上何回でも行うことができる．

操作：すべての敵をいっせいに攻撃する．この攻撃によって，位置 $x$ にある敵の強さは $\max (0,m-|p-x|)$ だけ減少する．

$k$ 体以上の敵の強さを $0$ 以下にすることができるかを判定し，可能な場合は必要な操作回数の最小値を求めよ．

制約

$1\leq k\leq n\leq 10^5$
$1\leq m\leq 10^9$
$1\leq x_i, h_i\leq 10^9\;(1\leq i\leq n)$
$x_1 < x_2 < \cdots < x_n$

考えたこと

二分探索まではすぐ見えたが判定関数の実装方針であらぬ方向に行ってしまい，コンテスト後にupsolveすることになった．

操作を $c$ 回行うとして，以下のような判定問題に対して二分探索を行う．

判定問題： $c$ 回の操作によって $k$ 体以上の敵の強さを $0$ 以下にすることができるか？

$c$ 回の操作によって敵 $i$ の強さが $0$ 以下になるための必要十分条件は

c\times \max (0, m-|p-x_i|)\geq h_i

である． $h_i > 0$ だから，これはさらに

c(m-|p-x_i|)\geq h_i

と同値である．これを変形すると

x_i+\frac{h_i}{c}-m\leq p\leq x_i-\frac{h_i}{c}+m

が得られる．このように，敵 $i$ の強さを $0$ 以下にすることのできる $p$ の範囲はある区間をなす．なお， $p$ は整数だから，上の区間は

x_i+\left\lceil\frac{h_i}{c}\right\rceil-m\leq p\leq x_i-\left\lceil\frac{h_i}{c}\right\rceil+m

としても同じことである．

よって，あとは以下の部分問題が解ければよい．

部分問題： $n$ 個の閉区間 $[l_i, r_i]\;(1\leq i\leq n)$ が与えられる．整数 $p$ を含むような区間が $k$ 個以上存在するような $p$ は存在するか？

これは，区間の座標を昇順にソートして区間の重なり数をシミュレーションすることで $O(n\log n)$ で判定可能である．

したがって，二分探索の上限を $c_{\rm max}$ としてもとの問題を $O(n\log n\log c_{\rm max})$ で解くことができた．

提出（コンテスト後）：https://codeforces.com/contest/2037/submission/292119997