2016-12-15

ARC 064 F - Rotated Palindromes

AtCoder programming

問題

F: Rotated Palindromes - AtCoder Regular Contest 064 | AtCoder

問題概要

長さ $N$ の数列 $a$ としてあり得るものを全て用意する。ただし、 $a$ は

$1 \le a_i \le K$
$a$ は回文(つまり $a$ と $a$ の逆順に並べたものは一致)

という条件を満たす。このようにして得られた $a$ に対して、「先頭の要素を末尾へ移動する」という操作を好きな回数行う。

これによって得られる最終的な $a$ としてあり得るものが何通りあるかを $mod 10^9 + 7$ で答えよ。

$1 \le N \le 10^9$
$1 \le K \le 10^9$

アイデア

例えば、数列の構成が長さ6で、abccbaのような数列だったとする。このときは、cyclic shiftにより構成される数列の種類は順に見ていくと

abccba (回文)
bccbaa
ccbaab
cbaabc (回文)
baabcc
aabccb

のようになっている。しかしながら、abababのような数列を考えるとabababとbababaの2種類しか現れないことがわかる。

このように数列内の最小周期によってその数列から生成される組み合わせの個数というのが変わってくる。そこで、この周期を全探索して、その結果を足し合わせることで全体を求めるということを考える。ただし、この全探索をする時は、「最短」周期を全探索するということを心に留めておく。

周期を全探索にするにあたって、この周期が $N$ の約数であることは明らか。この制約なら $N$ の約数の個数は多くても1500個程度であることがわかっているので、全探索できる。

さて、今周期を $d$ で固定する。さて、 $a$ を全体で見て回文になっているのだから、この周期 $d$ の数列も回文になっていなければおかしい(更にその周期 $d$ の数列の中に $d$ 未満の周期が存在していてはいけない)。さて、このことから、最低周期を $d$ に持つ数列 $a$ として最初に設定できるものの個数を $dp_d$ とすると、次の式が成り立つ:

$\displaystyle dp_d = K^{\lceil \frac{d}{2} \rceil} - \sum_{i \lt d , \ d\% i = 0} dp_i$

回文なので、前半を自由に設定できるとして、ただしそこからそれ未満の周期が出来ている個数を引かなければいけないという式の形になっている。このしきにより、約数の個数の2乗のオーダーでこのDPを計算できる。

それができたら、個別に周期 $d$ がある回文に対して、cyclic shiftした時に何種類の数列が生成されるかを掛け合わせたものを足し合わせることで最終的な答えが求められる。そこで、 $d$ の偶奇によって生成される種類が変わってくる。まず、 $d$ が奇数ならその時は中心の数の位置によって $d$ 個全てが違うものであると区別がつくのでそのまま $d$ 個になる。ただし、 $d$ が偶数なら上でも見たようにcyclic shiftの途中でもう一度回文が出ていることになり、同じものを2回カウントしている事になっている。よってこの時は $d/2$ 個がshiftによって生成されることになる。

実装(C++)

2016-12-13

CF 733 E - Sleep in Class

Codeforces programming

問題

Problem - E - Codeforces

問題概要

$n$ 段の階段がある。各段は、下から順に番号が $1$ から $n$ まで付けられており、その各段にはupかdownかのどちらかが書かれており、その段にいるときに進む方向を示している。そして、そこから移動した瞬間に、その段の示す方向は反転する。

さて、次のような動作を考える：はじめに、あなたは $i$ 段目の位置にいて、1秒に1回の移動を行う。そして、1段目にいるときにdownするか $n$ 段目にいるときにupすると階段から落ちる。落ちるのにも1秒かかるとしたとき、落ちるまでにかかる時間を各 $i(1 \le i \le n)$ について求めよ。いつまでも落ちることのない場合は、-1と答えよ。

$1 \le n \le 10^6$

アイデア

UとDの区間が交互に連続していると考えるとその区間はどんどんマージされていくので1つの立ち位置だけなら、シミュレーションにより $O(n)$ で解けるように感じるが、今回はそれを全スタート位置についてやらなければいけないのでそれは厳しい。

あるスタート地点に立った時のことを考えてみると、そこから何回折り返しが発生するかというのはスタート位置よりも上にあるDと下にあるUの個数に依存してくることに気づく。

ということで、先頭からのUの個数を累積和として配列 $ku$ に保存し、末尾からのDの個数を累積和として $kd$ に記録することにする(この累積和に関して、自分自身のマスは考慮しないことにして、それぞれ自分より小さい範囲、自分より大きい範囲の位置を考える)。

次に、次のような配列 $tl$ と $tr$ を考えてみる：

$tl_i$ : $s_i$ が常にDで不変であると仮定したときに位置 $i$ からスタートして脱出までにかかる時間
$tr_i$ : $s_i$ が常にUで不変であると仮定したときに位置 $i$ からスタートして脱出までにかかる時間

$tl$ の方に注目してみると、まず $tl_1 = 1$ は明らか。そして、 $i$ と $i+1$ の関係を考えてみる。すると、 $tl_{i+1}$ は $tl_i$ の状況に比べてUに遭遇したときに戻ってくるのに距離が $1$ だけ伸びていることになる。これを行き帰りで考慮しなければならないので1つのUにつき時間が $2$ だけ加算される。それと、はじめの一歩を考慮して $tl_{i+1} = tl_i + 2 * ku_{i+1} +1$ という漸化式が立てられる。 $tr$ の方も同様にして、 $tr_n = 1$ で初期化し、 $tr_{i-1} = tr_i + 2 * kd_{i-1} + 1$ となる。

さて、階段の一番上の段から上に登って落ちるのか、一番下の段から下に降りて落ちるのかは、 $ku_i$ と $kd_i$ の大小関係から分かる。もしこの2つの値が等しい時には、スタート地点の方向を見れば、その方向に一致する。この関係性から落ちる方向は決まっているが、上からと下から、同時に落下すると仮定して、その合計の時間から実際には脱出出来ない方の時間の一部を引くという形でスタート位置が $i$ 段目のときにかかる時間を求めていくことにする。このような方針にすることで、上で不自然な感じに設定した $tl$ と $tr$ が活かせる( $i$ を基準位置に区切ってかかる時間を考えることが出来るようになった)。

出口の方向にもよるが、 $tl_i + tr_i$ から $tl_j$ または $tr_j$ を引くことになる( $j$ は出口とは反対方向で最終的に到達する位置)。また、ちょうど位置 $j$ にいるときに反対で脱出されるわけではないので、数合わせをする必要もあるが、まずは $j$ について考えてみる。

下から脱出するとすると、 $kd_i - ku_i - f \ge 0$ になる( $f$ は $s_i$ がUなら1、Dなら0)。反対側で、最終的に到達する位置 $j$ は、この折り返しの回数を考慮すると、配列 $posd$ にDの現れる位置を上から順に保存しておくことにすれば、 $j = posd [ kd_i - ku_i - f ]$ というということになる。 $tr_j$ を引けばよいわけだが、それだけでは足りない。余計に $i$ と $j$ の間を何回か往復していることになっているのでその分も引いて上げる必要がある。そして往復分を考えれば、ここで引くべきなのは $(2(kd_i - ku_i - f) + 1) * (j-i)$ となる。これは、のこってる分だけ往復するのが第一項で、第二項が最後は結局反対側から出ていくので1回だけしか通過しないところがあるぶんを引いている。