2017-03-08

CF 738 F - Financiers Game

問題

問題概要

長さ $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++)

2017-02-13

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$ が大きいような状況では、既に $N$ が $p$ で割られているので $\sqrt{N}$ が十分小さくなるというイメージで計算が間に合う。

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

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

実装(C++)

裏紙

ほぼ競プロ、たまに日記

CF 738 F - Financiers Game

問題

問題概要

アイデア

実装(C++)

SRM 643 Div1 Easy - TheKingsFactorization

問題

問題概要

アイデア

実装(C++)