AtCoder Regular Contest 077F: SS

実験的にやるのがたぶん正攻法だけど、もうちょっと文字列の周期のこととかに気を配れるとよかった。解説にも書いてありますが、g(n+2)=g(n+1)+g(n)になります。これは実験をすると比較的簡単に気づけます。 証明は g(n)→g(n+1)にするということは、g(n)の接…

AtCoder Grand Contest 019D: Shift and Flip

なんとなくの解法はわかるけど詰めるのが結構難しいと思う。Sをiだけ右にshiftした場所でTと一致させることを考える。 移動したSとTを比較したとき、Si == 1 && Ti == 0のとき、その場でSiを0に反転させることができない。ほかの場合はその場で反転できるor…

赤黒木

最初に これいる?要はmergeとかsplitとかできるようになった強い配列です。ここらへんを参考にして実装しました。 https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf http://algoogle.hadrori.jp/algorithm/prbtree.html h…

2-SAT

(P||Q||...)&(R||S||...)みたいな連言標準形で書かれた論理式を真にする割り当てはあるかを判定する問題をSATといいます。 2-SATの場合カッコ内のリテラル数が高々2つ、つまり(P||Q)&(R||S)みたいになってます。2-SATの解き方は蟻本の通り、SCCを使って真のn…

Euler Tour

Euler Tourは木を直線にして扱いやすくするテクニックです。 これを使うとLCA、二点間のpathの長さがO(logN)で求められます。でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。 HL分解は実装が重い…

永続segtree

永続は怖いイメージがあると思いますが、segtreeくらいなら簡単に永続化できます。 単にupdateされる予定のnodeを複製して、その複製されたnodeに対してupdateを行えばいいです。 普通のセグ木に複製してリンクを張り替えるコストが増えただけで更新の計算量…

AGC017C: Snuke and Spells

http://agc017.contest.atcoder.jp/tasks/agc017_c解説を見るとこんなうまいやり方があったのかぁ…となるんですが、それをどうやって思いつけるようになるかが重要だと思います。 僕はこう考えたらしっくりきました。まず魔法をかける前、ボールがどうなって…

AGC017D: Game on Tree

http://agc017.contest.atcoder.jp/tasks/agc017_d(ある点vのsubtree)と(vから親pへ向かう辺)で構成されるグラフについてgrundyが求まれば、あとはXORをとれば、pのsubtreeに対してgrundy(p)が求まります。grundy(v)は再帰的に求まるとして、このグラフにvか…

grundy数

grundy数について勉強したのでお話します。grundy数はご存知の通り、ゲームの勝敗を求める際に使う数なのですが、こんな感じの性質があると思います。1.grundy数は非負整数であり、grundy数=0ならば負け、grundy数>=1ならば勝ちを意味する。 2.grundy数=kの…

POJ 3690: Constellations

http://poj.org/problem?id=3690蟻本に書いてあるように二次元hashをすればいいです。hashといえばこの記事 http://hos.ac/blog/#blog0003 が有名ですが、ここに書いてあるように3つのmodでhashをとるようにしてみました。注意:TLE解法です。 struct ll3 { …

SA+LCP+RMQ

SA+LCP+RMQで任意の2つのsuffixの組について先頭何文字が一致しているかをlog(N)で求めることができる。 前処理も全部O(N)でやることもでき、高速。(下のコードはRMQの前処理がO(NlogN)だが)HL分解した木に乗せることを考えながらライブラリ化した。 struct …

SA-IS

https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf elementi-bioinformatica/Two Efficient Algorithms for Linear Time Suffix Array Construction.pdf at master · Al…

AOJ2230: How to Create a Good Game

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230LP双対の問題。似たような問題でLongest Shortest Pathがあるのでそれの解説スライドを見ながら考察した。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2736 まず最長距離の双…

最短距離問題の双対について

LP

