heavy light decompositionを試したのでLCAの問題にsubmit。 参考にした資料 http://math314.hateblo.jp/entry/2014/06/24/220107問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C #include<iostream> #include<vector> #include<algorithm> #define REP(i, n) for</algorithm></vector></iostream>…

問題文 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=ITP1_11_D最近Scalaを学び始めた。詳しいことは後で。 import scala.io.StdIn._ object Main { case class Rotation(run: Dice => Dice){ def apply(d: Dice): Dice = run(d) def compose(…

問題文 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://poj.org/problem?id=3580前Treapで通した問題。今回はRBST。 #include<iostream> #include<vector> #include<algorithm> #include<ctime> #include<cstdlib> #define INF (1<<29) using namespace std; typedef long long ll; template<class T> struct RBST{ public: struct node_t{ T val,mini,lazy</class></cstdlib></ctime></algorithm></vector></iostream>…

問題文 http://www.spoj.com/problems/QCJ4/最小包含円のライブラリ検証問題。 自分の実装ではならしO(n)になっているはず… #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #include<cfloat> #include<cstdio> using namespace std; typedef double Real; Real EPS = 1e-8; c</cstdio></cfloat></climits></vector></iostream></algorithm></cmath>…

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

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0294 解説 http://web-ext.u-aizu.ac.jp/pc-concours/2014/download/pastexam/editorial2013_final.pdf私は書籍「最新コンパイラ構成技法」のLengauer-Tarjanの擬似コードを参考にしました…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2201金属棒の候補となる直線は ２円の共通内・外接線 ２円の内一方の半径にmを足したものと他方の円の共通内・外接線 両方の半径にmを足したものの共通内・外接線 の３通り。これを全列挙…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010前に通したコードを書き直したので。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<cstdio> using namespace std; typedef double Real; Real EPS = 1e-8; int sgn(Real a, Real b=0){return</cstdio></cmath></algorithm></vector></iostream>…

問題文 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=1131&lang=jp 解き直し。 y/x+1/z=(yz+x)/xz だから、これを使って探索。枝刈りはしなくても通る。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int p,q,a,n; int rec(int x,int y,i</algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156 g[現在の方向][Y][X]:=最短距離 でダイクストラ。 #include<iostream> #include<vector> #include<algorithm> #include<queue> #define rep(i,n) for(int i=0;i<(n);i++) #define INF (1<<29) #define Cost first.first #d</queue></algorithm></vector></iostream>…