文字列操作の問題(AtCoder ABC158-D)

Question

https://atcoder.jp/contests/abc158/tasks/abc158_d
こちらの問題を解こうとしたのが以下のコードになります。(これで提出したらno matching function for call to ‘std::basic_string<char>::insert(int, char&)’となってしまいましたがこれの改善方法もわかりません。)

自分はinsertを使って解こうとしたのですが詰まったので断念して解説を見たらpop_front/pop_backを使って解いていたのですが、競プロ界隈で有名なけんちょんさんという方がinsertでも解けるとブログに書いていらっしゃったので解こうとしたのですがなんとなく違う気がするので解決のヒントをご教授いただきたく投稿させていただきます。またinsertとpush_back/push_frontはどう使い分けたらいいでしょうか？よろしくお願い致します。

#include <bits/stdc++.h>
using namespace std;

int main(){
  string s;
  int q;
  cin >> s >> q;
  
  for (int i=0;i<q;++i){
    int type;
    cin >> type;
    if (type==1){
      reverse(s.begin(),s.end());
    }
    if (type==2){
      int f;
      char c;
      if (f==1){
        s.insert(0,c);
      }
      if (f==2){
        s.insert(s.end(),c);
      }
    }
  }
    cout << s << endl;
}
  

Answer 1

std::basic_string<CharT,Traits,Allocator>::insert

先頭にcに格納されている1文字を挿入したいのであれば、

s.insert(0,c);

ではなく

s.insert(s.begin(), c);

もしくは

s.insert(0, 1, c);

です。

fとcが初期化されていませんが、コードを貼る際に省略して漏れたということでしょうか。

---

for内でtype==1の場合にreverseを呼んでいますが、10万文字を何度も並びかえるのは処理時間の無駄です。
type==1の場合は挿入位置を逆転させ、最後に並び替えが必要か判定したほうがよいのでは？

Comments

[cunwe]

ご指摘いただきましたようにs.insert(s.begin(), c);にしてcin >> f >> c;を追加して提出しましたら、TLE(Time Limit Exceeded)となってしまいました。insertは高速と聞いたのですが。。

[episteme]

> insertは高速と聞いたのですが。。
誰から? どこから?

[cunwe]

https://drken1215.hatenablog.com/entry/2020/03/08/144800
この方も「らしい」と伝聞形ですが...

[SHOMI]

文字列先頭への挿入はコピーが発生するので高速とは思えませんが。
内部バッファの前方にも領域を確保するような実装ならそういうこともあるかもしれませんが、確保されている領域を使い切ればやはりメモリ確保とコピーが発生しますし。

[episteme]

deque<char> か list<char> なら先頭/末尾に高速挿入できますぜ。

[SHOMI]

リンク先はdequeやlinked listに触れた後にstringでもinsert(0, c)～と書いているので、混同して言っているようには見えないんですよね…なぜinsertが高速だという話が出たのだろう

[cunwe]

すいません、僕の勉強不足による発言でした。「速い」というのはinsertなどのメンバ関数を使うと速くなるということなのでしょうか？それともvectorなどのコンテナクラス(？)を使うと速くなるということなのでしょうか？

[SHOMI]

STLのコンテナならなんでも挿入が速いわけではありません。
vectorは末尾への追加が高速(ただし、内部のバッファを使い切った場合はメモリの再確保・コピーが発生する)で、それ以外の位置への挿入は速くありません。その代わり、どの位置のデータへもアクセスは高速です。
listはどの位置へも挿入自体は高速ですが、先頭・末尾以外の場合は挿入位置までたどるための時間がかかります。
dequeは先頭、末尾への挿入・削除が高速です。
https://cpprefjp.github.io/reference.html#container

[cunwe]

まだそれらを使いこなせてないですが頑張ります。説明していただきありがとうございました。