2020-02-19

JAG夏合宿Day3-G(AOJ2994): Toss Cut Tree

こういうやつの定跡を知っているかが重要そう。

問題

onlinejudge.u-aizu.ac.jp

解法

　木から頂点を取り除いていくので、森を扱うことになる。森の連結成分の数は、頂点の数から辺の数を引いたものである。これは期待値にしても変わらず(期待値の線形性)、 $(頂点の期待値)-(辺数の期待値)$ を考えてよい。森 $T$ の最終的な頂点数、辺数に対応する確率変数をそれぞれ $v _ T , e _ T$ とし、 $U$ についても同様に定義すれば、求めるべき値は以下のように書ける。

$E[XY] = E[(v _ T - e _ T)(v _ U - e _ U)] = E[v _ T v _ U] - E[v _ T e _ U] - E[e _ T v _ U] + E[e _ T e _ U]$

この各項を計算していこう。

$E[v _ T v _ U$ ]

　 $T$ の頂点 $i$ に対し、最終的に $i$ が残れば1、消えていれば0を取るような確率変数を $X _ i$ とする。また、 $U$ の頂点 $j$ に対し、最終的に $j$ が残れば1、消えていれば0を取るような確率変数を $Y _ j$ とする。このとき、期待値の線形性から、以下のような計算ができる。

$E[v _ T v _ U] = E\left[\left(\sum _ {i=1} ^ {N} X _ i \right) \left(\sum _ {j=1} ^ {N} Y _ j \right)\right] = \sum _ {i,j} E[X _ i Y _ j]$

ここで、 $E[X _ i Y _ j$ ]は $i \neq j$ のとき $\frac {1} {4}$ で、そうでないとき $0$ である。 $i \neq j$ となる $(i,j)$ の組は $N*(N-1)$ 個あるから

$E[v _ T v _ U] = \frac{1}{4}N(N-1)$

がわかった。

$E[e _ T v _ U$ ]

　上の議論がわかれば、実はほとんと同じである。辺 $(a _ i, b _ i)$ が残るには、頂点 $a _ i, b _ i$ がどちらも残る必要がある。従って期待値の線形性より以下の等式が成り立つ。

$E[e _ T v _ U] = \sum _ {i,j} E[X _ {a _ i} X _ {b _ i} Y _ {j}]$

$E[X _ {a _ i} X _ {b _ i} Y _ {j}$ ]は $(a _ i, b _ i, j)$ がすべて異なるとき $\frac{1}{8}$ で、それ以外のとき $0$ である。よって、 $(a _ i, b _ i, j)$ がすべて異なるような $(i,j)$ の組を数えればよく、これは $T$ の各頂点の次数を持っておくことで可能である。

$E[v _ T e _ U$ ]

　これは $E[e _ T v _ U$ ]と同様なので省略。

$E[e _ T e _ U$ ]

　もはやこれも説明不要かもしれない。今までと同様に以下の等式が成り立つ。

$E[e _ T e _ U] = \sum _ {i,j} E[X _ {a _ i} X _ {b _ i} Y _ {c _ j} Y _ {d _ j}]$

$E[X _ {a _ i} X _ {b _ i} Y _ {c _ j} Y _ {d _ j}$ ]は、 $a _ i, b _ i,c _ j,d _ j$ がすべて異なれば $\frac{1}{16}$ 、そうでなければ $0$ である。 $a _ i, b _ i,c _ j,d _ j$ がすべて異なるような $(i,j)$ の組の数は、 $T,U$ の各頂点の次数を見れば計算できる。

上で述べた計算すべき値はすべて $O(N)$ で計算可能なので、この問題が $O(N)$ で解けた。

実装

特に難しいところはない。

onlinejudge.u-aizu.ac.jp

2020-02-03

Codeforces#616-div1-C: Prefix Enlightenment

これが解けないのは悔しいんだけど、まあ難しいね...。

問題

codeforces.com

考察と解法

　まず、どの3つのスイッチを取っても、その3つに関わるランプは存在しないという条件に注目する。これは、各ランプについて、押すと影響のあるスイッチは高々2つしかないことを言っている。そうなると、ランプを辺、スイッチを頂点としたグラフを考えたくなる。とりあえず、すべての辺が2つの頂点を結んでいる場合を考えよう。
　このグラフの頂点(スイッチ)に黒か白の色を塗ることを考えよう。最初はすべての頂点は白色で、これはスイッチがoffであることを表す。黒色に塗ると、これはスイッチがonであることを表す。このように考えると、辺(ランプ) $i$ について、そのランプが点灯しているときは、以下の制約を満たす必要がある。

$S_i = 0$ のとき、辺の両端の色は異なる
$S_i = 1$ のとき、辺の両端の色は同じ

