writerやってましたー。
まず最初に、Div 1 Easy, Medium の exampleまわりのbroadcast messageが飛んだことに関してお詫びいたします。
解説を書きますー。
Div2 Easy
int count = 0; if(prev < 1200) count ^= 1; if(now < 1200) count ^= 1; ans += count;
みたいにすると条件分岐が少なくなりますが、まあ普通に書いたほうが無難でしょうか。
ans += (prev < 1200)^(now < 1200);
さらにやるとこうなるのかな。慣れてないとミスるだけなのであんまりお勧めはしません。
Div2 Medium
とりあえず、全部が重なってる領域は長方形になるので、その辺の長さを全部試してみましょう。
そうすると、それを被覆できる長方形の個数を数えて、それらのmaxを答えれば良いということになります。
Div2 Hard
典型問題です。
とりあえず、'.'の行・列は無意味なので削除して考えましょう。残ったのがn行m列だとしときましょう。
直接求めるのは難しいので、包除原理を使います。
「普通にブロックを適当に置く方法 (= 2^(n*m))」- 「1行選んでそこにはブロックを置かないとしたときのブロックを置く方法 (= nC1 * 2^(n-1*m))」・・・
みたいな。
Div1 Easy
dp[i][j] = コンテストiの直後にcielコーダーで、レートがjであるときの最大値
最近のcolor change数を嘆きながら作りましたw
Div1 Medium
とりあえず、全部横長の長方形になるように回転しておきます。(ちょっと考えると重ねる時には向きをそろえた方が有利なことが分かるので)
とりあえずXでソートして、X[0]が含まれないグループに含まれるXの添字の最小値が i だったときは、Y[i]~Y[2N-1]の大きい方からN個を取るか小さい方からN個を取るかのどっちかだけを考えれば良い。あとはiを大きい方からheapを持ちながら試すなりすればいい。
解法がなんとなく分かってもちゃんと考えるのがむずかしい。
Div1 Hard
考察すると、下の図のいずれかのパターンが含まれていれば良いということが分かります。(証明は下の方に書きます)
これさえ分かればなんとなく解けそうな気になってきます。こういうのは「2冪 - 上図のパターンを含まないもの」を数えるのが常套手段です。
試しに上から順番に埋めて行くと、／＼みたいなのが出てきた瞬間にあとはその下がかなり確定することが分かります。あとはもうこの問題の本質ではあまりない気がするので省略します。（後半パートも結構ムズい。概要は、特性を生かしてうまくDPという感じ。）
上の図のいずれかのパターンが含まれていれば良いことの証明
まず、「鏡を除いても変わらない」ならば「光の経路が閉路をなしている」ことが言えます。
光の経路の閉路を含む最小の矩形だけを切り取って考えます。
とりあえず上の図のパターンが含まれないと仮定します。すると、
・上端に「／＼」がある場合はその二列は全部「／＼」で埋まっていなければならない。
っていうのが言えて、下端・左端・右端にも同様なことが言えます。
鏡を除く前は、光は各セルで必ず曲がるので、少なくとも
・上端に「／＼」または下端に「＼／」がある
・左端に「<」または右端に「>」がある
の二つが言えます。
つまり、矩形内の少なくとも２列が「／＼」または「＼／」で埋まっていて、少なくとも２行が「<」または「>」で埋まっていることになります。しかし、このようなことはあり得ない（交差できない）ので矛盾。
もっと簡潔な証明があれば教えて下さい。
あと「光の閉路があれば鏡の閉路も必ずある」みたいなことも言える気がしているんですが、あんまり証明できていないのでそれも分かった人は教えて下さい。
