Codeforces Round 1035

A. Add or XOR

初手以外は $a$ は増やしていくことになります.増やすときに安いほうのコストを使います.

B. Line Segments

$a_1\leq a_2\leq \cdots \leq a_n$ として,距離 $\max(0,a_n-(a_1+\cdots+a_{n-1}))$ 以上 $a_1+\cdots+a_n$ 以下が作れます.

C. A Good Problem

$n$ が奇数ならば $(l,l,\ldots,l)$ が明らかに解かつ辞書順最小です.

$n$ が偶数とします.制約 $1\leq l$ よりある $k$ があって,どれかの項の $k$ 番目の bit は $1$ です.一方 $(1,1,\ldots,1)$ だと成り立たないので,その桁は $0,1$ が両方登場します.さらに xor が $0$ になることから,$0,1$ がどちらも偶数個登場します.

これで $4\leq n$ が必要だと分かります.また,$K$ を $l$ の topbit としたとき,$2^K\leq l,r<2^{K+1}$ だと解なしであることも分かります.

以上からわかる必要条件のもと,$(l,l,\ldots,l,2^{K+1},2^{K+1})$ が辞書順最小解になります.$K$ 番目のビットについて上の条件を見ることで最小性が分かります.

D. Token Removing

token の削除方法ごとに列の数え上げをしようとすると次の問題になります:

  • 列 $b=(b_1,\ldots,b_n)$ のスコアの総和を求めよ.$0\leq b_i\leq i$ で,$0$ 以外の要素は distinct.スコアは $0$ でない要素の総積である.

$x=n,n-1,\ldots,1$ の順に,$x$ が $b$ に現れるかどうかを決めていくという dp をします.

$x\leq i$ であるようなインデックス $i$ のうち,未使用のインデックスのところに $x$ を書くことができます.$x=n,n-1,\ldots$ 順に処理すると,使用済のインデックスは常に $x\leq i$ を満たすため,使用可能なインデックスの個数がこれまで使用したインデックスの個数だけから決まります.

よって,$x$ および使用済インデックスの個数を状態とする $O(n^2)$ 時間の dp で解けます.

E. And Constraint

C とまあまあ似ている考察?

$a_{i-1}\cup a_i\subset b_i$ という必要条件があります.まずこのような $b_i$ として可能な最小値 $b$ を桁 dp などで求めます.

$b_j(i\neq j)$ が決まっているとして $b_i$ を最小化することを考えます.このときの候補が実は $O(\log \max a)$ 通りになるということがいえます.状況は

  • 定数 $a$ について,$a$ を部分集合にしろという条件がある.
  • さらに追加で,この bit は $0$ にしなさいという条件が来るかもしれない

という状況です.例えば

a = 01000100001
b = 01001100101

だとします.$b$ でこれまで $1$ になっている何らかの桁が $0$ になるような次の数を求めていきます.

01001100101
01001101001
01001110001
01010100001
01100100001
11000100001

のようになります.ある桁がはじめて $0$ になるような最初の候補において,そこより下位の桁が自動的に $0$ になるため,これらを候補として普通に dp すればよいです($O(N\cdot \log^2A)$ 時間).

F. Volcanic Eruptions

$0$ 回往復も許可することで何らかの辺で往復すると仮定します.往復の価値とは $2$ 点の重み和のこととします.

価値が負の往復はしないとしてよいです.これは初期位置での往復が価値が $0$ であることから示せます.やや微妙な点として,後ろの往復を削って手前の往復を増やすと途中で噴火に巻き込まれる心配がありますが,自分の移動速度と噴火の移動速度が等速なので,もともと後ろの往復が可能だったなら大丈夫です.

往復の価値はすべて非負としてよいことが分かりました.すると,往復する辺は高々ひとつであることも同様に示せます.

結局移動パターンは次のように記述できます.

  • 適当な点 $v_1$ まで最短路に沿って進む
  • 適当な辺を往復する
  • 以降は適当な点まで最短路に沿って進む.さらに細かくすると
    • 木の深さが減る方向に移動し続けて $v_2$ に到達する
    • 木の深さが増える方向に移動し続けて $v_3$ に到達する

さらに,$v_2$ の到達は,噴火に巻き込まれるギリギリの時刻としてよいです.これは手前に往復を追加することを考えればよいです(スタート地点で価値 $0$ の往復が可能であることに注意).

計算は次の手順によって行えます.

  • $v_1$ に到達する時刻,その時点での HP を計算
  • $v_2$ に到達する時刻,その時点での HP を計算(時刻は「ギリギリの時刻」で一意,HP はその時刻での最大のもの)
  • $v_3$ に到達する時刻,その時点での HP を計算(やはり $v_3$ への到達時刻も「ギリギリの時刻」)

$v_1$ に関する計算は単にシミュレーションすればよいです.

$v_2$ に対する計算は,$v_1$ を固定するごとに考えると,適当な木上二分探索をしたあと,木のパス上への chmax クエリに帰着できます.経路の途中で HP が $0$ 以下にならないことを保証する必要があることに注意.

$v_3$ に対する計算は top-down な dpによって行えます.

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