この制約を満たすように色を塗るとき、黒色の頂点を最小で何個塗ればよいかということを答えよというのがこの問題の要求となる。
　さて、すべての頂点が白い状態から、番号が $i$ 以下の辺が制約を満たすように黒く頂点を塗っていくことを考えよう。ある頂点 $v$ を黒色に塗ることにすると、そのスイッチを繋ぐ辺のうち番号が $i$ 以下の辺があれば、上の制約より、辺が繋ぐのもう一方の頂点の色が決定することになる。この決定は連鎖するので、 $i$ 以下の辺でつながれた連結成分ごとに状態が決まっていくことになる。頂点 $v$ を塗らないことにしても、連鎖は同様にしておこる。つまり、取り得る状態は連結成分について高々2つしかなく、このうち黒い頂点の数が少ない方がわかればよいことになる。この計算が高速に行えればよい。
　制約の要となるグラフの辺をどんどん増やしていきながらクエリに答える問題なので、Union-Findを使った解法を考えるのは不自然ではないだろう。ここでは、頂点を倍加するテクニックを用いる。つまり、グラフの頂点として、( $v$ ,白)と( $v$ ,黒)という $2K$ 個の頂点を用意し、最初は辺が1本もない状態からスタートする。また、頂点を黒く塗ることにはコストがかかるので、( $v$ ,黒)に重み1を載せておく。辺 $i$ を追加するとき(頂点 $u,v$ を結んでいるとする)は、次のような併合操作を行う。

$S_i = 0$ のとき、( $u$ ,白),( $v$ ,黒)を併合して、( $u$ ,黒),( $v$ ,白)を併合する
$S_i = 1$ のとき、( $u$ ,白),( $v$ ,白)を併合して、( $u$ ,黒),( $v$ ,黒)を併合する

併合のときに、連結成分内の重みの総和も更新する。すると、辺 $(u,v)$ の属する連結成分の答えは、( $u$ ,白)が属する連結成分の重みと、( $u$ ,黒)が属する連結成分の重みであることがわかる。両者は同じ連結成分に属することはない。今回は問題の入力として必ず条件を満たすスイッチの押し方が存在することが保証されているので、矛盾が生じる(前述したように、あるスイッチの状態を決定した後に、状態の決定が連鎖していく中で黒かつ白である必要のある頂点が現れること)ことがないからである。この処理を辺1から順に行い、答えを適宜更新してくことでこの問題が解ける(実装の項参照)。
　ある辺が1つの頂点としか結ばれていないときの扱いは、あらたにスイッチ $X$ を用意し、( $X$ ,白)と( $X$ ,黒)という頂点を用意して同様の処理を行うことにする。ここで、( $X$ ,黒)のコストを5000兆などの十分大きい数にしておけば、 $X$ が黒く塗られるようなスイッチの押し方が最適解となることがなくなるのでうまくいく(結局、 $2K+2$ 個の頂点を用意することになる)。

実装

　辺 $(u,v)$ を追加する手順は

$u,v$ が同じ連結成分にあったら何もしない(対称性により、色に関係なく同じ連結成分にあるかどうかが決まる)
そうでないとき、 $u$ が属する2つの連結成分の重みのうち、小さい方を答えから引く。 $v$ についても同様。
$u,v$ を前述のルールによって併合する
$u(v)$ が属する2つの連結成分の重みのうち、大きい方を答えから引く。

実装は適宜関数化するとよい(snukeさんの実装を参考にした)。 codeforces.com

2020-01-26

DDCC2020本戦-B : Hawker on Graph

こういう非自明な例が出てくると理解が進んで助かる。(間違ってたら教えてください)

問題

B - Hawker on Graph

解法

　解説の議論を追っていくことにしよう。

単に足していくだけだったら...

　まず最初に、重み $w$ の辺を通るごとに所持金が $w$ だけ増え、負になることもあり得る場合を考えよう。この場合は、 $dp _ {u,v,k}$ を「頂点 $u$ から頂点 $v$ に $k$ 回の移動で向かうときの所持金の最大値」とすれば、遷移式は

$dp _ {u,v,k+1} = \max (dp _ {u,x,k} + dp _ {x,v,1})$

と書ける。 $k+1$ 回目で $v$ に行くので、 $k$ 回目にどこにいるかで全探索していることになる。
　ところで、この遷移式をよく見てみると、右辺が行列積の形をしている気がしてくる。例えば $\max$ を加算、その中の加算を乗算に置き換えてみると、これは実行列の四則演算における積の計算そのものである。 $\max$ と加算の場合も、同様に行列を用いて計算ができる。元の問題に立ち返れば、加算はグラフ上でパスを伸ばしていく演算であり、 $\max$ は互いに素なパスの結果をまとめる演算ということになる。
　遷移が行列で書けるということは、行列累乗による高速化を検討したくなる。行列累乗に持ち込むには、2つの演算に「結合則」(演算を行う順番を変えても結果が変わらないこと、交換則とは違う！)と、加算に交換則が成り立つこと、分配則が成り立っている必要があるが、 $\max$ と加算はもちろんそれが成り立っている。そういうわけで、この場合は $O(N ^ {3} \log K)$ で解くことができる。

