CF 738 F - Financiers Game
問題
問題概要
長さの数列が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。
ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分のスコアとすることが出来る。次にRさんのターンとなる。Rさんは数列の右端からスタートする。この時、その前の段階でLさんが数列から取った個数が個である時に、Rさんは個または個の値を数列の右端から順に取ることが出来る。
以下、交互に繰り返す。パスは出来ない。数列の値が取り尽くされるか、これ以上選べない状況になってしまったらそこでゲームを終了する。
D = (Lさんの合計スコア) - (Rさんの合計スコア)
とすると、LさんはDを最大化するように、RさんはDを最小化するように最適に行動する時、Dの値を求めよ。
アイデア
DPで解くことを考えてみる。すると、必要な情報は数列の左端、右端、直前のターンで相手が取った個数、今どちらのターンかの4つになると考えられる。
ここで、今Lさんのターンで、上のような状況でのDを、Rさんのターンで同様の状況でのDをとすると、それぞれは次のような遷移で更新していくことが可能になる:
これらを計算することで答えとなる。このDPの計算量は見た目上に見えるが、実際そうではないことを確かめる。
まずに注目すると、に到達するために最低でも個の値が既に数列から取られている状況であることを考えると、という条件が成り立ち、は以下となることが確定する。
更に、LさんとRさんが取る値の個数の差に注目する。最も差が大きくなるような状況は、一方が前者と同じだけ、もう片方が+1になるような選び方をし続けるような状況だが、これを考慮するととなることが分かる。の定義より、となるので、上で触れたDPをの3つの変数の形に変えることによって、で実現することが可能になる。
このDPの計算量の落とし方はかなり面白かったし勉強になった。
実装(C++)
続きを読むSRM 643 Div1 Easy - TheKingsFactorization
問題
TopCoder Statistics - Problem Statement
問題概要
自然数の素因数分解を求めよ。ただし、の素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。
例えば、であるとき、素因数分解はであるから、小さい方から数えて奇数番目のがヒントとして与えられる。
アイデア
普通に素因数分解するのでは、かかってしまうので、間に合わない。そこで、ヒントを利用する。
まず、ヒントとして与えられる素因数の個数で、全体の素因数が何個あるかの見当を付けることが出来る。例えば、ヒントが2個なら、答えには3個か4個の素因数があるはずである。
ヒントの個数が1個なら、答えに含まれる素因数の個数は1個か2個ということになる。これはヒントをみればどちらになるか簡単に判断できて、その1個がと一致するなら素因数は1個で、そうでないならをそのヒントで割った値も素因数になっていることが確定する。
以下、ヒントの個数が2個以上である状況を考える。まず、を既にわかっている素因数で割っておく。
まず、素因数分解の素朴な方法として、最初に述べた計算量からも推測がつく通りに対する素因数分解はからまでのそれぞれで割れるかどうかを試すという方法がある。それぞれの数で順番にを割っていき、終わった時点でが1よりも大きければその数も(より大きい)素因数であるといえる。
これだけだと間に合わないが、ここでヒントを利用する。ヒントの中で一番大きい数に注目する。すると、ヒントの与えられ方の性質から、以上の素因数は多くとも1つしかないことが分かる。よって、を試し割りするのはこの以下で十分である事がわかる。
がとても大きい数だったらこの制約は意味がないじゃないかと思うかもしれないが、直感的にはが大きいような状況では、既にがで割られているのでが十分小さくなるというイメージで計算が間に合う。
最悪の状況を考えてみると、実際に素因数が3個である状況を考え、与えられるヒントが2とだったとする。この時に、2つの制約とがちょうど拮抗する状況を考えても、であるから試し割りの範囲は最悪でもくらいに収まることが分かる。
とても面白い問題だった。