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>…

問題文 http://poj.org/problem?id=3169蟻本で解説されてる問題。やっと理解した。不等式制約の双対をとると最短経路問題になる。 #include <iostream> #include <vector> #include <algorithm> #define MAX_V 1001 #define MAX_E 30000 #define INF (1<<29) using namespace std; struct </algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=24551~Nの頂点があって、1からNの間をT回移動したい。 一度移動に使った辺は使用できない。 移動の時に使う辺のコストの最大値を最小化せよ。 二分探索+最大流。 二分探索で、移動に使用する辺の最大値を決め打ちする。 決…

問題文 http://poj.org/problem?id=2391n頭の牛とm個のフィールドがある。 フィールドにはそれぞれ小屋があり、入れる牛の数も決まっている。 また、フィールド同士は辺でつながっている。 辺には牛が通れる数の制限はない。 全ての牛が小屋に入ることを考え…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122 dfsした。 #include<iostream> #include<vector> #include<algorithm> #include<cmath> using namespace std; vector<pair<int,int> >sp; int dx[12]={-1,0,1,2,2,2,1,0,-1,-2,-2,-2}; int dy[12]={-2,-2,-2,-1,0,1,2,2,2,1,0,-1}; int n</pair<int,int></cmath></algorithm></vector></iostream>…

問題文 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=2118数字が書いてあるグリッドが与えられる。 この数字の中から、4近傍に隣接しているもの同士をとらないように選んだとき選んだ数字の和を最大化せよ。 前の一行を覚えておくdp。 #include<iostream></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488 区間dp。monge性を使わなくても通ってしまった。 dp[i][j]:=i~j番目までの点で木を作るときの最小コスト #include<vector> #include<iostream> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cctype> </cctype></string></queue></set></map></algorithm></iostream></vector>…

問題文 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>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306重みつき無向グラフが与えられる。このグラフの中から 各ノードの"満足度"の総和を最大化するようなクリークを求めたい。 "満足度"とは、そのノードについているエッジのコストの最小…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264 問題文の通りに実装する。 x+y=z (mod p) x-y=x+p-y (mod p) x*y=z (mod p) x/y=x*mod_inv(y,p) (mod p) #include<iostream> #include<vector> #include<algorithm> #include<string> #include<sstream> #include<cstdlib> using namespace st</cstdlib></sstream></string></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070 dp[使った数字][和]:=場合の数 #include<iostream> #include<vector> #include<algorithm> #include<cassert> #define all(c) (c).begin(),(c).end() using namespace std; int count(int bits){ bits = (bits & 0x55555555)</cassert></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1269 動的計画法。 dp[使った素数の数][使った素数の最大のid][作りたい数]:=場合の数 #include<iostream> #include<vector> #include<algorithm> #define all(c) (c).begin(),(c).end() using namespace std; vector<int>w; </int></algorithm></vector></iostream>…

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

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0190 双方向bfsで解いた。 #include<iostream> #include<vector> #include<algorithm> #include<map> #include<queue> using namespace std; map<vector<int>,int>mp,used; struct State{ vector<int>v; int t; State(vector<int>v,int t):v(v),t(t){} }; v</int></int></vector<int></queue></map></algorithm></vector></iostream>…

3-SATを解く、Schoeningのアルゴリズムという乱択アルゴリズムを実装した。 変数はアルファベット１文字のみ。否定は~。 未検証。(a|~b|~c)&(b|c|~d) のように入力を与える。文字同士の間に空白は入れない。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #</cctype></string></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5874.pdf 二部グラフのマッチング。嘘解法だった。本当は一般グラフのマッチングで解くらしい。 #include<iostream> #include<vector> #include<algorithm> #include<set> #define INF 1LL<<62 #define MAX_V 1000 using namespace std;</set></algorithm></vector></iostream>…