元の問題の解法

　元の問題では、所持金 $x$ のときから重み $w$ の辺を通ると所持金が $\max(x+w,0)$ となる。この変化を行列累乗に持っていくことを考えよう。そのためにまず、この所持金の変化の関数を $\max(x+a,b)$ と見て、行列の各要素に $(a,b)$ のペアを持たせることにする。次に、上述した行列積に落とすのに必要な2つの演算を考えよう。まずパスを伸ばす演算を考える。 $f = \max(x+a,b)$ 、 $g = \max(x+c,d)$ とすると $g \circ f = \max(\max(x+a,b)+c,d)$ となる。ここで $x+a \leq b$ のときは $\max(b+c,d)$ となり、 $x+a \gt b$ のときは $\max(x+a+c,d)$ となる。これをまとめると

$g \circ f = \max(\max(x+a,b)+c,d) = \max(x+a+c,\max(b+c,d))$

となり、これはたしかに合成前の関数と同じ形をしている。
　次に、パスをまとめる演算を考える。これ $\max(x+a,b)$ と $\max(x+c,d)$ の $\max$ ということになるが、 $x$ のある方を使うなら $a$ と $c$ の大きい方、使わないなら $b$ と $c$ の大きい方が関わるので、単に $\max(x+\max(a,c),\max(b,d))$ でよい。これも合成前と同じ形をしている。
　今定義した2つの演算はどちらも結合則と分配則を満たし、パスをまとめる演算は交換則を満たすことがわかるので、これらの演算をもとに行列累乗が可能である。

実装

atcoder.jp

自分で演算を用意したり、今回は可換な演算ではないので2項演算でもどちらを前に置くかなどに気を付ける必要がある。おかしいなと思ったら雑に順番を入れ替えるのも手かもしれない（？）。

2020-01-11

Codeforces#613-E:Delete a Segment

遅延セグ木で殴るのは、気持ちがいい。

問題

https://codeforces.com/contest/1285/problem/E

解法

　座標 $i$ について、その座標を覆う区間の数を $s_i$ とする。求めるものは、(考えるべき座標の両端の $s$ の値が0であることにすると) $s_i$ 上で $0$ が連続している部分(つまり区間)の数から $1$ を引いたものになる。この値が区間を1つ取り除いたときにどうなるかを調べたい。
　ここで、遅延セグ木を用いてこの全探索を行うことを考える。各区間に持たせるべき情報を考えよう。まず、 $0$ の区間の数は当然必要である。また、区間のマージを考えると、今考えている区間の左/右端が $0$ かどうかという情報も必要であるとわかる。さらに、区間の $s_i$ の値を $1$ 引いたり足したりするので、 $s$ が $1$ のときについても、 $0$ と同様の情報を持たせるべきであるとわかる。区間への作用が心配だが、今回は $1$ か $-1$ のどちらかで、区間を一度取り除いて戻すということしかしないため、適切に $0$ と $1$ の値を更新するだけでうまくいくというのがミソになる。

実装

https://codeforces.com/contest/1285/submission/68552603

セグ木力の向上を実感できてよかった。

2019-12-31

第一回アルゴリズム実技検定(PAST) 感想

　クレジットカードを持っていなかったので課金できず(?)、バーチャル参加をしました。179:50で全完、ひどいハマりかたをしたところはあったけどまあ自分の実力的にはこんなもんかなと思います。簡単に感想と解説を書いておきます。そのうち出る公式解説が丁寧だと思うので、あまり参考にならなさそうだけど...。提出はこちらで、言語はC++です。

A

　stringで読んだ後、islower()で小文字があるかを判定、なければstoi()で整数に変換して2倍する。ある程度関数をちゃんと知っていると楽。

B

　書いてある通りに。

C

　sortして上から3番目を出力する。

D

　各数が何回現れたかをカウントして、すべて1ならCorrect、そうでないなら回数が0のものが回数が2のものに変わったということなので、それを出力する。

E

　ハマった(は？)。書いてある通りにやるのだが、クエリ3の処理でフォローすべきユーザーを列挙してから更新を行わないとだめ。順番に更新を行ったためにサンプルが合わず頭を抱えていた。

F

　Aと同様、islower()とisupper()で大文字小文字判定ができる。指示の通りに文字列を分割してsortをするが、sortの際に小文字に揃えておいて、後で大文字に直すみたいなことが必要なので注意。自分は(小文字の配列,文字のid)でソートしてよしなにやった。

G

　 $3 ^ {N}$ の全探索。dfsでもよいし、bitで集合を管理するやつでもできる。提出参照。

H

