読者です 読者をやめる 読者になる 読者になる

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へ張ったのだった。

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

f:id:parukii:20170324141410j:plain

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

再帰 DP

解法

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

全域木 DFS 連結グラフ

解法

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

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

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

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

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

のようになる。

このとき、順番が隣り合う場合は必ず2頂点はある辺で結ばれていることがわかる。よって、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の子として色を塗れる。

思いつき方

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

f:id:parukii:20170306111411j:plain

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

Implication graph 強連結成分分解

解法

各チームについて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

思いつき方

知識