Segment treeを整備したという日記
(2019/10 追記:自分のライブラリを GitHub で管理するようにし始めたので、最新版が以下から参照できます)
github.com
最近Sumsegtreeを使う問題を解いたら、持ってたSumsegtreeがバグってたので、ついでにもっと色々使えるように手直ししたのでその備忘録みたいなものを書きます。
c#でのsegtreeのコード載せてるページ少ないし、ね。
なお、基本的に秋葉大先生のスライドをとても参考にさせていただいて作っているので俺の記事は読まなくていいのでこちらをお読みください
プログラミングコンテストでのデータ構造
以下コードです。
using System; class Segtree<T> { int n; T[] tree; Func<T, T, T> f; T exnum; public Segtree(int m, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ex; } public Segtree(int m, T ini, Func<T, T, T> f, T ex) : this(m, f, ex) { for (int i = 0; i < m; ++i) tree[i + n - 1] = ini; all_update(); } public void assign_without_update(int j, T x) { tree[j + n - 1] = x; } public void update(int j, T x) { int i = j + n - 1; tree[i] = x; while (i > 0) { i = (i - 1) >> 1; tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } } public void all_update() { for (int i = n - 2; i >= 0; i--) tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } public T look(int i) { return tree[i + n - 1]; } // [s, t) public T run(int s, int t) { return query(s, t, 0, 0, n); } T query(int s, int t, int k, int l, int r) { if (r <= s || t <= l) return exnum; if (s <= l && r <= t) return tree[k]; return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r)); } }
(2016/04/19 : iniが指定されていない時にexnumで初期化するように設定しました)
(2016/10/03 : 色々細かいところを修正したのと、全体の初期化を でなく で実現するための関数を追加、あと半開区間にしました!)
まず、型を自由に指定できるようにしてあります、これは基本的にはlongにしとけばどうにかなるのであんま意味ない気もしますが、doubleにしたい時とか
D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
とかだとまぁ楽かなぁという気がします。
それでは、変数の解説をしていくと、
・Func
Func
また、MaxとかMinだと Math.Max とか Math.Min を渡してあげるだけで動きます、嬉しい。
その他でも、f(x1, f(x2, x3)) = f(f(x1, x2), x3) を満たす関数なら動くのかな...? 理学部じゃないのでわからん。
・T exnum
exnum は、区間が範囲外の時に返す値を入れる変数で、とても弱い値を入れておけばokです。例えば、Sumの時は0, Maxの時は-∞, Minの時は+∞, といったように。
・T ini
ini は、初期化用変数です。別にいらないような気もするかもですが、Tがclassだったりすると馬鹿みたいにランタイムエラーを起こすのであったほうが良いです。
あとは前述したスライドとほぼ同じなので、これで使えます。
一番の肝はコンストラクタで初期化する時で、そこがちゃんと出来てしまえばあとは毎回同じように使えます。めっちゃ嬉しい。
こちらが使用例になります。
Submission #694898 - AtCoder Regular Contest 033 | AtCoder
Submission #694924 - AtCoder Regular Contest 008 | AtCoder
#118362 No.426 往復漸化式 - yukicoder
(2016/10/03 : 使用例を追加しました)
最小費用流とか平衡二分探索木とかも持っとかなきゃなぁという気はしてる(書く気は起きない)。
No.335 門松宝くじ, No.336 門松列列
奇跡的に全完できたけど、普通にクソ苦手なセットだった
門松列の流行早く終わってくれ
No.335 門松宝くじ - yukicoder
No.336 門松列列 - yukicoder
門松宝くじは、当確率である2つの数字が選ばれたとき、3つの数字が門松列かつ3つの数字のmaxが最大になるようにもう1つの数字を選ぶようにして、そのときのmaxの期待値を出す問題(自分でも何を言っているのかわからない…)
普通に全部の選ばれる数字の組(通り)に対して ()通り全探索すると となりダメ(最初、800^3 = 2400万だと勘違いしてこれで出した)
そこで、選ばれた2つの数字について具体的に考えていきます
- 選ばれた2数a, b(a < b)について、元の順列におけるindexが index[a] < index[b] のとき
下図(横軸 : index, 縦軸 : 数値)で適当に赤く塗られたところの数をあと一つの数として選べば、3数は門松列になります
ここから、実は区間のMaxとminさえ持っていれば良いことがわかります
max[i][j]を区間[i, j]におけるMax、min[i][j]を区間[i, j]におけるminとすると、
max[0][index[b] - 1] > b のとき ...... 得点は max[0][index[b] - 1]
max[0][index[a] - 1] > a のとき ...... 得点は b
min[index[b] + 1][n - 1] < b のとき ...... 得点は b
min[index[a] + 1][n - 1] < a のとき ...... 得点は b
上のいずれにも適さないとき ...... 門松列を作れないので得点は 0
max[i][j], min[i][j] を前もって で求めておけば、各組に対して定数時間で求めることができ、結果 となります
index[b] < index[a] のときも同じような感じで求めることができます
門松列列は、順列の並び替えの中でジグザグな列は何通りあるか、という問題
(どっかで見たことある気がするけど、題意は または となる i が存在しないことと同義)
まぁ、DPを考えます。
i - 1番目の数がi番目の数より大きかったかどうかで、i + 1番目にどのような数を置けるかが決まります
(例えば ......, 6, 4 というところまで数列を作っていたら、次の数は5以上でなければならない)
使える数字は決まっていて、一度使った数字は使えないので、次に置ける数字がm個、次に置けない数字がn個だとすると下図のようになります
このとき、次のような漸化式が成り立ちます
dp[m + n][m] = dp[m + n - 1][n] + dp[m + n - 1][n + 1] + ... + dp[m + n - 1][m + n - 1] (dp[0][0] = 1)
(dp[m + n - 1][k] は、次に置ける数の中でk - n + 1番目に小さい数を選んだときの場合の数)
これをこのままループを回すと となりますが、
sum[i][j] = dp[i][k]
を順次求めておけば となり、間に合います
求めるものは、sum[N - 1][N] * 2 です
なんかすごい変なDPをしている自覚はあります......
それぞれ、提出はこんな感じです
#71404 No.335 門松宝くじ - yukicoder
#71459 No.336 門松列列 - yukicoder
(P,Q)-サンタと街の子供たち 解説(?)
なんかめっちゃ面白い問題だなぁ、と思いかつ上手くハマって解けたので、つたないですが解説記事を書かせていただきます。
(お昼に間違ってフライング投稿しちゃってて慌てて非公開にしましたごめんなさい><)
問題はこちら
No.321 (P,Q)-サンタと街の子供たち - yukicoder
ナイトはチェス盤のすべてのマスに到達できるが、それ以外の距離の移動のみではどうなるか? というもの
まずは、例外処理から(以下、 とし、各座標はすでに絶対値を取ってあることとします)
- (p, q) = (0, 0) のとき
自明に動けないので、 となる点がいくつあるか探します( が書いてなかったように思うのですが、できればどちらか明記していただけるとありがたかったかも、書いてあったらごめんなさい>< )。
- p = 0 のとき
ならばいけるので探します。
- gcd(p, q) > 1 のとき
必要条件として、 が挙げられます。かつ、p, q が互いに素となる状態にして後述の条件を満たすか判別すればよいです。
- p, q が互いに素のとき
とりあえず、チェス盤を考えます。
まず、ナイトと同じな (p, q) = (1, 2) のときを考えると、最初は (0, 0) の白マスにいて、移動した先は必ず黒マスになっています。
次に、(p, q) = (1, 3) を考えると、白マスにしか到達することができず、絶対に黒マスに到達することができません。
ここで、次のような仮定をすることができます。
「すべてのマスに到達できる ⇔ gcd(p, q) == 1 かつ (p + q) % 2 == 1」
かつ、
「gcd(p, q) == 1 かつ (p + q) % 2 == 0 ⇔ すべての白マス( (x + y) % 2 == 0 ) に到達できる」
本番では、私はこれを証明せずに投げて通してしまいました。
ここに証明を書いてもいいのですが、writerさんが解説ページで証明っぽいのをなされているのでここでは割愛させていただきます(めんどいし)。
http://yukicoder.me/problems/849/editorial
23分ほどでACし、7番目くらいでした。あんまこじらせないでさっと行けてよかった……。
happy b1rthday 2 me 解説
Advent Calender Contest 12日目の問題を担当しました、はい。
コンテストページ
順位表- yukicoder
問題
No.319 happy b1rthday 2 me - yukicoder
解説はこちら
めっちゃ頑張って作ったしみんなみちくり~
最初のほう全然解かれなくて☆4の機運が高まってたけど、23時時点で24人の方々に解かれたので、まぁよかったかなぁ、という感じです
【アンケート】
今日の@rian_tkb さんの問題
No.319 happy b1rthday 2 me
https://t.co/UaXyOIA6P7
の問題のレベルどれが良さげですか?
#yukicoder
— yukicoderお知らせアカウント (@yukicoder) December 11, 2015
24時間で1問とか激ヤバ、かつペナルティなしなコンテストなので、多少実装がめんどくても、多少WA狙いなサンプルケースでもゆるしてちょ、って感じ><
一応、想定解のコードっぽい何かです
http://yukicoder.me/submissions/62385
このような拙い問題を皆さま解いていただき、本当にありがとうございました
なんかそのうちもうちょい追記するかも
CODE FESTIVAL 2015 本戦、あさぷろ、リレー
遅くなりましたが、コード祭りのすべての?問題が公開されたようなのでそろそろ書かないわけにはいかないなぁ、と。
本戦
わりとFAを狙ってCから解きました(ただしバグらせた模様)
C : 貪欲に🍣を作ればよい、というのはすぐに見えたんだけど、焦って101みたいなのを2個とカウントしたりとかして7分とかかかった
A : やるだけ
B : まぁN = 1を見落として1WA
D : N-1点、つらい……、という感じ。書きながら考察していくうちに、N点取るのと同じ人数必要か一人少なくても大丈夫か、というのは最大人数必要な時間を全て含有するような区間があるか、というようにすればよい、というのはわかったのだけれど、途中から時刻の最大値が100000だったのをNだと勘違いしてて10分くらい溶かした、死にたい
E : まぁ貪欲にパターンに当てはめて短くしてくんだろうなぁ、と思いはしたけれど、
これ'!'が含まれているときは、入力が0かそれ以外か、出力は1, 0, -1の3通りのみ、となるので、元の式に0と1を当てはめて、その出てきた値がどれになっているか、という9通りに対して全てあらかじめ最短コードを求めておけばよいのでは……! っつって実装しました。
まぁコードを見てもらった方がはやいcode-festival-2015-final-open.contest.atcoder.jp
結局4通りしか見つからなくてそのままほい~、っつって投げたら通ってしまった、うん
と、ここまででちょうど1時間、といったところ
あとの2時間は何をしていたかというと、主にF問題の考察をしていたり、G問題の指数時間解を書いていたり(とほほ)していました
パーカーボーダーが5問になっていなかったらまた泣き寝入りしているところだった……
結果としては65位、感想とか思うところはこの前の記事で書いた気がするのでまぁいいや
あさぷろ
眠い、短縮王のせいで無限に眠い
ほんとは、短縮王についても自分の頑張りをすごくこの場で主張したいんだけど、普段からコードゴルフしているような人々にとってはあたりまえ体操だろうから出す先がない……
コードゴルフはこれから細々とやっていきたいっすね
あさぷろの問題については、Easyとの共通問題しか解けず
Aは普通に計算したけど、二分探索とかしても普通に間に合ったのかなぁ、どっちが実装楽かは個人差ありそうだけど
BはN = 100なので分割する場所をずらしながらLCSで、LCSは適当にそこら辺からdpコピペしてきた
Cは終了後にLinkedListから普通の配列(しゃくとり)に直したら通った、つらみ
リレー
リレーは本戦65位なので7問目を解く
これcode-festival-2015-relay.contest.atcoder.jp
パッと見やべぇわかんねぇw とか思ったけどよく見たら副菜のdpテーブル作っておいてそこに主菜をひとつひとつ当てはめていったときのmaxを見ればいいだけ
っつって実装しに行ったら緊張してたのか、クソみたいなバグで10分くらい溶かした、死にたい
当日のACコードcode-festival-2015-relay.contest.atcoder.jp
あとはBを解いたりJを試すみたいなことをしていた