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

問題文 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://poj.org/problem?id=2217蟻本で解説されてる問題。蟻本と週刊spaghetti sourceさんを参考にしてローリングハッシュで実装してみた。TLEになった。答えも正しく出てるのかはわからない。 #include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdio> #define</cstdio></vector></string></algorithm></iostream>…

問題文 http://poj.org/problem?id=1159与えられた文字列を、文字を挿入する操作のみを行って回文にする。挿入する文字の最小個数を求めよ。 ↓と同じ。メモ化再帰。int型を使うとMLEする。 http://d.hatena.ne.jp/TobiasGSmollett/20130702/1372785990 #incl…

問題文 http://poj.org/problem?id=1157訳 http://wikiwiki.jp/pku/?1157%20LITTLE%20SHOP%20OF%20FLOWERS メモ化再帰した。 #include<iostream> #include<algorithm> #define INF (1<<29) using namespace std; int h,w,v[102][102],memo[102][102]; int rec(int a,int b){ if(a=</algorithm></iostream>…

問題文 http://poj.org/problem?id=3254グリッドが与えられる。マスの数が1であるようなもののうちで、それぞれ4近傍に隣接しないような選び方がいくつあるか求めよ。 1行を覚えておくDP。 dp[ マスの番号 ][ 直前の1行の状態 ] := 場合の数 #include<iostream> #inclu</iostream>…

問題文 http://poj.org/problem?id=2441n頭の牛がいて、m棟の小屋がある。牛にはそれぞれ入れる小屋が決まっていて、全部の牛を小屋に入れるような入れ方が何通りあるかを求めよ。 ビットDPした。 dp[ 牛の番号 ][ どの小屋を使ったか ] := 場合の数配列がと…

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

問題文 http://poj.org/problem?id=1967 宝の位置とその宝を取れる制限時間が与えられる。任意の位置からスタートして、宝を全て拾うときの最短時間を求めよ。 区間DP。 l[訪れた区間の左端][右端]:=訪れた区間の左端を終端とする最短時間 r[訪れた区間の左…

問題文 http://poj.org/problem?id=3180N頭の牛がM本のロープでつながれている。 タンクの周りを正しく踊れている牛のグループの数を求めよ。 強連結成分分解して、含まれている頂点の数が2以上の強連結成分の数を数えた。 #include<iostream> #include<vector> #include<algorithm> using</algorithm></vector></iostream>…

問題文POJ http://poj.org/problem?id=1088UVa http://uva.onlinejudge.org/external/102/10285.html縦r,横cのグリッドが与えられる。 上下左右で、数字が現在のセルより小さいセルにのみ移動可能。 移動できる最長経路の長さを求めよ。 メモ化再帰した。 PO…

問題文 http://poj.org/problem?id=1014 1から6までの価値がついたビー玉を二人で分けたい。 ビー玉の個数が与えられるので同じ価値になるように わけられるかどうか判定せよ。 動的計画法で解いた。 ビー玉の価値の合計の半分が作れればよい。 個数制限つき…

問題文 UVa http://uva.onlinejudge.org/external/101/10117.htmlPOJ http://poj.org/problem?id=1271 高さhの牛乳に凸多角形のパンをk回浸す。 牛乳に浸されたパンの面積の最大値を求めよ。 パンの辺との距離がhかつ辺に平行な直線でパンを切り取る。 これ…