Codeforces Global Round 2

こどふぉ（Codeforces）に初めて参加した！
初参加で４完レート1578（青まであと22）だったけどAtCoder換算とかどうなんだろう、よくわからない

A - Ilya and a Colorful Walk (500点)

問題: Problem - A - Codeforces
どちらかの端から出発して貪欲に見ていって長いほうを出力してAC。 $O(n)$ 。

拙解 (C++14): Submission #52388117 - Codeforces

B - Alyona and a Narrow Fridge (1000点)

問題: Problem - B - Codeforces
長さ順にボトルをソートすると、長いほうからペアを作って収納するのが最も少ないスペースで収納できるとわかる。 $1\le h \le 10^9$ のオーバーフローに気を付けつつ、 $O(nlogn)$ でソートして何本まで入るかを二分法（ $O(logn)$ ）で探すとAC。 $O(n{log}^2 n)$ 。

拙解 (C++14): Submission #52394207 - Codeforces

C - Ramesses and Corner Inversion (1500点)

問題: Problem - C - Codeforces
所定の操作をどのように行っても、行・列ごとのパリティビットは変わらないことが分かる*1。そう考えると、変更点は必ず長方形を描くような４つ組に分解できなくてはパリティビット列を保持できないことが分かる。したがって、 $A$ と $B$ のすべての行・列のパリティビットがあってるかどうかをチェックすればAC。 $O(nm)$ 。
~~大学教授に問題出されて解けないラムセスとかいう問題設定で某ソシャゲ連想して草生えそうになった~~

拙解 (C++14): Submission #52397285 - Codeforces

D - Frets On Fire (2000点)

問題: Problem - D - Codeforces
$1\le k \le n$ に対する「s_iから始まる連続する長さ $r_k-l_k+1$ 個の整数列」を全部合わせたとき登場する整数が何個あるか数える必要がある。
被る区間がいくつあるかは、区間ごとの隙間を考えると、 $\{ a_i\}$ の階差数列をソートして二分法で求められるから、これをもとに被った部分を引いてAC。 $O((n+q)logn)$ 。