日本情報オリンピック 2011年本選

今年は難易度分布の分散が小さすぎるのではなかろうか。
去年の５番とかふつうに大苦戦して楽しかったのに……。
初心者にとっては難化。上級者にとっては易化。５完ゲーですね！


以下は解いたときの思考の流れメモ。実装は略。

１

・クエリだ
・よし平方分割だ
・微妙に間に合わない
・平方分割に加えて短冊状に切るなどすれば間に合うね
・端点固定DPでええやん……

２

・n≦10だ
・よし2^nだ
・dp[i][j]＝ジャンル集合iだけ使えてj冊売ったときの最高利益
・微妙に間に合わない
・端点固定DPでええやん……

３

・まずは始点が１点のみの例を考える
・とけた
・始点が増えてもやること変わらなかった

４

・Ｘ座標とＹ座標は独立に考えてよい
・座標でソートして、X_i

５

・微生物の匹数で二分探索ができる（×logn）
・耐久力最弱の微生物を固定すれば、簡単にとける（×n^2）
・↑は、setなどを使えば簡単に高速化できる（×n^2　→　×nlogn）
・あれもうおわり