Cまで三完。
コンテスト後のツイート
x+1からy個移動する場合を差分計算で計算すると、元のm個から一個抜き、一個挿入すればOK。PyPyだとSortedMultisetが必要で計算量はn*m*m*√m（√mはSortedMultisetでの操作）でTLEでした。コンテスト後にChatGPTにC++に直してもらったら一応ACできたけど、想定ではなさそう。
— titia (@titia_til) December 20, 2024
D. Shift + Esc
ツイートした解法でC++なら一応ACできたわけだけど、もっと簡単かつ計算量の良い解法があった。
shift回数全部試してDPすればsetなど必要ない！
shift回数を全部試すのは最初に考えたと思うのだけど、その中でDPすることを思いつかなかったのだと思う。累積和をとって全探索のm*mかかると思ってしまった。
しかし、言われてみるとDPするのは自然で、これをに気付かなかったのはダメ。
0 件のコメント:
コメントを投稿