　遅延セグ木を貼ってしまったが、その必要はない。「偶数/奇数の中での残りの数の最小値」と「偶数/奇数について、クエリ2または3でどれだけの量が出荷されたか」ということを表す変数を持っておくと、売れるかどうかの判定はこれらの変数をもとに判定できる。よって、この問題は $O(N+Q)$ で解ける。そもそもこの発想が遅延セグ木っぽいんだけど...。

I

　この問題と全く同じ。dp[i番目のセット販売まで見た][手に入れた部品の集合]でdp。

J

　少し悩んだ。整備することにしたマスの集合は、「ある1点を始点とした点 $(H,1),(H,W),(1,W)$ に伸びている、互いに始点以外をを共有しない高々3つのパスの分解できるようなもの」だけを考えればいいことがわかる。よって、始点を全探索してDijkstra法で上記3つの点への最短距離を求めてその和を取ればよい(始点の値も足す)。

K

　LCAを貼ってしまった。貼らずにやるなら、根からdfsをして、初めてその頂点を訪れるタイミング $in _ v$ と、最後にその頂点を訪れるタイミング $out _ v$ をメモしておく。すると、 $a$ が $b$ の子孫である条件は $in _ b \lt in _ a \lt out _ b$ となる。

L

　少し悩んだ。大きい塔だけを頂点と見たグラフで最小全域木を作るみたいな感じだが、それだけだと小さい塔を使うと得をする場合の扱いが難しい。よく考えると、小さい塔を使うことがあるなら、使った小さい塔たちは当然大きい塔たちとも連結であるはず。だから、使うことにした小さい塔の集合を決め打つと、大きい塔と(使うことにした)小さい塔を含めたグラフの最小全域木のコストが答えの候補になる。bit全探索+クラスカル法でOK。

M

　お　ま　た　せ
　平均最大化といえば二分探索。モンスターの強さ $k$ 以上を達成できるかを判定。これは $\rm{(魔力の和)} - k\rm{(質量の和)\geq 0}$ と同値なのでこれを判定する。使うお助けモンスターを決めるとあとはdp[何体目まで見たか][何体使うことにしたか]というdpで上記の量の最大値を求め、この値が0以上なら $k$ が達成可能とわかる。計算量は $O(NM\log{ans})$ 。

N

　 $W$ がでかいことをとりあえず忘れる。ある区間を石がないようにするために必要なコストは、(すべての石のコストの総和)から(その区間と共通部分をもたないような石のコストの総和)を引いたものになる。後者の値は、 $l _ i$ :右端が $i$ より左側にある石のコストの総和と $r _ i$ :左端が $i$ より右側にある石のコストの総和をあらかじめ累積和みたいな感じで計算しておくと $O(1)$ でわかる。
　今述べた方針で全探索できそうだが、ここで $W$ が大きいことを思い出すと、これでは間に合わない。よく考えると、区間の候補としては左端や右端が、ある石の左端や右端と同じ位置にあるものだけを考えればいいので、座標圧縮をしておけば区間の候補が $O(N)$ になって間に合う。ちょっと添え字とかがめんどくさい。半開区間を信じる。

O

　これと似ている。出目の大小しか関係ないので出目は座標圧縮しておく。 $dp _ i$ を直前に出た目が $i$ のときに振れる回数の期待値の最大値、とすると、 $i$ の大きい順に更新していけば遷移できる。何も考えないと遷移が $O(N)$ で間に合わないが、どのサイコロを振るべきかを考えると、当然振る回数の期待値が最大であるようなものを振るべきである。各出目に対応するサイコロは1つなので、 $dp _ i$ を更新した後に、対応するサイコロについて「このサイコロを振るとどれくらいの期待値ががもらえるか」という値を加算しておくと、遷移がO(1)、セグ木とかを使うと $O(\log{N})$ でできるので間に合う。セグ木に投げる関数をmymaxという名前にしてたのに中身は加算にしていて、20分くらい時間を溶かした...。

だいたい典型だと思えたのでよかった。割と楽しかった。実装は、遅いね...。

2019-12-14

Segment Treeを理解したい人生だった

本記事は、Competitive Programming (1) Advent Calendar 2019 - Adventarの12/11分として書かれたものです。

この記事について

　こんにちは、monoidsigma¹です。皆さんはSegment Tree(通称セグ木)を知っていますか？セグ木というのは簡単に言うと、結合則 を満たす演算の関わる区間に関するクエリを高速に処理することのできるデータ構造です。扱うことのできる構造は「モノイド」という名前が付いており、本記事でもこの言葉を使うことにします。セグ木の導入としては区間の最小値を求める問題や区間の総和を求める問題が扱われることが多いです。また、セグ木の実装を「抽象化」することで、一般のモノイドに対応することが可能であるということが広く知れ渡っています (beetさんの記事、実装についてはこちらの記事)。
　ところが、じゃあ実際セグ木でどういうことができるのか、ということが具体的に書かれた資料はあまり多くありません²。本記事では、行列演算や一次関数の合成、最大公約数の計算など有名な例はもちろん、名前のつかないような非自明なモノイド達³をセグ木で扱う問題について簡単に解説・紹介します。このようなモノイドは、あまり「モノイド感」のないモノイド達であり(理由:名前がない、有名じゃない)、彼らを扱うことができるようになれば、セグ木に対する理解をさらに深めることができると考えています。

