第二回全国統一プログラミング王決定戦本選に参加してきました！

予選

A:はい

B:まあ、はい

C:これ本当に難しい。DE解いた後に考えたけど無理だった。

D:遅延セグ木で殴れそうなので殴ります→AC

E:小さい方から $2N$ 個の和が大きい方から $N$ 個の和より小さい、というのが明らかに必要条件。どうせこれが十分条件でしょ、と適当な直観を信じて実装→AC

ABDEの4完で157位でした。まあまあ余裕で予選通過しました。

当日

遅刻しました（は？？？）

日経コン遅刻しない？遅刻だね
— 濃い紅茶 (@koi_kotya) 2019年12月15日

コンテスト開始2分前くらいに会場に到着。 Wi-Fiの接続あれこれは間に合いませんでした。

ぞい！（遅刻）
— 濃い紅茶 (@koi_kotya) 2019年12月15日

そんなこんなで数十秒遅れでコンテストに参加しました。

A: わたわたしながら問題を読みます。真ん中を固定して考えると $O(N^{2})$ で解けそう。 →AC

B: 上位互換をこれで見た。 atcoder.jp IKを固定すると残りの部分の分け方が全部決まると気づく。 Z-Algorithmで前処理すると判定は $O(1)$ でできそう。 IKの全探索は $O(N^{3})$ でできるので、解けます。

C: とりあえず前処理として、上下右下に何個連続して黒マスがあるかを調べておく。 Nの左上の点を固定して、構成できる最大のNが $O(\log N)$ くらいで分かれば解けそう。

斜めに見たときに直線状に並ぶ各点について、(上に連続する黒マスの数)-(列のindex)をセグ木に乗せる。セグ木上で二分探索を行って、条件を満たす最大値を求める。

計算量は $O(N^{2}\log{N})$ で間に合うはず！と信じて実装するも実装のバグが取れずWAのままコンテストが終了……。解法のお気持ちは公式解説とほぼ同じだと思います。（ACコード）

ABの2完で128位でした。 Cが通せなかったことが悔しい。