Codeforces #408 (Div. 2) E: Exam Cheating

dp[i][j][fs][sc]

=i番目まの問題まで確定していて、j回カンニングしている。１人目に対して直前にしたカンニングの左端はiからfs個左、2人目に対して直前にしたカンニングの左端はiからsc個左とする。ただし、fs,scはK以上はすべてKの1値で表す。このとき最大の得点。

この愚直なDPの計算量は

O(n*p*k^2)

n*p*k^2≦1000*1000*50^2 = 2.5*10^9

で間に合わない。

もっと容易に解が求まる場合を考えてみる。

2人対してすべての問題をカンニングできる場合を考える。

この場合は

p≧2*ceil(n/k)

と同値。このとき得点しうる問題はすべて得点できる。

そうでない場合は

p<2*ceil(n/k)

が成り立つ。

このとき

O(n*p*k^2)

= O(n*(n/k)*k^2)

= O(n^2 * k)

となり、間に合う。

計算量が多いのは解が自明なケースであった。解が自明なケースを場合分けで切り離して計算量を落とす。

Codeforces #408 (Div. 2) D: Police Stations

1個の町に複数の警察署がある場合もありうるが、明らかに無意味なので1個の町にはたかだか1個の警察署しか無いとする。

道路で結ばれた町は、全体で木になっている。

ある頂点が複数の警察署でカバーされているとする。そのうち最も近い頂点をu,二番目に近い頂点をvとする。グラフは木なのでu,v間の単純道はただ1個であって、その単純道には必ず複数の警察署でカバーされる頂点が存在する。なので、u,v間の単純道で真ん中あたりの辺は1個取り除くことができる。

この操作を可能な限り繰り返すと、警察署と同じ数の部分木に分割されることがわかる。ただし、各部分木はちょうど1個の警察署を含み、しかも部分木のすべての頂点はその警察署から距離d以内にある。

このような部分木に分割して取り除いた辺(使用しなかった辺)をすべて求めたい。

そのためには、すべての警察署を始点としてBFSすればいい。

Codeforces #408 (Div. 2) C: Bank Hacking

与えられた銀行の関係は木になっていることがわかる。最初にオフラインにする頂点を固定する。この頂点を根とする根付き木を考える。他の頂点をオフラインにするには、すでにオフラインの頂点と隣接していないといけないのであった。よって、親がオフラインでなければならない。親をオフラインにするのに+1だけその子の頂点の強さが増えるのであった。(neighboring)同様に、親の親が存在する頂点は、その親の親をオフラインにするときに強さが+1される。(semi-neighbouring)したがって、

頂点iをオフラインにする時、その強さは以下のようになる。

根の場合はa[i]

根の子はただ1個の親(根)をもつのでa[i]+1

それ以外の頂点は親と、さらにその親も持つのでa[i]+2

このように根を固定するとすべての頂点の強さが定まるので、根を固定したときに必要な強さはこれらの最大値。その最小値を求めればいいことがわかる。

すべての頂点の強さをとりあえずa[i]+2で初期化する。

根を総当りで固定しよう。

根の強さをa[i]に変える。

根の子の強さをa[i]+1

に変える、このとき、頂点の強さの最大値が簡単に求まればいい。

セグメント木で頂点の強さを管理すれば、O(log(n)) で値の更新と最大値取得ができる。よって、全体でO(nlog(n))の時間で間に合う。

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

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