parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 二分探索 XOR 排他的論理和が総和以下っぽい。詳しく説明する。 とする。 まずが成り立つ。更にも成り立つ。 部分文字列の左端lを固定してみる。このときr=lならば明らかに条件を満たす。 A[l]⊕A[l+1]⊕...⊕A[r] < A[l]+A[l+1]+...+A[r] が成り立つと仮定する。このとき、先のxorの性質により A[l]⊕A[l+1]⊕...⊕A[r]⊕A[r+1] < A[l]+A[l+1]+...+A[r]+A[r+1] が成り立つ。 よって右端をいくら伸ばしても常に総和のほうが大きい。 つまりl<=r<=Nについて順に 等しい、等しい、等しい、等しい、総和のほうが大きい、総和のほうが大き… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2018%2F05%2F28%2F145706" title="D: Xor Sum 2 - AtCoder Regular Contest 098 - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=x%2C%20y%2C%20z%20%5Cin%20%5Cmathbb%7BZ%7D_%2B Hatena Blog https://hatena.blog 2018-05-28 14:57:06 rich https://par.hateblo.jp/entry/2018/05/28/145706 1.0 100%