ACの二完。
コンテスト後のツイート
AtCoder Regular Contest 181 AC二完でした。
— titia (@titia_til) August 4, 2024
A 三回では可能。一回でできるかはBITとか使ってチェック。二回でできないのは、N,...,1のとき。
B Tの長さは分かったが、Tの長さが大きいとき処理できなかった。
C P,Qの逆順列を取り、その和がNより大きいかで1を入れるか0を入れるか決める。
B - Annoying String Problem
解法ツイートを参考にAC。
Sの一文字目がTの何文字目にあたるのか？ を調べる方針は良かったし、TがSの繰り返しだろうというのも当たっていた。
そこまでくればgcdで周期を考えるのは自然なはずだが、これを思い付けなかった。うーん。
また、Tの長さを計算したら負になる場合がある、ということに気付かずWAやREを重ねてしまった。
考察は後一歩だった気もするが、ここに引っかかることを考えるとACは遠かったね。
D - Prefix Bubble Sort
概ね自力でAC。（コンテスト後にツイートなどは見たけど、あまり参考にせず解いた）
xという操作を適用すると、「x以前にあって、転倒数への寄与が0より大きいものたち」は、indexが一つ下がり転倒数への寄与が一つ小さくなる、ということには割合すぐ気付けた。
が、実装が上手くできず、Aが広義単調増加であることをどう使えば良いかも迷った。長いこと遅延セグ木でどうにかならないかと考えていたけど上手くいかず、Aが広義単調増加ならクエリに関するimos法でできると気付けた。（これが公式解説の方法だった）
700点にしては簡単で、時間があれば自力で解けたとは思うけど、Cの後こっちを解いていれば解けたという気はあまりしない。
0 件のコメント:
コメントを投稿