beet's soil

競プロのことなど

典型テクニックまとめ

いつも忘れるので整理してまとめるぞい

続きを読む

多重vectorを可変引数テンプレートで


すいばか さんに圧倒的感謝🙏🙏😭🙏🙏

以下C++ のコード

すいばかさん版:型は最後の引数で決まる

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}

template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

型をtemplateで指定する版

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

グローバルでauto関数が定義できるの知らなかった(ラムダだけだと思い込んでた)

eiyaさんの N次元配列を同じ値で埋めるテンプレ2 を参考にするとfillもできる
N次元配列を同じ値で埋めるテンプレ2 - 永夜の記録

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

githubのリンク
library/vec.cpp at master · beet-aizu/library · GitHub

auto dp=make_v<int>(4,h,w);
fill_v(dp,0);

みたいに使える

これでやっと

vector<vector<vector<int> > > dp(4,vector<vector<int> >(h,vector<int>(w)));

から解放される…!

std::vector::emplaceのargsに自身の要素を指定してはいけない

突然ですが以下のコードは何が出力されるでしょうか?

#include<vector>
#include<iostream>
#include<numeric>
using namespace std;
signed main(){
  vector<int> v(8);
  iota(v.begin(),v.end(),0);
  v.pop_back();
  v.emplace(v.begin(),v.back());
  cout<<v.capacity()<<endl;
  for(int x:v) cout<<x<<" ";
  cout<<endl;
  return 0;
}

当然
6 0 1 2 3 4 5 6
になってほしくないですか?僕はなってくれると思ってました。
実際僕のローカル環境ではそうなりました。

これを踏まえた上でこれらのオンライン実行環境での動作を見てください。
Paiza: Online PHP/Java/C++... editor and compiler | paiza.IO
ideone: Ideone.com - YD77BF - Online C++0x Compiler & Debugging Tool
wandbox: [Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
yukicoder: オンライン実行 - yukicoder


5 0 1 2 3 4 5 6

は?キレそう
wandboxのバージョン機能で試したところ、gccの6.3までのバグっぽい。
未定義動作でした。(2018/03/14追記) eiyaさんありがとうございます。


AtCoder( GCC 5.4.1 ) とか CSA (バージョン書いてないけどバグった)とかでは気をつけましょう。
CodeForcesとyukicoderはgcc7.2に対応しているのでデフォルト設定を変えておいた方がいいかもしれません。


そこまで厳密に調べたわけではないんですが、要素数をいじるような操作(resize()とかpop_back()とかpush_back()とか)を行なった後は、emplaceのargsに自身の要素を指定してはいけないようです。
対策はそこまで面倒ではなくて、vector::emplace ではなく vector::insert を使えばいいだけです。

別に仕様とかではないっぽい(実際gcc7系以降では修正されている)
vector::emplace - cpprefjp C++日本語リファレンス

gcc7で修正されている例
wandbox: [Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
yukicoder: オンライン実行 - yukicoder

全部未定義という仕様でした(うーん)
そもそももっと大きな括りとして変更操作時には再確保が行われる可能性があるので、引数に自身の参照を与えると全て未定義になるようです。
回避策としては一度変数に退避するか、コンストラクタで一時オブジェクトを作るかでしょうか(うーん)



B - Holes

上の問題を解いていて軽い気持ちで番兵入れようと思って

    g.emplace(g.begin(),g[m-1]);
    g.push_back(g[1]);

したらバグって1時間解けたのでいろいろ試したところコンパイラバグ未定義動作だとわかってつらかった。
C++はクソ
それではみなさん、快適なC++ライフを!w

ACM-ICPC 2017 Asia Tsukuba Regional

うぃーんビートビートひるどwwwwwwうっくっくwwwwwwえいえいえt(←いずらいt)いえいwwwwらて。

続きを読む

Heavy-Light Decomposition

この記事は
「競プロ!!」 競技プログラミング Advent Calendar 2017 - Adventar
の13日目の記事として書いています。

続きを読む