baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ 主客転倒 数え上げ 括弧列 D - 1D Coulomb メモ 以後以下のように言葉を定義する S[i] := iの電荷(+か-) R(s) := sと逆の電荷, R(+) == -, R(-) == + cnt(i, s) := [0, i)にある符号sの数(つまりiより左にあるsの個数) まず各iがどちらに動くかを考える iが+の場合、i以外の合計は-1になり iが-の場合、i以外の合計は+1になる よって左右どちらかの合計が0の時、電荷は逆方向に動くため 一番左の電荷は右に動き、一番右の電荷は左に動く。 以後同様に考えると、各電荷は括弧列の対応のように動くことが分かる。 具体的には cnt(i, s[i]) >= … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2023%2F07%2F10%2F151726" title="AtCoder Regular Contest 164 D - 1D Coulomb - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-07-10 15:17:26 rich https://baitop.hatenadiary.jp/entry/2023/07/10/151726 1.0 100%