注意

問題例がいくつかあるのでネタバレを含みます。
基本的に半開区間で考えます。 $a _ {l,r+1}$ とか書いてあったら区間 $[l,r+1)$ のついてのなんかの量だと思ってください。⁴。
実装例をいくつか載せていますが、セグ木の部分はうしさんのライブラリを使わせていただいています。うしさんありがとう。⁵

セグ木に載る構造

　セグ木をあまり知らない人(がここまで来ているかわかりませんが)のために、セグ木のアイデアを確認します。実装レベルの説明は他の記事(ふるやんさんの記事やTsutajさんの記事など)に任せることにして、どういう事実を利用しているのかということをみていきます。
　数列 $a _ i$ が与えられていて、 $\min(a _ l, a _ {l+1} , \cdots, a _ r)$ が知りたいとしましょう。このとき、 $l \leq m \leq r$ を満たす $m$ について、次の等式が成り立ちます。

$\min(a _ l, a _ {l+1} , \cdots, a _ r)$ = $\min(\min(a _ l, a _ {l+1} , \cdots, a _ {m}),\min(a _ {m+1}, a _ {l+1} , \cdots, a _ r))$

これは、「区間 $[l,r+1)$ に関する最小値は、区間 $[l,m+1)$ と区間 $[m+1,r+1)$ に関する最小値がわかれば計算できる」ということを言っています。再帰的な構造をしていますね。この事実が成り立つために、minについて結合則が成り立つことが重要であることに注意してください。 このよう、結合則から導かれる「ある区間の答えを、その区間を分割してできた2つの区間の結果から計算できる」という構造を利用していると考えると、セグ木を使って問題を解く上で便利だと思います。あとは計算量を落とすためにいろいろ工夫するわけですが、そこは上述の記事を参照してください。

有名な例

　それでは、セグ木を使ってできることの具体例の紹介をしていきます。

min/max,sum

　最初にセグ木を試すならやはりこれでしょう。dp高速化などの手段としても頻繁に登場します⁶。

1次関数の合成

　 $f _ i=a _ i x+ b _ i (a _ i \neq 0)$ として、 $f _ r \circ f _ {r-1} \circ \cdots \circ f _ l$ を求める問題です。一般に関数の合成は結合則を満たしますが(交換則は満たさない！)、次数が変わってしまうと扱うのが大変です。1次関数であれば合成しても次数は変わらないので、容易に扱うことができます。具体的には、区間 $[l,r+1)$ に対する合成の結果として $x$ の係数と定数項を持っておくことで、セグ木による扱いを実現できます。
yosupoさんのジャッジ Point Set Range Composite
実装例
 AtCoderでの問題例 ARC008-D : タコヤキオイシクナール

行列積

　行列の積は結合則を満たすのでセグ木に乗ります。dp高速化の文脈で出てきがちな行列積ですが、行列をセグ木に乗せて解く問題もありがちです。AtCoderの問題で比較的易しいものを紹介します。

D - DISCO!

解説

まず、与えられた文字列中に部分列として"DISCO"がいくつあるか、という問題を考えます。 $D _ i, I _ i, S _ i, C _ i, O _ i$ をそれぞれ、「 $i$ 文字目まで考えたときの、部分列 "D","DI","DIS","DISC","DISCO"の数」としましょう。このdpの遷移式は非常に単純ですが、この遷移を行列で書くと以下のようになります⁷。

$d _ i, i _ i, s _ i, c _ i, o_ i$ はそれぞれ、 $i$ 文字目がD,I,S,C,Oであれば $1$ 、そうでなければ $0$ である変数です。この行列積をとることで、 $dp$ の計算が可能です。
　元の問題に戻ります。各 $i$ に該当する行列をセグ木に乗せます。演算を通常の行列積とすれば、区間 $[l,r+1)$ に対応するdpの結果が得られることになります。行列積は可換ではないことに注意してください。
実装例

こっちの方がクエリ処理要素があります。解説はしません。 D - Dangerous Hopscotch

最大公約数(GCD)

　自然数 $a,b$ の最大公約数を求める演算 $gcd(a,b)$ も結合則を満たし、セグ木に乗ります。
問題例 : C - GCD on Blackboard
もうちょっとちゃんと試したい人用(TL注意) : Codeforces Round #458 (combined) D Bash and a Tough Math Puzzle

最小共通祖先(LCA)

