NECプログラミングコンテスト2021 (AtCoder Beginner Contest 229) D - Longest X (400)
.
の数の累積和を求めておく
それぞれの位置で以下を行う
$ 現時点までの.の数 - k
個の最も左の地点を求める
この地点までは埋めて全て
x
にできる
この区間の長さが答え以上なら更新する
毎回二分探索するので
$ \mathcal{O}(|S| \log |S|)
問題:
https://atcoder.jp/contests/abc229/tasks/abc229_d
提出:
https://atcoder.jp/contests/abc229/submissions/27525680
#NECプログラミングコンテスト2021
#ABC229
#400pt
#D
#ABC
#AtCoder
#O(NlogN)
#累積和