yukicoder #492: とても長い数列と文字列(Long Long Sequence and a String）

解法

f(n)を文字列にしたものをS(n)とする。
|S(n)| = 2|S(n)| + (n^2の桁数)
更に|S(4)| = 16 = 2^4
なので
|S(60)|>2^60 が成り立つ。
よってR<|S(60)|であり、K>60の場合は、K=60と見なしてよい。
以下、1<=K<=60とする。
f(n)の各桁の値d(0~9)の出現数を
cnt[n][d]
とする。
これは簡単なDPで求められる。
cnt[n][d] = cnt[n-1][d]*2 + (n^2のなかでのdの出現数)

g(r)をL=1,R=rとしたとき(つまり(0,r])の解を順序対として返す関数とする。
つまり(和,積)を(0, r]について返す。ただし、g(0)は(0, 1)を返す。
この関数が書ければg(R)とg(L-1)によって、
求めたい和は差により、求めたい積は素数10^9+7を法とした除算により、求まる。

g(r)の中身を考えてみよう。
g(0)=(0,1)
であった。

r!=0の場合を考える。
|S(n)|<=rを満たす最大のnをkとする。
(1)|S(k)| = rのとき
ちょうどf(k)の文字化したものを見ればよい。
cnt[k]はすでに求まっているから
和は Σ(x*cnt[k][x])
積は Π(pow(x, cnt[k][x]))
のように求まる。
(2)|S(k)|<rのとき
(1)の計算をしてから、r' = r-|S(k)|とおく。
(2-1) r'<=(k+1)^2の桁数のとき
(k+1)^2の上位r'桁も計算に加える。
(2-2) r'>(k+1)^2のとき
(2-1)の計算をした上で
r'' = r'-( (k+1)^2の桁数 ) として
g(r'')を解いて計算に加える。
2*r''<=rが成り立つからgの再帰の深さはせいぜいlog(r)

べき乗がボトルネックになり、実行時間は

O( (log(R))^2 )

思いつき方

文字列の長さが2倍以上に増えていくことに気づく。

=>f(60)まで

SRM 710 DIV1 Easy: ReverseMancala

解法

入力例(0)、(1)からわかるように、Bの操作の逆はAの操作で、Aの操作の逆はBの操作で表せる。
なのでstartとtargetの両方にAの操作を適用してある状態(かりにSとおく)にできればよい。
つまり
start->(Aの繰り返し)->S
かつ
target->(Aの繰り返し)->S
となるような状態Sがあれば、
start->(Aの繰り返し)->S->(Aの逆/Bの繰り返し)->target
のように解を作れる。
startとtargetは和が等しい配列で、その和をtとする。
S={t, 0, 0, ..., 0}
のような状態ならば操作Aの繰り返しで必ず構成できる。
S[0]<tとすると、i!=0でかつS[i]>0であるような添字iがある。
iに操作Aを適用したとき、(i+1) mod n へ少なくとも1個の要素が移される。
このように
i,i+1,...,n-1
番目に対して順に操作Aをほどこすと、最終的にS[0]の値が必ず1増える。
よってS[0]がtになるまで繰り返せばよい。

思いつき方？

入力例をよく読む。同じ操作を見つける。同じ操作で挟み撃ち。必ず作れる特異な状態を考える。

Codeforces #403 (Div. 2) F: Innokenty and a Football League

解法

行列の累乗みたいなことをするには、

O(ビット数*n^3)

で間に合わない。

実はbitsetを使えば十分速度が出せる。

メモリや実行速度が十分でないbool変数を使った解法は、bitsetを使うだけで間に合う場合がある。

最大の移動回数を求めるには、

0111<1000 (2進数表記)

のように、全てのビットが立っている数よりも、それより1桁多い数のほうが必ず大きいので、2進数で貪欲に上位の桁から決めていけばよい。

P->PB->PBBP->PBBPBPPB (1)

が問題文に書かれている。

これを反転したもの

B->BP->BPPB->BPPBPBBP (2)

も考えてみる。

解が0000...0???? (2進数)の形をとるとする。

つまり、いま解の2進数表記で下から4桁目を決めようとしている。

4桁目が立つならばそのルートは

PBBPBPPBから始まる。

そうでない場合を考えると、

ルートは空であるかP,PB,PBBPのいずれかから始まる。

よって、1桁ずれた部分問題

(??? (2進数), PBBP)

が得られた。

次にPBBPBPPBから始まる場合、つまり解が

0000...01??? (2進数)

の形をとる場合、

PBBPBPPBを反転したものはBPPBPBBPであり、

ルートの続きは空、B,BP,BPPBのいずれかとなる。

問題

(??? (2進数), BPPB)

が得られた。

これは(2)が(1)を反転したものであることから、(??? (2進数), PBBP)と同様に解ける。

思いつき方？

P=>PB=>PBBPを作るのに、B=>BP=>BPPB=>...を使うことに気づく。

適切に問題を表す

ここでは(d桁目以下が未定、P/Bから始まる)

反転から、似たような小さい問題に持っていけることに気づく。