　2頂点のLCAはよく見ると思いますが、当然それ以上の数の頂点のLCAも定義できます。LCAを求めたい頂点集合がバラバラだと順番に試していくしかありませんが、「頂点番号が $[l,r+1)$ の範囲にある頂点たちのLCAを求めよ」というクエリであれば、セグ木で対応可能です。区間 $[l,m+1)$ のLCAと区間 $[m+1,r+1)$ のLCAをそれぞれ覚えておき、それら2頂点のLCAを求めれば、 $[l,r+1)$ に対するLCAを求めることができます。
問題例 : Codeforces Round #520 Div2-D Company

ここまでは演算が単純なものを紹介してきましたが、少し非自明な例を見ていきます。

ACPC2019 Day3-E 総和の切り取り

問題概要

　数列 ${a _ i}$ に対して、 $q$ 回値の書き換えを行う。それぞれの書き換えの後、 ${a _ i}$ の連続部分列の総和の最大値を求めよ。
リンク

クエリでなければ有名な問題で、「 $dp _ i$ : $i$ 番目の要素を末尾とする連続部分列の総和の最大値」というdpで解けますが⁸、クエリがあると当然そうはいきません。セグ木を使った解法を考えてみましょう。
　 $ans _ {l,r+1}$ を数列「 $a _ l, a _ {l+1} , \cdots, a _ {r}$ における連続部分列の総和の最大値」とすれば、 $ans _ {0,N}$ を各クエリ毎に答える問題になります。「今まで通り、 $ans$ をセグ木に乗せておけばOK！」と言いたいところですが、今回はそうはいきません。次の図をご覧ください。便宜上、区間 $[l,m+1)$ を $L$ 、区間 $[m+1,r+1)$ を $R$ 、区間 $[l,r+1)$ を $LR$ と呼ぶことにします。 f:id:sigma1113:20191212150257p:plain

この図からわかる通り、今回は $ans _ {LR} = \max(ans _ {L},ans _ {R})$ とは限りません。緑色の区間のように、左端が $L$ 内にあり、右端が $R$ にあるような区間も考慮して、 $ans _ {LR}$ を計算しなければいけないからです。
　じゃあセグ木では解けない...？と思ってしまうかもしれませんが、そんなことはありません。ここで、「知りたい値を計算するために必要なものを一緒に載せておく」ということをします。緑色のような区間が答えとなる場合、それはどのような性質を持っているでしょうか？ $m+1$ から $L$ 側に区間を伸ばしていくことを考えると、 $L$ 内において、右端を $m$ に止めたときの区間の和が最大となるところまで伸ばしていけばいいことがわかります。 $R$ 側に伸ばしていくときも同様です。従って、次の2つの量が鍵を握ることがわかります。
$sum _ {l,r+1}$ を区間 $[l,r+1)$ の和として

$rsum _ {l,m+1} = \max _ {l'} (sum _ {l',m+1})$
$lsum _ {m+1,r+1} = \max _ {r'} (sum _ {m+1,r'+1})$

従って、これらの値を使えば、 $ans _ {LR}$ の候補は

$ans _ {L}$
$ans _ {R}$
$rsum _ {L} + lsum _ R$

の3つです。これで $ans _ {LR}$ の計算を行うことができました。これで安心...と言いたいところですが、まだ考えなければいけないことがあります。今度は $lsum$ と $rsum$ を計算しなければいけません。しかし、このためには単に区間内の和 $sum$ を持っていれば十分です。以上より、以下の4つの値を載せたセグ木を用いることで、この問題を解くことができます。

その区間における答え $ans$
その区間内において、その区間の左端を必ず使う区間における和の最大値 $lsum$
その区間内において、その区間の右端を必ず使う区間における和の最大値 $rsum$
区間の総和 $sum$

実装については、セグ木を抽象化しておけば、「何を載せるか」ということと「区間についてどのような演算を行うか」という情報を渡してあげれば十分です。
実装例

このように、セグ木に最終的に知りたい値だけはなく、「知りたい値を計算するために必要なものを一緒に載せておく」というテクニックは非常に有用で、実際同じようにして解ける問題もAtCoder以外のサイト⁹では出題されています(AtCoderにもありますか？)。以下に問題例を載せておくので、興味のある人は解いてみるとよいでしょう。

No.776 A Simple RMQ Problem - yukicoder (実は...)

略解

　載せる情報は上の問題と同じです。解答クエリは区間の位置関係によって丁寧に場合分けすることでできますが、解説によるともう少し楽にできるようです。
実装例

Codeforces Round #179 Div1-E Yaroslav and Points (DEGwerさんの記事から取りました)

略解

　まず、すべての入力を読んでおいて座標圧縮をしてしまいましょう。その上で、セグ木を使って圧縮後の区間に以下の6つの情報を載せます。

その区間における答え $ans$
区間の左端の(本来の)座標 $lx$
区間の左端の(本来の)座標 $rx$
区間内の座標の数 $num$
区間内の各点についての $lx$ との距離の総和 $lsum$
区間内の各点についての $rx$ との距離の総和 $rsum$

