問題文 http://poj.org/problem?id=2217Suffix Treeを実装したので最長共通部分文字列の問題にsubmit。 #include <iostream> #include <vector> #include <algorithm> #include <string> #include <cctype> using namespace std; const int SIZE = 128; struct Node { int b,e,d; //begin, end, distance f</cctype></string></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C&lang=jp参考スライド http://www.slideshare.net/iwiwi/2-12188845Link Cut TreeでLCAをやってみました。 Link Cut Tree部分はほとんど参考スライドのものと同じです。 #include<iostream> #</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_6_A 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で紹介されいるが、セグ木を使って効率よく解けると書いてあったので実装。 x座標を座標圧縮すると平面走…

問題文 http://judge.npca.jp/problems/view/97参考にさせていただきました http://sigma425.hatenablog.com/entry/2014/12/30/164148i回目のループで、x回目のループ終了時点での配列aの[l,r)の区間に含まれる数の個数を答えるので永続segtreeが必要。 #inc…

問題文 http://poj.org/problem?id=3580区間への加算 区間の反転 区間の右巡回シフト 挿入 削除 区間の最小値 のクエリがくるので処理する問題。参考にしたもの http://www.slideshare.net/iwiwi/2-12188757 mergeやsplitとかは参考スライドのもの。区間 [l,…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116典型問題。↓を参考にした。 http://algorithms.blog55.fc2.com/blog-entry-133.html #include<iostream> #include<vector> #include<stack> #include<algorithm> using namespace std; typedef pair<int,int> pii; char G[501][501];</int,int></algorithm></stack></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A Range Minimum Queryを平方分割で解いた。 #include<iostream> #include<algorithm> #include<vector> #include<climits> #define max_n 100000 using namespace std; typedef long long ll; const ll B=1000; ll a[max_n</climits></vector></algorithm></iostream>…

文字列がいくつか与えられるので全ての文字列に現れる部分文字列の中で最長のものの長さを求めよ。 suffix arrayを使えば良い。共通部分文字列は蟻本に詳しく書いてる。嘘解法だった。隣同士の最長共通部分文字列しか計算してないのに通っていた。 #define I…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6133.pdf補完機能を使って文字を打つとき、ひとつの文字を打つのに必要な最小の打たなければいけない文字数の平均を求めよ。 トライ木を使った。そのノードの子が2つ以上なら、そこまでで補完機能一…

問題文 http://poj.org/problem?id=3468 蟻本でも紹介されている問題。 セグメント木を実装した。各節点は次の2つのデータをもつ。 whole[ ] その節点の区間全体に一様に加えられた値 part[ ] その節点の区間に一様でなく加えられた値 #include<iostream> #include<vector> #in</vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6139.pdf数列とクエリが与えられる。クエリは以下の2種類である。C a b 数列のa番目をbに更新する。 P a b 数列の区間[a,b]の積が負であれば-、0であれば0、正であれば+を出力する。 セグメント木を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431 (全ての荷物の重さ)-(最長増加部分列の重さ)が答えになる。dp[ i ]:= i 番目を最後尾とする最長増加部分列の重さ dp[ i ]=max(dp[ j ] | 0 i未満の番号の最長増加部分列の最大値を求…