Codeforces #403(Div. 2) E: Underground Lab

解法

k人のクローンがいてそれぞれceil(2n/k)個の頂点を訪れることができるので、訪れることができる頂点の数の合計Sは

S = ceil(2n/k)*k >= 2n

与えられたグラフは連結グラフなので全域木が存在する。与えられたグラフのある全域木Tについて考える。

TでDFSした時、頂点を見る順番は

頂点v(初めて訪れた)=>頂点vの子w=>...=>頂点v(wから戻ってきた)

のようになる。

このとき、順番が隣り合う場合は必ず２頂点はある辺で結ばれていることがわかる。よって、DFSの探索順で頂点を訪れればすべての頂点を訪れることができる。この頂点の探索順を配列Aで表すとする。

|A|<=S

であれば、Aの順に頂点を訪れていけばよい。

全域木の辺の数は

n-1であり、各辺は2回ずつ訪れてその度に訪れた頂点の数は増えていく。また最初の1頂点(根)も考慮すれば

|A| = 2(n-1)+1=2n-1

であり|A|<S

思いつき方

連結グラフ→全域木

k人が訪れることのできる頂点数の合計は?→2n

Codeforces #403 (Div. 2) C: Andryusha and Colored Balloons

解法

木の問題は、根付き木にすると見通しが立てやすくなることが多い。

根から再帰的に色を塗っていく。

ある頂点vの色をcur_col, 親の色をpar_colとする。また、部分木vのうち色が決まっているのはvだけとする。子の色を決めたい。問題文中の色を塗る条件をわかりやすく言い換えると、距離2以内の頂点の色は異なるということになる。あるvの子c[i]の色に対して、距離2以内に来る頂点ですでに色が決まっている、または一緒に色を決めなければならない頂点は以下の通り。

(1) 頂点v(cur_col)

(2) 頂点vの親(par_col)

(3) 別のvの子c[j] (i!=j)

つまり、下の図のように塗れば良い。

根の処理だけ特殊になるが、根を実際には存在しない頂点0の子とし、頂点0の色を実際には存在しない色0で塗っておけば、頂点0の子として色を塗れる。

思いつき方

根付き木にして描いてみる。

Codeforces #403 (Div. 2) D: Innokenty and a Football League

解法

各チームについてshort nameの付け方は2通りある。

また、それぞれのチームのshort nameの関係は、いくつかの包含関係で表せる。

2値変数Aが真であることをa、偽であることを¬aのように表すと

(x[1]=>x[2])∧(x[2]=>x[3])∧(x[3]=>x[1])∧(¬x[3]=>x[2])∧(¬x[1]=>¬x[2])∧(¬x[2]=>¬x[1])

のような複数の包含関係を「かつ」でつないだような論理式全体を真にするような各変数の値の割り当てはImplication graphの強連結成分分解で知ることができる。Implication graphはa=>bのような包含関係をそのまま有向辺として持つグラフのこと。各強連結成分の真偽値が等しくなるような2値の割り当てが解になる。ただし、aと¬aの連結成分が等しい場合、aと¬aの値が等しいことになり明らかに矛盾。この時は解なし。また、対偶関係も辺として加えられるので注意。

これを実際の問題に当てはめてみよう。

(1)異なるチームS,TについてSの名付け方sとTの名付け方¬tが等しい場合

チーム名の重複は許されないから

s=>t

かつ

¬t=>¬s

この2条件は対偶関係になっている。

(2)名付け方sと名付け方tが等しい場合

つまり、問題文で与えられているように

Sの名付け方が(DIN, DIB), Tの名付け方が(DIN, HOGE)

のような場合

SをDIBと名付けた場合はTはDINとは名付けられないのであった。

よって

¬s=>¬t

同様に

¬t=>¬s

これらに対偶関係を加えてまとめると

¬s<=>¬t

かつ

s<=>t

思いつき方

知識

SRM 708 DIV1 Medium: PalindromicSubseq

X[i]の値を具体的に求めていこう。

各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)もかかる。しかし、i,jを固定した場合、事前に計算をしていれば各(i,j)についてO(1)でS[i],S[j]を含むような回文を数えられる。

f[l][r]:=S[l,r)を使った空の文字列も含む回分の個数

g[l][r]

:= Sから得られる回分のうち、偶数長でかつ対になる文字がそれぞれg[0,l)とg(r,n]から得られるものの個数

とする。

l=min(i,j), r=max(i,j)+1とすれば半開区間が得られ、

[l,r)の内側だけでペアになっている回文と、両端だけでペアになっている回文を作れればよく、これは

f[l+1][r-1]*g[l][r]

で求まる。

和をとればX[i]が求まり、Y[i]も求まる。

g[l][r]の求め方は

SRM 708 DIV2 Hard: PalindromicSubseq2 - parukiのブログ

と同様。

f[l][r]はもっと簡単で

f[l][r] = f[l+1][r]+f[l][r-1]-f[l+1][r-1] + (s[l]==s[r-1]ならばf[l+1][r-1]、そうでなければ0)