読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 740 D - Alyona and a tree

Codeforces programming

問題

Problem - D - Codeforces

問題概要

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

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

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

  • 頂点uvを根とする部分木に含まれる
  • 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の条件に関して、uvの距離で定義されているが、今回のグラフは木なので任意の頂点間の距離は根からの距離を利用することで計算できる。根からの各頂点への距離をd_iとすると、controlの定義からuvよりも根から離れていることになるので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++)

続きを読む

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)で実現することが可能になる。

このDPの計算量の落とし方はかなり面白かったし勉強になった。

実装(C++)

続きを読む

SRM 643 Div1 Easy - TheKingsFactorization

SRM programming

問題

TopCoder Statistics - Problem Statement

問題概要

自然数N素因数分解を求めよ。ただし、Nの素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。

例えば、N=60であるとき、素因数分解60 = 2 * 2 * 3 * 5であるから、小さい方から数えて奇数番目の2 , 3がヒントとして与えられる。

  •  2 \le N \le 10^{18}

イデア

普通に素因数分解するのでは、O(\sqrt{N})かかってしまうので、間に合わない。そこで、ヒントを利用する。

まず、ヒントとして与えられる素因数の個数で、全体の素因数が何個あるかの見当を付けることが出来る。例えば、ヒントが2個なら、答えには3個か4個の素因数があるはずである。

ヒントの個数が1個なら、答えに含まれる素因数の個数は1個か2個ということになる。これはヒントをみればどちらになるか簡単に判断できて、その1個がNと一致するなら素因数は1個で、そうでないならNをそのヒントで割った値も素因数になっていることが確定する。

以下、ヒントの個数が2個以上である状況を考える。まず、Nを既にわかっている素因数で割っておく。

まず、素因数分解の素朴な方法として、最初に述べた計算量からも推測がつく通りNに対する素因数分解2から\sqrt{N}までのそれぞれで割れるかどうかを試すという方法がある。それぞれの数で順番にNを割っていき、終わった時点でNが1よりも大きければその数も(\sqrt{N}より大きい)素因数であるといえる。

これだけだと間に合わないが、ここでヒントを利用する。ヒントの中で一番大きい数pに注目する。すると、ヒントの与えられ方の性質から、p以上の素因数は多くとも1つしかないことが分かる。よって、Nを試し割りするのはこのp以下で十分である事がわかる。

pがとても大きい数だったらこの制約は意味がないじゃないかと思うかもしれないが、直感的にはpが大きいような状況では、既にNpで割られているので\sqrt{N}が十分小さくなるというイメージで計算が間に合う。

最悪の状況を考えてみると、実際に素因数が3個である状況を考え、与えられるヒントが2とpだったとする。この時に、2つの制約\sqrt{N}pがちょうど拮抗する状況を考えても、N \le 10^{18}であるから試し割りの範囲は最悪でも10^6くらいに収まることが分かる。

とても面白い問題だった。

実装(C++)

続きを読む