ACPCVC20200212 復習メモ - tinumu's reminder

A: Flip and Rectangles

大きさが一定でなくても良いので、市松模様になっていると、色を行で全て同じに出来るので、
全て黒にすることが出来る。厳密な証明は2x2の4マスで考えると出来る(はず)。
左右2マスの色の異なり方が列において、同じになっている長さ $h$ が、 $2 \times h$ の長方形をなしていることを言うことが出来る。これは連結でき、 $w$ 列だけ長さ $h$ だけ異なり方が同じになっている場合は $(w+1) \times h$ の長方形をなすことが出来る。
これは幅を 1 だけ追加されているヒストグラムと見ることができるので、最大長方形を使うとこの問題を解くことが出来る。ただし、幅を 1 追加しないといけない。

差分を最大長方形にするの、やばいだろ(おかげで幅1のH の長方形のケースを忘れてしまった)

B: Fountain Walk

座標を適当にスタートを左下, ゴールを右上と考えてみる。
この時、早くなるかも知れない関わりのある噴水は、 $(x_1, y_1), (x_2, y_2)$ の領域内であることがわかる(外郭も含める)。
できるだけ多くの噴水を通ったほうが $20 - 5 \pi$ だけ縮まるので、この区間を最大増加部分列(LIS)に乗せてあげるとよい。
ただし、どうやっても $10 \pi - 20$ だけ増えてしまうケースがあって(増えるのは1回だけであることは証明できる)、うまく処理をして頑張ろうねという問題になっている(これが本質ですか(?))。

でも、実装がバグらなければ、一番簡単な気がするな。

C: Sand Glass

それぞれの時間 $r_i$ について、「どこまでの区間であれば、Xや0 の最大最小を気にせずに処理できるか」が $O(N)$ でシミュレートできる。
区間から漏れた $a_i$ については、漏れた側の上(下)限と同じ答えになるので、それを出力すれば良い。
区間が潰れてしまった場合は、潰れている位置 $a$ についてシミュレートするだけなのでこれも簡単に求められる。
実装は、時間 $t_i$ を挟む $r_p, r_{p+1}$ について見て、 $r_p$ から $t$ へのシミュレーションをするとうまく処理が出来る。時間を見つけるのにupper_boundなどで $O(log K)$ , シミュレーションは $O(1)$ である。よって $O(Q log K)$ 程度で処理が出来る。

えーこれは発想自体は結構楽じゃないか？
思いつきたいなぁ