kmjp's blog

競技プログラミング参加記です

Mo's, Algorithm の検索結果:

HackerRank 101 Hack 52 : C. Car Show

…通りあるか。 解法 Mo's Algorithmで解く。 まず、各区間の左端A[i]に対し、同じ数字を複数含まない最大の右端B[i]を求めておこう。あとはMo's Algorithmの要領で、左右の端を動かしつつ、内部に含まれる条件を満たす区間の数を求める。 区間内の要素をそれぞれ左端iとする場合、R<B[i]であるなら区間Rを右に動かしたとき、条件を満たす区間は1つ増加する。 この条件をもとに、クエリ区間内に収まらない右端の個数と、条件を満たす部分区間の数をそれぞれ更新して…

Codeforces #442 Div2 F. Ann and Books

…求めておこう。あとはMo's Algorithmで解いていく。 まずS[i]を、map等使い同じ値同士分類しよう。keyがS[i]、valueがiの昇順vectorとなるようにしておく。 あとは[L...R]に対する解の値から、前後1つ伸ばすか減らす場合の解の増減分を求めればよい。 例えば[L...R]から[L...(R+1)]になるとき、S[R+1]-S[x]=kとなるようなk∈[L..R]の数だけ解は増加する。 これはkeyを(S[R+1]-k)とするvalueのvect…

第3回 ドワンゴからの挑戦状 本選 : B - ニワンゴくんの約数

…コストが小さいため、Mo's algorithmで解くことができる。なお、区間の増減の際複数の素因数に対し処理を行う必要があるので、Mo's algorithmを適用するだけだとまだちょっと重くTLEする。 Editorialでは、小さな素因数に対しては区間に対する素因数の指数の総和を前処理することで高速化している。 以下のコードではこのアプローチを取らず、同一の指数の複数回加減算をまとめたり、インラインアセンブラによる除算の高速化で無理やり通している。 int N,Q; l…

CSAcademy Round #13 : F. Interval Expected Max

…。 解法 平方分割でMo's Algorithmして解く。 区間の長さを1変えるとき、2要素の最大値の総和は以下のように変化する。区間を1伸ばし、値xが追加される場合、 xとx未満の要素が選ばれると考えると、x未満の要素の数だけ、2xが加算される。(2xは選び方が順不動なため) xとx以上の要素が選ばれると考えると、x以上の要素の数だけ、2*その要素が加算される。(2倍は選び方が順不動なため) 言い換えると、x以上の要素の総和の2倍が加算される。 自身が2回選ばれる場合、xが…

Codeforces ECR #006: F. Xors on Segments

…よ。 解法 想定解はMo's Algorithmなのだが…。 愚直にO(N^2)通りf(A[L],A[R])を列挙しても間に合ってしまうようだ。 int N,M; int A[50050],X[50500]; int L[50050],R[50500]; int XX[1010101]; int ma[50505]; int ret[50505]; void solve() { int i,j,k,l,r,x,y; string s; for(i=1;i<=1000000;i…

Codeforces #340 Div2. E. XOR and Favorite Number

…は定番のテクがある(Mo's Algorithmと呼ばれているらしい?)。クエリをfloor(L/√N)昇順でfloor(L/√N)が一致するものはR順に並べ替えよう。 すると1回のクエリあたり区間の左端Lを動かす量は平均O(√N)となることが期待できる。 また区間の右端は基本的に右に動かすだけで、前のクエリと比べfloor(L/√N)が異なるときだけ左に戻すので、左に戻す回数はO(√N)であることが期待できる。 よってLもRも動かす回数はO(N√N)程度動かせばよい。 in…