ACPC2019 day1 参加記録

結果

途中から参加して2完でした。ABは問題なく解けたのですが, CでREが出てしまい困り果てた末の2完でした。

気づいたこと・感想

• std::vectorはループの中でサイズ変更の可能性がある場合, イテレータを用いたループをするべきではない
• そのような場合, イテレータの変わりにindexとsize()を用いるべきである
  • 概要ツイート (opens new window)
  • この原因はstd::vectorの内部実装に依ります
  • std::vector::emplace_back (opens new window)を見ると以下のように書かれています

この関数を呼び出す前にsize() < capacity()であった場合、この関数の実行は定数時間で行われる。そうでない場合は、メモリ領域の再確保と、その領域への要素のコピーもしくはムーブが行われるため、線形時間で実行される。

• ということで, ループを行っている間にsize()を変更するとメモリの再配置が行われるため, イテレータの情報が古くなってしまう
• 何も知らずに機能を使うとこうなることを知った