pekempeyさんの最強解説 ei1333さんの最強解説
pekempeyさんの記事に乗っていることですが「要素が更新されない」「クエリの先読みが可能」「区間 [L,R] の結果から [L-1, R], [L+1, R], [L, R-1], [L, R+1] の結果が容易に得られる」という条件が大切
計算量はO( (N+Q)√N) で、追加削除はO(1)かO(logN)が求められることが多く（O(logN)は大体計算量オーバー）、答えを求める部分はO(sqrt(N))でも間に合う
派生が色々ある
- Mo's Algorithmの上位互換があり、永続データ構造と組み合わせることで解ける問題が増える
  - この上位互換では範囲を増やすのは自由だけど、減らすのは難しい(Rollbackでしか出来ない)場合は上位互換を使う
- 時空間Mo's Algorithm
  - 更新に対応している解説1 解説2
- 木上でのMo's Algorithm
  - 理解してない
  - http://codeforces.com/blog/entry/43230
  - http://codeforces.com/blog/entry/55574

問題

通常のMo's Algorithm
- HR Unique Art
- HackerRank Week of Code 31 Nominating Group Leaders 平方分割+Mo's Algorithm
- 第3回ドワンゴからの挑戦状本選 B. ニワンゴくんの約数 Mo's Algorithm+それ以外の難しい高速化
- CF429 Destiny
- CF442 Ann and Books
- CF204 Jeff and Removing Periods 解説
- HR Car Show 解説
- HE Powerful Pair in Tree

時空間Mo's Algorithm
- CF466 Machine Learning

未処理

2017-04-17

CodeChef April Challenge 2017 問題と解説

競技プログラミング

https://www.codechef.com/APRIL17?order=desc&sortBy=successful_submissions

Similar Dishes

T組の料理がある。
各料理は4つの材料で構成されている。
T組の料理が似ているならば"similar"、似てないならば"dissimilar"をそれぞれ答えよ。
※似ている : 材料のうち半分以上が同じ

Dish Of Life

N個の島とK種類の材料がある。
i番目の島ではP[i]種類の材料が集まる。

全ての島を回っても材料が全て集まらないなら"sad"
全ての島を回らないと材料が全て集まらないなら"all"
全ての島を回らなくても材料が全て集まるなら"some"

を出力せよ

Bear and Row 01

1と0から成る文字列Nが与えられる。
行える操作は「ある1に対して端っこに行くか隣に1がある状態まで動かす」操作である。
この操作は移動距離+1のコストがかかる。
全ての1を左に移すために必要なコストの総和の最大値は？

Bear and Clique Distances

N頂点ある。
この頂点のうち、1～K番目の頂点は完全グラフであり、辺のコストはXである。
これとは別にM本の辺があり、A[i]とB[i]をコストC[i]で繋いでいる。
頂点Sから他の頂点への最短距離を求めよ。

Chef and Divisor Tree

Divisor Treeは以下のルールで作られた根付き木である。

根はある数
ある親の子はノードに書かれた数の約数(書かれた数は除く)
数が1となると葉
ノードにはコストがあり、そのコストはノードの次数と等しい

(問題文のテストケースに図があるのでそれをみると分かりやすい)
A<=n<=Bをみたす全てのnに対して、Divisor Treeを作り、根からある葉へのパスのコストの総和の最大値を計算し、その総和を答えよ。

Stable market

N個の数列Aがある。
その数列に対してQ個のクエリについて答える。
各クエリでは、[L[i],R[i]]の範囲でのK[i]連続区域は何個あるかを答える。
K連続区域とは同じ数がK個以上連続しているまとまりのこと。

Bear and Random Grid

命令文Sと、N*Nの盤面がある。
盤面は'.'なら通れて、'#'だと通れない。
全てのセルについて、そこを初期地点として、命令文で動ける最大命令数を求める。
'.'のセルで最大命令数を求めたとき、そのxor和を答えよ。
盤面に'#'が出る生成規則がある(割愛)。

Chef and Digits

A[0]～A[9]が与えられる。
ある数について、現れる文字をカウントした時に、ある数iの個数が丁度A[i]となったとき、その数は嫌いとされる。
L<=n<=Rを満たす全てのnに対して、嫌いでない数は何個あるか。

Serejs and Billiards

マラソン問題
ビリヤードをする。
(0,0)から(N,N)の盤面がある。
ボールがM個あり、4*M回まで操作ができる。
操作のルールは
1. 加速度としてdx,dyを-1,0,+1で指定し、E回分だけ動かす。
2. 端に当たると跳ね返る
3. (-1,-1),(-1,N+1),(N+1,-1),(N+1,N+1)のいずれかに入ると得点

Heavy-Light Decomposition

与えられた根付き木をHL分解する。

Light辺を通るときは長さLでコストL
Heavy辺を通るときは長さLでコスト(ceiling[log_2L] + 1)

かかる。Heavy辺を上手く選んで、根から全ての葉へのコストの最大値を最小化せよ。

以下、解説

はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Beginner Contest 060 / AtCoder Regular Contest 073 解説

競技プログラミングにおける最長部分増加列問題まとめ

最長部分増加列

問題

競技プログラミングにおける桁DP問題まとめ

桁DP

問題

yukicoder contest-１６１解説 (yukicoder No.504 505 506 507)

CSAcademy Round #25 問題と解説

0-Sum Array

Suspect Interval

Rectangle Path

Min Ends Subsequence

Zone Capture

競技プログラミングにおけるMo's Algorithm問題まとめ

Mo's Algorithm

問題