Codeforces Round 921 (Div. 1)

　A一完で紫に落ちた。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 921 (Div. 1) A一完でした。順位表を見るとB飛ばすべきだったのかも……。
A n回、全ての文字を使い切るindexを調べる。その最後に現れた文字をもっておく。
B stoqさんのブログ（https://t.co/wF4sfpn6ct）のコードを使わせてもらった。……が、WA on 8が取れず。えー。

— titia (@titia_til) January 27, 2024

B. Space Harbour

　等差数列をセグ木で扱えることは知っていたが、どうすれば良いか覚えていなかったので、検索するとstoqさんのこの記事が出てきた。

　等差数列を足し込む遅延セグ木があることを知り、そのコードを拝借して解こうとした動き自体は良かった。遅延セグ木を使う問題だとPyPyじゃ間に合わないことも多いしね。

　しかし、C++に慣れていないためコードを直すのに時間がかかり、WAが出た後の修正もできなかった。

　結局、間違っていたのは、「upper_bound()をそれ以下のindexが現れる最大のindex」だ

と思うという勘違いのため。

　lowerとupperで対称的なのかと思ってしまったんだねぇ。そして、それでもtest7まで通ってしまったため、定義を確認したり色々なケースを試そうという気持ちになれなかった。せめて他のケースを試していれば気付けて時間内に修正できた可能性はあるね……。そこも反省。

・lower_boundはbisect_left

・upper_boundはbisect

　胆に銘じておこう。

　なお、その他に添え字ミスもしていて結構ACは遠かった。test7まで通ってるから本質的なミスじゃないはず、と思ったのがはっきり間違いでした。