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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

東京大学プログラミングコンテスト(UTPC)2014 E問題 宝くじ

AtCoder

初めてのSegment-Tree
値を二つ持つタイプのSegment-Treeです。
ちなみに本番では解けてません。

- 問題概要

宝くじの実況中継をします。
当選番号aと賞金bが発表されます。
このとき、宝くじの番号の下|a|桁がaであるとき賞金bがもらえます。
この(a,b)がn回与えられ、(a,b)が与えられるたびにその時点で宝くじ1枚でもらえる合計金額の最大値を出力せよという問題です。

- 解法

解を満たす当選番号は入力で与えられる当選番号のいずれかが必ず満たします。
したがって与えられる当選番号より状態を増やす必要はありません。
解法にはTrie-TreeとSegment-Treeの2種類があります。
以下Segment-Treeでの解法になります。

まず数値を文字列に変換します。
そして文字列を反転します。
すると12345,345という当選番号が与えられたとき、文字列として反転すると
54321,543となり、345が12345の下三桁であるとき、543は54321と開始3文字が一致します。
そして辞書順で比較すると、543と開始3文字が一致する文字列は必ず543よりも辞書順で大きくなります。
また、たくさんの文字列をソートすると、543から始まる文字列は連続することが分かります。
つまり、543を開始文字とする当選番号に賞金を加算したいという操作をするということは、文字列の配列の連続した区間に対して加算をするということと同値になるのです。
区間を管理したいときにはSegment-Treeが有効です。

あらかじめ出てくる文字列をソートしておきます。
ここで、同じ文字列が存在しないようsetなどをかませておきましょう。
出てきた文字列でSegment-Treeを作成します。
k番目の要素の子は2k+1,2k+2となっています。
各ノードは[s,t](文字列配列のs番目からt番目までの区間)というように区間を管理し、
ちょうど[s,t]に加算された値の合計値addと
そのノードの子ノードにおける要素の最大値child_maxを保持します。
どの区間に加算を行うかはlower_boundなど二分探索を用いて求めましょう。
そのノードが管理する[s,t]よりも問い合わせられた[p,q]のほうが小さいときは分割して再帰的に呼び出すことで一回の問い合わせ、最大値更新の計算量がO(|a|\log n)となります。

全体の計算量はO(|a|n\log n)となります。

- ソースコード

http://utpc2014.contest.atcoder.jp/submissions/378562
トライ木のほうは木の高さが最大で10なのは分かるんだけど子ノードの管理をどうすればいいのか分からなくて手をつけていません。
入力で与えられる当選番号に10個の配列をつけてやればいいのかな?