読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

O(√n)

Educational Codeforces #18: E. Colored Balls

http://codeforces.com/contest/792/problem/E

Codeforces Round #395 (Div. 1) E. Timofey and our friends animals

snuke さんの以下の記事を読んでいればやるだけ?snuke.hatenablog.comhttp://codeforces.com/contest/763/problem/E 問題概要 n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与…

CodeChef SnackDown Online elimination round

https://www.codechef.com/SNCKEL16

Educational Codeforces Round 13 F. Lena and Queries

http://codeforces.com/contest/678/problem/F 問題 以下の 3 種類のクエリを処理せよ。 点 (x,y) を set に追加する i 番目のクエリで追加した点を set から削除する xq+y の最大値を求める

Codeforces Round #350 (Div. 2) A,B,C,D

今回は比較的解きやすい問題だったせいか E まで解けた人が多く、解くスピードも求められたようだ。 A. Holidays http://codeforces.com/contest/670/problem/A 問題 一年が n 日ある惑星の話で、平日 5 日と休日 2 日が交互にやってくる。1 年を通した休日…

約数の個数の総和を O(√n) で求める

$n$ の約数の個数を $d(n)$ と書くとき、 $$ D(n) = d(1)+d(2)+ \cdots + d(n) $$ は $O(\sqrt{n})$ で求められる。 $n$ 以下の正整数で $i$ を約数に持つものは $\lfloor n/i \rfloor$ 個ある。このことから $$ D(n) = \left\lfloor \frac{n}{1} \right\rfl…

Mo's algorithm

Educational Codeforces Round 6 の F 問題 Xors on Segments の想定解が Mo's algorithm らしいのですが、Mo's algorithm を知らなかったので調べました。 そのついでに記事にしておきます。 このページを参考にしました。 www.hackerearth.com Mo's algori…

Educational Codeforces Round 5 E. Sum of Remainders

毎回 Educational の E 問題ぐらいになるとパッと解けない。 問題文 codeforces.com 問題概要 整数 n, m が与えられるので、n mod 1 + n mod 2 + ... + n mod m を求めよ。