6つもあって少しびっくりするかもしれませんが、マージは複雑ではないです。
実装例

Codeforces Round #604 Div1-C Beautiful Mirrors with queries (期待値計算が難しいかもしれません。セグ木は不要なようですが、使って解けます。)

略解

　数学をすると、 $n$ 個の鏡をクリアするのにかかる日数の期待値 $E _ n$ は以下の式で書けることがわかります。

$\displaystyle E _ n = \sum _ {i=1}^n \frac{1}{\Pi _ {j=i} ^ {n} p _ j}$

　チェックポイントの変化に応じて、対応する値を足し引きすればよさそうです。セグ木に持たせる情報は以下の2つです。

その区間を抜けるのに必要な期待値(つまり答え)
$\Pi _ {j=l} ^ {r} \frac{1}{p _ j}$

実装例

Hackerrank(有志コン) 第3回ゆるふわオンサイト Div1-E Sweets Distribution(Hard)

略解

　4人の登場人物を0,1,2,3とします。この問題では、あるところまでは人0で、その後のあるところまでは人1で、...というように境界が定数個で、状態の変化も単調であることがポイントになります。この点を生かして、セグ木に以下の情報を持たせます。

$res _ {i,j} =$ 区間の左端を食べるのが人 $i$ で、区間の右端を食べるのが人 $j$ のときのその区間における答え

区間のマージは、各 $i,j (i \lt j)$ について、区間の境界で食べる人が切り替わる場合と、そうでない場合の2つを試せばよいです。式で書けば以下のようになります。

$\displaystyle res _ {i,j} = \max _ {i \leq k \leq j} (\max (res _ {L _ {i,k}} + res _ {R _ {k,j}},res _ {L _ {i,k}} + res _ {R _ {k+1,j}}))$

実装例

個人的にびっくりしたものを紹介しておきます。この問題を紹介するために本記事を書いたと言っても過言ではありません。ぜひ挑戦してみてください(ちなみに想定解はTLが厳しいです)。

Codeforces Round #526 Div1-C (Div2-F) Max Mex

略解

　次のものをセグ木に載せます。

区間 $[l,r+1)$ の数字をすべて含むようなパスが存在するかどうか(bool値)
存在するなら、そのようなパスの両端

区間のマージは、例えば各端点の組をすべて試し、パスになるかどうかを調べるという方法があります。マージには $O(1)$ のLCAを使いましょう(は？)。また、マージの際の定数倍にも注意してください(は？)。
　この情報を持ったセグ木を使えば、Mexの値はセグ木上の二分探索によって求めることができます。

　自分はこの問題の解説を読んでびっくりしました。セグ木でこんなことができるんですね...。

　他にも「こんなものもセグ木に乗るぞ」というもので面白いものがあったら教えてください。掲載を検討します(遅延セグ木はまたの機会に...)。

RMQ and RAQ をセグ木で解く(noshi91さん提供)

　面白い話を聞いたので紹介します。RMQ and RAQは遅延セグ木の入門問題として有名ですが、なんとこれをセグ木を使って解きます。これができればもう遅延セグ木はいらないですね！
　まず簡単にアイデアを説明します。区間加算クエリをimos法で処理することを考えます。つまり、 $[l,r+1)$ に $x$ 加算というクエリが来たら、 $l$ に $x$ 加算し、 $r+1$ に $-x$ 加算します。ここでセグ木に以下の情報を持たせます。

その区間より左側からの加算を無視したときの、その区間の最小値 $min$
その区間より右側にあとどれくらい加算するかを表す値 $sum$

そして区間 $L,R$ のマージを以下のように行います。

$sum _ {LR} = sum _ L + sum _ R$
$min _ {LR} = \min(min _ L, sum _ L + min _ R)$

$min$ のマージの式の右辺の $min _ R + sum _ L$ の部分がポイントです。区間 $R$ に、区間 $L$ からやってきたimos法の影響を足しこむことで、区間加算の操作を実現しています。
　注意点ですが、区間 $[l,r+1)$ の最小値を答えるクエリに対しては、 $sum _ {0,l} + min _ {l,r+1}$ の値を答える必要があります。 $l$ より左側から始まった区間加算クエリの影響があるかもしれないからです。

実装例

データ構造を載せる

　データ構造であるセグ木にデータ構造を載せるということもできます。CHTを載せるLi-Chao Treeやセグ木を載せる話があります。本記事では紹介にとどめますが、興味のある方はリンク先の記事をご覧ください。

あとがき

　本記事では、セグ木の載るものを具体的にいくつか紹介しました。特に、知りたい値を計算するためにいろいろな値を載せるというテクニックは、セグ木の適用範囲を広めるものだと思います。本記事が皆さまのセグ木に対する理解の一助となれば幸いです。ちなみに遅延セグ木についても記事を書いていますが、公開日時は未定です。¹⁰
　それでは、快適なセグ木ライフを。

