Codeforces Round 694

スポンサーリンク

A. Strange Birthday Party

$k_i$ が大きい方から順に貪欲に決めてよいことが分かります.

B. Strange Definition

$a_i=b_i^2c_i$ で $c_i$ が square free とすると,adjacent というのは $c$ が等しいことです.平方数倍は無視できて,入力はすべて square free としてよいです.

操作も,操作後になるべく平方数で割ってしまって考えます.すると,偶数個あるものは $1$ に,奇数個あるものは自分自身になることが分かります.

C. Strange Shuffle

適当解法で通しました.答の候補を持っておき,ランダムに質問するたびに整合性のとれない候補を消していきます.後半で必ず答の候補が減るような質問を優先するようにしたら通りました.

D. Strange Housing

連結ならば可能であることが示せます.帰納法で示すことにします.$G-v$ が連結であるような $v$ をとります(全域木の葉など).$G-v$ がを条件を満たすようにした上で $v$ を適切な方にすれば条件を満たすことを確かめられます.あとはこの証明から適当な構築をすればよいです.

E. Strange Permutation

普通に気合実装という感じ.

例えば「$i$ 番目から先で,コスト $j$ 以下使えるとしたときの,$i$ 番目が $k$ であるような順列の個数」を数えます.これは後ろから順に dp すれば数えられます.先頭の文字に対する操作は長さ $5$ 以下の subarray の reverse に限られることに注意します.

これができると,辞書順何番目というのも手前から決めていけば $O(N)$ 時間で求められます.このときの計算を高速化します.

もとの $p_i$ をそのまま採用するのを基本として,そうでないものを例外とすると,例外を選ぶときにはコストを使っているので,例外は高々 $4$ 回しか発生しません.よって最初に例外が発生する位置を取得することを $4$ 回行えばだいたい全体の計算ができます.例外が発生する位置の条件を整理すると,静的な列に対する二分探索だけがあればよいことが分かります.

F. Strange Covering

bounding box の状況で場合分けします.

bounding box のうち 3 辺以上の点をひとつの長方形でとる場合を考えると,これは「左 $m$ 点と右 $n-m$ 点」,またはその上下版という形です.これは簡単です.

残りは,それぞれが bounding box 上の点を $2$ つずつとる場合で,これは $2$ パターンあります.

「左端・右端」と「上端・下端」をとる場合を考えます.左端の位置を $l$,右端の位置を $r$ とすれば,面積は $l,r$ の関数になります.左に余る点の $y$ 座標の最小・最大や右に余る点の $y$ 座標の最小・最大などがそれぞれ $l,r$ から決まり,コストは $(x_r-x_l)Y+(\max(a_l,b_r)-\min(c_l,d_r))X$ のような形になります.さらに $r$ を止めて,$a_l,b_r$ や $c_l,d_r$ の大小関係を考えると,$a$ や $c$ に単調性があることから,区間ごとに $\min,\max$ を外せます.整理すると,区間 min クエリがあれば出来ることが分かります.

残りは bounding box のうち隣接する $2$ 辺ずつをとる場合です.回転と平行移動により,座標はすべて非負でひとつの長方形が $(0,0)$ から始まるとしてよいです.

座圧して,ひとつめを $[0,0]\times [x_i,y_j]$ でとったときのコストを考えます.$x_i$ より右または $y_j$ より上にある点の座標の $\min$ からもうひとつの長方形の大きさが決まります.

今度は $x_iy_j + \max(a_i,b_j)\times \max(c_i,d_j)$ のような式になります.また単調性はあって,$j$ を止めたときの計算を考えると区間ごとに $\max$ を外すことができます.

最後に残るのは $x_iy_j + c_ib_j$ を最小化($i$ は区間内)というタイプの計算です.$(x_i,c_i)$ という点群があって,それらに対する $(y_j,b_j)$ との内積の最小値という形なので,凸多角形に対する min dot のクエリです.

$i$ が区間なので,セグメント木を作りノードごとに凸多角形を作って対処しました($O(N\log^2)$ 時間).区間がスライドであることを考えれば,swag の要領で incremental な cht を持つなどすれば $O(N\log N)$ 時間になると思います.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました