AtCoder Beginner Contest #017

コンテストページ http://abc017.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/abc017
A - プロコン
3つの課題の配点と得点割合が与えられて合計もとめるだけ
B - choku語
choku語は空文字列またはchoku語の末尾に"ch","o","k","u"を連結した文字列と定義されるのでchoku語かどうか判定せよ。
解法は各文字列の先頭文字がすべて異なるので先頭からマッチングするだけ
C - ハイスコア
解説のとおりある宝石を選び方についての最適解を列挙すればいい。Xを覆う区間というのはli<=X∧X<=riとなる区間でありこのままだと2次元の問題となり面倒だが補集合を考えるとX<li∨ri<Xとなる区間の集合となりX<liを満たす区間とri<Xを満たす区間は重複しないことからそれぞれ独立に求めればよくて1次元の問題になる。よって宝石Xを獲得しない選び方の最適解は(X<liを満たす区間の個数+ri<Xを満たす区間の個数)として求めることができる。
D - サプリメント
解説のとおり左端の位置についてサプリメントを摂取できる最大の右端の位置は広義単調増加となるので尺取法でO(N+M)で列挙できる。組み合わせの計算については各iについてdp[i]の値を足しこむ範囲は必ずiより後ろなのでいもす法を使いながら計算すればO(N+M)で解ける。