idsigma - AtCoder ↩
beetくん　はやくこれを完成させなさい↩
非自明というのは基準が人によって違うので難しいですが、代数慣れしていない人に「モノイドの例を1つ教えて」と言われて、本記事の後半で紹介するようなモノイドを挙げる人はおかしいんじゃないかと思ってしまいます(冗談です) ↩
半開区間はいいぞ　境界を求めて累積和するときとかもごちゃごちゃにならない(個人の感想です) ↩
ライブラリを自分で書くか、ネットに落ちているものを使うか、それとも用意しないかというところは意見がわかれるところだと思います。中身がブラックボックスだと困ることもあるので、最初に一度は自分で書いて、あとは早いのを使うというのが個人的な落としどころです(実践しているとは言っていない) ↩
実家dpとか誰かが言ってたらだいたいセグ木が出てくるイメージ ↩
1いらないかも ↩
$i$ 番目を足しても負にならないなら足しこむ、なるなら $0$ を入れる感じの遷移 ↩
こういうのも面白いと思うんですけどね…↩
説明がつらい↩

2019-11-24

ABC146

A

曜日を格納した配列を作っておいて、入力と一致したら対応する値を出力すればよいです。

Submission #8612614 - AtCoder Beginner Contest 146

B

各文字ごとに丁寧にN回インクリメントすればよいです。

Submission #8612571 - AtCoder Beginner Contest 146

C

$d(N)(=c)$ を固定します。このとき、 $c$ 桁の整数であって、値が $\frac{X-cB}{A}$ 以下である整数を買うことができます。そのような整数のうち、最大のものが答えの候補です。 $c$ は1から10まで試せばよいので間に合います。(19まで試したしまったけど...。)

Submission #8612542 - AtCoder Beginner Contest 146

D

まず $K$ の値がいくつになるかを考えます。次数が $d$ の頂点があったとき、その頂点に関する条件を満たすためには $d\leq K$ でなければなりません。つまり、次数の最大値が $K$ の下界です。逆に $K$ が次数の最大値であるような辺の塗り方が作れることを示します。根を1つ決めてdfsしながら順に塗っていきます。頂点 $v$ に来たとき、 $v$ の親 $p$ との間にある辺の色を覚えておきます(根の場合は適当に関係ない値にしておく)。この色以外を使って $v$ の子との辺を塗らないといけませんが、 $v$ の子の数は $K-1$ 以下であり、 $K-1$ 色使っていいのでそれらを好きに塗ればよいです。あとは実装力勝負でしょう。

Submission #8612498 - AtCoder Beginner Contest 146

E

難しいと思いました。区間 $[a,b$ の和を $S _ {a,b}$ 、その長さを $l$ とすると、ある自然数 $x$ があって、 $S _ {a,b}=xK+l$ が成り立つということが条件です。 $l$ を移項すると $S _ {a,b}-l=xK$ で、 $S _ {a,b}-l$ が $K$ で割り切れればよいです。ここで $S _ {a,b}=(A _ a-1)+(A _ {a+1}-1)+\cdots+(A _ {b}-1)$ が成り立つので、新たな数列を $B _ i = A _ i-1$ で定義します。すると、この問題は、「数列 $B _ i$ について、その総和が $K$ で割り切れるもののうち、長さが $K$ 未満である連続部分列の数を求めよ」と言い換えられます。これは $B _ i \ (mod \ K)$ の累積和 $T _ i$ をとると、 $T _ a=T_b$ のとき、 $T _ b-T _ a$ が $0$ なので、 $B _ {a+1}$ から $B _ b$ の和の $(mod \ K)$ は0です。従って、 $T _ i$ が同じ $i$ をまとめておいて、あとはその差が $K$ 未満である組の数を数えればよいです。

Submission #8621948 - AtCoder Beginner Contest 146

F

最短の回数を求めるには、 $dp _ i$ : $i$ までの最短回数、というdpが思い浮かびます。愚直にやると $O(NM)$ ですが、遷移をこれはセグ木で高速化できます。ところが、今回は辞書順最小の移動手順を求められているので、 $i$ を小さい方から埋めると困ってしまいます。しかし、 $i$ を大きいほうから埋めるとどうでしょうか？
$dp _ 0$ まで埋まった状態から、辞書順最小の移動手順を求めます。今0にいるときに、条件を満たすような位置は「 $dp _ 0 = dp _ i +1$ 」を満たすような最小の $i$ です。これはセグ木を用いた二分探索によって見つけることができます。この操作を $N$ にたどり着くまで繰り返せばよいです。全体で $O(N(logN) ^ 2)$ かけてもいいですし、「セグ木上の二分探索」によって $O(NlogN)$ の計算量を達成することも可能です。

Submission #8625619 - AtCoder Beginner Contest 146