2017-03-12

CF 740 D - Alyona and a tree

Codeforces programming

問題

Problem - D - Codeforces

問題概要

頂点数 $n$ の木があり、各頂点には $1$ から $n$ までの番号が振られている。根の頂点番号は $1$ である。各頂点はそれぞれ整数 $a_i$ を持っている。

また、辺には重みがあり、 $n-1$ 本の辺の情報について、 $i$ 個目の情報は頂点 $i+1$ と $p_i$ を結んでおり、その重みは $w_i$ である。

いま、頂点 $v$ が頂点 $u( \neq v)$ をcontrolしているということを次のように定義する：

頂点 $u$ は $v$ を根とする部分木に含まれる
$dist(u,v) \le a_u$

各頂点 $i$ に対して、その頂点がcontrolしている頂点の個数を求めよ。

$1 \le n \le 200000$
$1 \le a_i \le 10^9$
$1 \le p_i \le n$
$1 \le w_i \le 10^9$

アイデア

controlの条件に関して、 $u$ と $v$ の距離で定義されているが、今回のグラフは木なので任意の頂点間の距離は根からの距離を利用することで計算できる。根からの各頂点への距離を $d_i$ とすると、controlの定義から $u$ は $v$ よりも根から離れていることになるので2番目の条件は $d_u - d_v \le a_u$ となり、更に変数を揃えるために変形すると $d_u - a_u \le d_v$ ということになる。

さて、ここで $u$ を固定して考えてみる。 $v$ としてあり得るのは根からの $u$ へのパス上にある頂点ということになる。根をスタート地点として $d_v$ は単調増加するので、初めて条件を満たす位置 $x$ から $u$ の手前までの区間がこの条件を満たすのでこの区間に+1すればいいということになる。

まず、初めて条件を満たす位置 $x$ を探すためには、各頂点からの親をダブリングして保存しておけば二分探索によって探すことが可能になる。

そして、このような区間へのaddはimos法で $u$ の親の頂点に+1, $x$ の親の頂点に-1をしておいて最後に子から親へ足し上げれば答えを出すことが出来る。

実装(C++)

2017-03-08

CF 738 F - Financiers Game

Codeforces programming

問題

Problem - F - Codeforces

問題概要

長さ $n$ の数列 $a$ が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。

ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分のスコアとすることが出来る。次にRさんのターンとなる。Rさんは数列の右端からスタートする。この時、その前の段階でLさんが数列から取った個数が $k$ 個である時に、Rさんは $k$ 個または $k+1$ 個の値を数列の右端から順に取ることが出来る。

以下、交互に繰り返す。パスは出来ない。数列の値が取り尽くされるか、これ以上選べない状況になってしまったらそこでゲームを終了する。

D = (Lさんの合計スコア) - (Rさんの合計スコア)とすると、LさんはDを最大化するように、RさんはDを最小化するように最適に行動する時、Dの値を求めよ。

$1 \le n \le 4000$
$-10^5 \le a_i \le 10^5$

アイデア

DPで解くことを考えてみる。すると、必要な情報は数列の左端 $l$ 、右端 $r$ 、直前のターンで相手が取った個数 $k$ 、今どちらのターンかの4つになると考えられる。

ここで、今Lさんのターンで、上のような状況でのDを $L_{l,r,k}$ 、Rさんのターンで同様の状況でのDを $R_{l,r,k}$ とすると、それぞれは次のような遷移で更新していくことが可能になる：

$L_{l,r,k} = max( R_{l+k,r,k} + \sum_{i=l}^{l+k-1} a_i , R_{l+k+1,r,k+1} + \sum_{i=l}^{l+k} a_i )$ $R_{l,r,k} = min( L_{l,r-k,k} - \sum_{i=r-k+1}^{r} a_i , L_{l,r-k-1,k+1} - \sum_{i=r-k}^{r} a_i )$

これらを計算することで答え $D = L_{1,n,1}$ となる。このDPの計算量は見た目上 $O(n^3)$ に見えるが、実際そうではないことを確かめる。

まず $k$ に注目すると、 $k$ に到達するために最低でも $1+2+ \cdots +k = \frac{k(k+1)}{2}$ 個の値が既に数列から取られている状況であることを考えると、 $\frac{k(k+1)}{2} \le n$ という条件が成り立ち、 $k$ は $\sqrt{2n}$ 以下となることが確定する。

更に、LさんとRさんが取る値の個数の差 $d(=(n-r)-(l-1))$ に注目する。最も差が大きくなるような状況は、一方が前者と同じだけ、もう片方が+1になるような選び方をし続けるような状況だが、これを考慮すると $|d| \le k$ となることが分かる。 $d$ の定義より、 $r = n-d-l+1$ となるので、上で触れたDPを $l,d,k$ の3つの変数の形に変えることによって、 $O(n^2)$ で実現することが可能になる。