AtCoder Beginner Contest 132：C - Divide the Problems
問題
https://atcoder.jp/contests/abc132/tasks/abc132_c
解法
(N / 2 + 1 番目に難しい問題の難易度, N / 2 番目に難しい問題の難易度] のどれかを K と設定するのがよい．ソートすればこれは求まる．O(NlogN)．
解答
https://atcoder.jp/contests/abc132/submissions/6351673
AtCoder Beginner Contest 130：F - Minimum Bounding Box
問題
解法
x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい．なぜならば，変化するタイミング間では求める面積は広義単調増加・減少になるので，間ではなく両端のタイミングでその区間での面積の最大・最小となっているから．このタイミングは，左右それぞれに動くもののうち x 座標が最大・最小となる点同士，上下それぞれに動くもののうち y 座標が最大・最小となる点同士がぶつかるときになる．また，それぞれ x, y 座標が固定であるもののうち x, y 座標がそれぞれ最大・最小である点ともぶつかるときの面積も調べる必要がある．O(N)．
解答
AtCoder Beginner Contest 130：E - Common Subsequence
問題
解法
まず，問題文の解釈から．選んだ部分列の数字を文字列を連結させて読むのではなく，数列としてみたときに等しいものの個数を求める．例えば {1, 3, 3, 3} と {1333} は，各項を文字列としてみて連結させると同じものになるが，数列としてコンマ区切りで見ると当然同じではない．
以下の DP を考える．
dp(i, j) := S_i, T_j までありうる共通の部分列の個数の和
遷移は
dp(i, j) = dp(i - 1, j) + dp(i, j - 1) - dp(i -1, j - 1) (S_i == T_j のとき + dp(i - 1, j - 1) を追加でする)
となる．- dp(i - 1, j - 1) をしているのは，dp(i - 1, j) と dp(i, j - 1) の中で dp(i - 1, j - 1) を重複して数えてしまっているため．全体で O(NM)．
解答
問題文の解釈を間違っていたため Virtual コンテスト中に解けなかった...
