概要 何となく理解したので自分用のメモ 文字列 s を cyclic に回転させた時の辞書順最小の文字列を求める問題をO(n)で解く 呼び方が色々ありそうだけど Wikipedia の Lexicographically Minimal String Rotation (以下 LMSR) を採用するLMSR は Suffix Arra…

概要 問題 ： 「多数の f_i(x) = a_i * x + b_i と，多数のクエリ x に対し min f_i(x) を求めよ．」 この問題を解くためにConvex Hull Trickというものがある． 蟻本において，K-anonymous Sequenceという問題の解法として紹介されている（Convex Hull Tric…

この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の16日目の記事です。 データ構造の話です。 地区予選の過去問を解いているときに、以下のような問題を見つけました。 【問題…

d[i] + e(i,j) >= d[j] というような形の式が何個か制約として与えられたとき、d[s]=0としてd[k]の最大値を求めましょうという話

ICPC2010アジア予選の問題で、 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308 というものがあった。 普通のライツアウトはある点を押すとその点とマンハッタン距離１の点が反転するが、この問題ではその点とマンハッタン距離dの点が反転す…

概要 ボロノイ図関連について、定義はボロノイ図 - Wikipedia参照高速にボロノイ図を求めるアルゴリズム（フォーチュンのアルゴリズム？）は存在しているのだが、ここでは1つのボロノイ領域をO(n(n+m))くらい?で求める方法を考える。（n:点の数、m:凸領域の…