堀で気力が死んでました。体調不良によりやむなく参加を見送りました。
C - Rectangle Cutting
長方形を二つに分け、小さい方の最大値。なので最大でも面積の半分になります。
真っ二つに分けることができれば話が早いですが、その方法は？というと与えられた点から中心に線を引けば真っ二つ。
与えられた点が中心ではないなら1本のみ。与えられた点が中心なら無限に引けます。
余談
「二つの長方形に分ける」と誤読したため延々と悩んでました。この方針でもAC結構出た(7/10)ため誤読に気づかず何か見落としてるケースが？と小一時間。日本語の勉強からですねぇ…。
D - Enough Array
ある連続部分列に含まれる全ての要素の値の和がK 以上になれば、のためその後も全部K以上になる。(1～iでK以上なら1～i+1、1～i+2、…もK以上)。
K以上となる区間を見つけて残りを足し合わせる、というのを繰り返せばいい。尺取り法でやった。
E
そのうちやる*1
F - Minimum Bounding Box
AC取った(@2019/6/24)のでメモ
次の解説記事がすごくわかりやすかったです。
私の理解でざっくりと書くと、
傾きが変化する時刻のどれかが答えとなる時刻となります。
傾きが変化する時刻の候補は、与えられた点をグループに分け、各グループ間の最大・最小値が重なる点です。
軸ごとに3つのグループに分けます
- 動かないグループ(x:U,D、y:R,L)
- 正方向に動くグループ(x:R、y:U)
- 負方向に動くグループ(x:L、y:D))
各グループについて最大・最小値を記録します*2。
傾きが変化する時刻ですが、まじめに考えると面倒なので、単純に各グループ間の最大・最小の差分の絶対値を取ってそれぞれの時刻を調べりゃいいと思います。高々2x2x3x2+1の25個*3、十分間に合います。
