AtCoder ARC071C: 井井井 / ###

解を式で表してそれを簡単にする

(右端)-(左端)　の長さの重複を認めた集合をW,

(上端)-(下端)　の長さの重複を認めた集合をH,

とすると解は

Σw*h (w∈W, h∈H)

で表せる。

これにはよくある式変形により

Σw*h (w∈W, h∈W)

=Σw(w∈W) * Σh(h∈H)

たとえば

w0*h0+w0*h1+w1*h0+w1*h1

= (w0+w1)*(h0+h1)

のようになる。

辺の長さの和が求まれば解は求まりそう。問題は簡単になった。

辺の長さの和を求める

左右(x座標)について解ければ上下については同様。以下、左右についてのみ考える。

長さの和を求める

→ある縦の線分とその右隣の縦の線分の間の横の辺の使われる回数は？それと長さの積を出して和を取る。

要するに、縦棒で仕切られた横棒たちが何回使われるかを考えればいい。ある1個の横棒に注目する。この横棒の左にl個横棒があるとする。このとき、注目している横棒は0~l個分左に伸ばせる。同様に横棒が右にr個あるなら、0~r個分右に伸ばせる。よって、(l+1)*(r+1)個この横棒を使った辺がある。辺の長さを掛けて和を取ったものが辺の長さの和であった。これにより解は求まった。

Atcoder ARC E: TrBBnsformBBtion

部分文字列の文字の順序は関係ない

つまり、部分文字列は任意の順序に並び替えることができる。

隣接する異なる2文字を入れ替えられることを示す。

AB

→BBB

→BBAA

→BBBBA

→BA

したがって、任意の隣接する2文字は入れ替えられる。なのでバブルソートの要領で任意の順位並び替えることができる。したがって、部分文字列の順序は関係ない。そのため、以下はA,Bの個数だけ考える。

A,Bの個数はmod 3で考えればいい。

"AAA"→""

"BBB"→""

のような操作が可能であった。実は空でない文字列について逆の操作が可能。

空でない文字列に対して""→"AAA"の操作が常にできることを示す。

(1)Aが少なくとも1個ある場合

1個のAに着目して

A

→BB

→AAB

→AAAA

よって

A""→A"AAA"

(2)Aが1個もない場合

文字列は空でないと仮定したので少なくとも1個のBがある。

1個のBに着目して

B

→AA

→BBA

→BAAA

よって

B""→B"AAA"

以上からAとBの個数はともに3個単位で任意の増減ができる。したがって、mod 3でA,Bの個数を数えれば良い。

これで全点対最短経路問題になる

事前にA,Bの部分和を計算しておく。

(Aの個数mod 3, Bの個数mod 3)

のような頂点を持ち、状態遷移を有向辺としたグラフを考える。

各クエリは、ある頂点uからvへ到達できるかということになる。

頂点数はたかだか9個なのでワーシャルフロイド法を使えばおしまい。

yukicoder #503: 配列コレクション

操作回数をa, 最後に残る要素の数をbとする。
N>=Kよりa>=1
K>=2よりb>=1

最終的にAの各要素はDの累乗になることがわかる。
D=1のとき、コーナーケースでAのすべての要素は1になるので解は
b

以下、D≠1とする。
Aの要素はDの累乗であり、かつ操作回数がaなので、取りうる値は
1,D,D^2,...,D^a
のいずれかである。

ここでD^aまでというのをきちんと説明する。
操作はa回である。操作1回で掛けられるDは1個だけ増える。というのはB[i]=D^tとして、このt回分は以前の
操作の分であるため。よって、全体でDがa回掛けられていることがわかる。また、このa個は1箇所に集めることができる。すなわち必ずD^aを作れる。更に、それは任意の箇所で可能。

D^k (0<=k<=a)　について考える。
D^aにかぎらず、D^kは任意の箇所に作れる。
D^kをすべて数えてみよう。

そうすれば解はΣ(D^k*(D^kの出現回数))で求まる。
D^kは任意の箇所に作れるのでその場所はb通り。
その1通りに対して、数列の残りの部分を決めていく。
残りはb-1箇所であった。
更に、残りa-k個のDをb-1箇所のいずれかに掛けて行く必要がある。
つまり、b-1箇所から重複を許してa-k個を選ぶ事になり、これは単に
H(b-1, a-k)
で求まる。
したがって、解は
Σ(D^k * b * H(b-1, a-k))
である。

実は今のところにコーナーケースがある。
残りb-1箇所からa-k個を重複を許して選ぶと言った。ところが、b-1=0の場合はH(b-1,a-k)の計算がうまくできない。
なのでb=1がコーナーケースになる。
式で見れば
H(b-1,a-k)
=C(a+k+b-2,a-k)
a-k+b-2<a-kとすると
b-2<0
b<2
b>=1より
b=1
b=1というのは配列がただ1個の要素しか持たないので解は
D^k

Codeforces #406 (Div. 1) B: Legacy

解法

セグメント木の上でダイクストラ

セグメント木にある各頂点でダイクストラする。
もう少しきちんと説明する。
まず、
操作2について考えてみる
v->[l, r]
であった。
[l, r]は、セグメント木のいくつかの対応する頂点に分解できる。(図1)
この頂点はたかだかlog(n)個。
あるセグメントxへ移動できるならば、その子孫のセグメントへも移動できる。
セグメントxの表す範囲をs(x)のように表すと
s(y)⊆s(x)であるようなすべてのセグメントyへ移動できる。(図2)
なので、すべてのセグメント木上の頂点について、あらかじめ親から子へコスト0の辺を張っておく。
あとは操作2ごとに、v->セグメントxへコストwの辺を張る。

操作3について考えてみる
[l,r]->v
であった。
先と同様に[l,r]をいくつかのセグメントに分解できる。
その一つをセグメントxとしたとき、
s(y)⊆s(x)であるようなすべてのセグメントからvへ移動できるはず。
なので、先とは逆にあらかじめ子から親へコスト0の辺を張っておき、(図3)
あとは操作3ごとに、セグメントx->vへコストwの辺を張る。

操作1は操作2,操作3の1種なので解けている。

ただ、操作2と操作3は一緒に処理しようとするとうまくいかない。
操作2の準備として親から子へコスト0の辺を張った。また操作
3の準備として子から親へコスト0の辺を張った。
これでは任意の親子間でコスト0の双方向の辺があることになり、任意の頂点間の距離が0となってしまい
うまくいかない。

ここで一工夫する。
セグメント木を2個作って行き来させる。2個のセグメント木をそれぞれS,Tとする。
Sは子から親へのコスト0の辺を持ち(図2)、Tは親から子へのコスト0の辺を持つ(図3)。
操作2,3の辺を張るのはいずれもS->Tとセグメント木を横断するようにする。
またTの任意の頂点から、Sの対応する頂点へコスト0の辺を張る。(図4)

わかりづらいので、このグラフの意図を。
Sのグラフ上の頂点は、その頂点から移動できるようになるまでのコストを持ち、
Tのグラフ上の頂点は、ある操作によってその頂点に到達するまでのコストを持つ。
セグメントx「へ」移動できるならセグメントx「から」移動できるはず。だから、コスト0の辺をTからSへ張ったのだった。

あとは、このグラフでダイクストラするだけ。

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から始まる)

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