次のグラフの最短距離問題のLP考えよう。 辺は(辺番号)/(辺のコスト)となっている。 LPは次のようになる。min(y1+3(y2)+y3+3(y4)+y5) s.t. y1+y2=1 y1-y3-y4=0 y2+y3-y5=0 y4+y5=1 y1,y2,y3,y4,y5>=0行列を使うと、 min{yb|y>=0, yA>=c}となる。ただし A= {{…

AtCoder Regular Contest 081E: Don't Be a Subsequence

https://beta.atcoder.jp/contests/arc081Typical DP Contest FGHIJ - omochan's diary これのGとほとんど同じで、dp復元がくっついただけ。 でも1-originで逆から見ていくのでかなりこんがらがった。普通に0-originのstringを参照するときに-1をつければい…

Typical Dp Contest PQRST

DP

http://tdpc.contest.atcoder.jp/PQRSは結構難しい(はず)。解いたやつから順番にあげていきます。 P 木dpするだけのO(NK^2)、と言ってしまえばおしまいだが木dpはバグらせがち。 最初点を主役にして、dpの遷移が意味不明になった。 dp[v][K]:=((vのsubtreeに…

Typical DP Contest KLMNO

DP

http://tdpc.contest.atcoder.jp/K O(NlogN)ということは問題が簡単な構造をしていますね?区間dpなど複雑なものを考えないでください。 segtreeを使ってできます。 std::findはO(logN)と思っていたのでTLE出た時びっくりした。 あと区間を使う順番に気を付け…

Typical DP Contest FGHIJ

DP

http://tdpc.contest.atcoder.jp/F 駅に一回も止まらない方法は1or0通りなので 駅に一回は止まる方法を求めれば良い。 区間和を含んだ式になるが、大体形は決まっているので、代わりにsという値で更新を行っている。 あとは場合分けをきちんとする。 int N, …

Typical DP Contest ABCDE

DP

http://tdpc.contest.atcoder.jp/assignmentsTypical DP Contestの問題が最近のCodeforcesでも出たということを聞いて埋めておこうと思った。20問あるので5問ずつに分けます。A 配列使いまわしもして十分高速だけど、boolのdpだとどっかで無駄に情報持ってな…

Yosupo Wettbewerb E: Oh, Vertexes & Edges!

http://kcs.miz-miz.biz/contest/6/view/EAtCoder Grand Contest 014E: Blue and Red Tree - omochan's diaryこれと全く同じじゃん!と思ったけど微妙に違った。最初辺に注目してマージテクしようと思ったが(つまりqueueに入れるのを辺にした)、これでは新た…

KMP法

KMP

KMPのK - あなたは嘘つきですかと聞かれたら「YES」と答えるブログMP法とKMP法の違い - 生きたいここを参考にさせてもらいました。KMPで求めるのはまさに蟻本p327「禁止文字列」における文字列の状態推移である。 すなわち、ある文字列TとSを比較するとして…

MP法

MP法を勉強したのでメモ。文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログこれを参考にしました。A[i]の定義はS[0:i-1]の接頭辞と接尾辞が最大何文字一致しているかである。 [0:i-1]が一致しているから…

POJ 1854: Evil Straw Warts Live

BIT

http://poj.org/problem?id=1854蟻本には分割統治法と書いてあるがBITでやってしまった。同じ文字だったら一番右にあるのと一番左にあるのを回文のペアにするのが良くて、二番目三番目…についても同様である。 違う文字だったら、対称性よりどっちを先に端に…

AtCoder Grand Contest 014E: Blue and Red Tree

http://agc014.contest.atcoder.jp/tasks/agc014_eマージテクの問題を一つ解きたくなったので。詳しくは解説に任せるが、青と赤の辺が重なっている部分を一つの頂点に併合していく感じの操作が出来れば良い。 これは各頂点から生えてる辺を持ってマージテク…

UVa 10245: The Closest Pair Problem

UVa Online Judge蟻本にO(NlogN)になる理由などは述べられている。実装だが、ここが本当にうまいと思った。 //a is sorted by x coordinate int m = n / 2; double x = a[m].fst; double d = min(closest_pair(a, m), closest_pair(a + m, n - m)); inplace_…

UVa 12161: Ironman Race in Treeland

UVaデビューです。UVa Online Judge重心分解。問題はどうやってsubtree間のpathを高速に処理するか。 まず各subtreeの重心からのpathについてdamageとlengthの合計を求めておく。 それをすべて一つの配列に入れてsortして、その配列と同じ大きさのsegtreeに…

POJ 2114: Boatherds

http://poj.org/problem?id=2114蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書…

POJ 1741: Tree

http://poj.org/problem?id=1741重心分解。解法は蟻本にある。適当に整備して使いやすいようにした。updateだけいじればよくなっている。updateも重心を根とする木について考えれば良いので楽。 namespace CD { //centroid decomposition struct edge { int …

POJ 3470: Wall

http://poj.org/problem?id=3470平面走査するだけのタイピングゲーなんだけど、TLEがかなり厳しい。AC率308/2036が物語っている。vectorを配列にするとかベタな高速化をしてもACに至らず…segtreeが重いのかな?TLE解法 struct T { pi v; T(pi v = pi(inf, -1)…

POJ 3411: Paid Roads

http://poj.org/problem?id=3411問題文をよく読みましょう。(a,b)は有向辺です。無向辺でやったあとを残しておきました。 ベルマンフォードっぽくbitDPをやればよい。 int N, M; int A[20], B[20], C[20], P[20], R[20]; int dp[1 << 11][11]; int main() { …