はじめに
本記事は競プロ Advent Calendar 2023,第 4 日目の記事として書かれました.
本記事では,わたしが普段競技プログラミングに取り組む際に使っているテンプレ (C++) の紹介をします.使用言語が Python や Rust や Haskell の方,すみません.
動機としては,普段記事を書くとき*1にテンプレ部分を省略してコードを載せているのですが,そのテンプレ部分をまとめた記事が無いので,企画に便乗して書いてみようと思った次第です.
結構てきとーにやっている部分があるので,技術的にアレな部分もあろうかと思いますが,生暖かく見守っていただくか,やさしくご指摘頂けると助かります.
一応,自己紹介など
あまり Twitter ……もとい X を積極的にやっていないのもあって最近の人とは繋がりが少ない気がするので,軽く自己紹介をしておきますと,torus711 という ID でコンテストに参加しています.競技プログラミング自体は 10 年ぐらい前の TopCoder から始めましたが,AtCoder のレート推移を見るに現代の環境にはついていけていない感じがありますね.
自己紹介ついでにいくつか記事を紹介すると,
などがあります.
inlucde たち
#include <iostream> #include <iomanip> #include <sstream> #include <vector> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <functional> #include <iterator> #include <limits> #include <numeric> #include <utility> #include <type_traits> #include <cmath> #include <cassert> #include <cstdio>
古き良き(?) include ラッシュです.モダンな人は <bits/stdc++.h> を include する気がしますが,
- 現状ので十分揃っていて困っていない
- なんとなくコンパイルが遅そう(偏見)
みたいな理由でそのままにしています.
using
using namespace std; using namespace placeholders;
みんなやってるであろう using です.わたしは std::bind をちょこちょこ使うので,std に加えて std::placeholders も using しています.
型エイリアス
using LL = long long; using ULL = unsigned long long; using VI = vector< int >; using VVI = vector< vector< int > >; using VS = vector< string >; using ISS = istringstream; using OSS = ostringstream; using PII = pair< int, int >; using VPII = vector< pair< int, int > >; template < typename T = int > using LIM = numeric_limits< T >; template < typename T = int > using OSI = ostream_iterator< T >;
頻出でかつ長い気がする型名に別名を付けています.タイピング時間というよりは,入力に伴うストレスを気にしている感じです.
あっ,「頻出」とか書きましたが頻繁には使わないようなのが混ざってますね,はい.
std::cin, std::cout での std::vector の入出力
template < typename T > inline istream& operator>>( istream &s, vector< T > &v ) { for ( T &t : v ) { s >> t; } return s; } template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ) { for ( int i = 0; i < int( v.size() ); ++i ) { s << ( " " + !i ) << v[i]; } return s; }
(見やすさのために改行とインデントを入れています.)
かなり行儀が悪い*2ですが,operator>> と operator<< をオーバーロードして,std::cin と std::cout で std::vector を入出力できるようにしています.入力は多次元にも対応していて,出力はよくあるスペース区切りを採用しています.
遥か昔に書いたのですっかり忘れていたのですが,出力の方,
( " " + !i )
は何とも言い難いですね…….
変数宣言&入力
void in_impl(){}; template < typename T, typename... TS > void in_impl( T &head, TS &... tail ) { cin >> head; in_impl( tail ... ); } #define IN( T, ... ) T __VA_ARGS__; in_impl( __VA_ARGS__ );
変数の宣言と入力を一括で行えるようにしています.例えば,
IN( int, a, b, c );
と書くと int 型の変数 a, b, c を宣言して,この順で標準入力から読み込みを行います.
std::vector の生成
template < typename T, typename V > auto make_vector( const int n, const V &v ) { return vector< T >( n, v ); } template < typename T, typename... TS > auto make_vector( const int n, TS... ts ) { return vector< decltype( make_vector< T >( forward< TS >( ts )...) ) >( n, make_vector< T >( forward< TS >( ts )... ) ); }
std::vector を生成する関数テンプレートです.多次元のときに使うのがメインで,例えば
auto v = make_vector( 3, 4, 5, 42 );
とすると 3 次元の std::vector *3で,それぞれの次元の要素数が $3, 4, 5$ で,$42$ で初期化されたものが得られます.
文字列と他の型の変換
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; } template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }
文字列から任意の型・任意の型から文字列への変換です.std::to_string があるのでもはや後者はいらなそうですね.たぶん C++03 時代に書かれました.対称性の面から残しておいてもいいかな?
fromString は
auto a = fromString< int >( s );
のように型を指定して使います.
REP
#define NUMBERED( name, number ) NUMBERED2( name, number ) #define NUMBERED2( name, number ) name ## _ ## number #define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n ) #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
よくある REP マクロ(とそのヘルパ関数)です.それぞれ,
- REP1 : 指定の回数繰り返すだけ(ループ変数を参照しない)
- REP2 : $0$ から指定の値までカウントアップ
- REP3 : 指定の値から(別の)指定の値までカウントアップ
となっています.REP1 では見えなくてもループ変数は必要なので,行番号を使ってユニークな識別子を生成しています.
REP 系をどこまで用意するのかという点については人によって意見が分かれるかと思いますが,REP マクロの役割は大きく 2 つの側面があると思っていて,それは
- 「単純」なループが REP で書けるので,記述量が減るとともに typo による凡ミスを防げる
- 逆に,「単純」でないループが生のまま残るので,注視すべきポイントが分かりやすい
の 2 つです.
ではどこまでを「単純」とするかですが,わたしは後者もある程度重視しているので「$1$ ずつカウントアップするループ」までを単純だとして,上記 3 種だけを用意しています*4.
REP のインターフェース
#define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ )
REP という一つのマクロの引数の数によって REP1, REP2, REP3 を呼び分ける仕組みです.実際に引数を当て嵌めてみると分かりやすいですが,__VA_ARGS__ の中身の個数が変わることで後ろの引数がズレて,F に入るマクロが変わります.
FOR
#define FOR( e, c ) for ( auto &&e : c )
見たまま,range-based for の wrapper です.
ALL 系
#define ALL( c ) begin( c ), end( c ) #define AALL( a ) ( remove_all_extents< decltype( a ) >::type * )a, ( remove_all_extents< decltype( a ) >::type * )a + sizeof( a ) / sizeof( remove_all_extents< decltype( a ) >::type )
前者はよくあるやつで,std::begin, std::end をセットで使うのは頻出なのでまとめて書けるようにしています.
後者は生配列に対する ALL 的なものなのですがちょっと特殊で,多次元配列を平らにしてからその範囲を返します.わたしは DP 配列を生配列で用意することが多いので重宝しています.
size の wapper
#define SZ( v ) ( (int)( v ).size() )
コンテナの size の呼び出しに略称を付けつつ,int へのキャストを噛ませています.REP の継続条件に size をそのまま使うと unsigned int が返ってきて警告が出るので,それを消す的な意味合いです.
find の簡略化
#define EXISTS( c, e ) ( ( c ).find( e ) != ( c ).end() )
コンテナの find を使う存在判定が微妙に長いので短くしています.
chmin / chmax
template < typename T > inline bool chmin( T &a, const T &b ) { if ( b < a ) { a = b; return true; } return false; } template < typename T > inline bool chmax( T &a, const T &b ) { if ( a < b ) { a = b; return true; } return false; }
第一引数の値が第二引数の値より小さい or 大きいときに,第一引数の値をより小さい or 大きい値で更新します.ある種の DP の更新で頻出する他,「更新が発生したら true を返す」とすることで,BFS や Dijkstra 法で値をキューに入れるべきかどうかの判定に使えたりします.
その他略称系
#define PB push_back #define EM emplace #define EB emplace_back #define BI back_inserter #define MP make_pair #define fst first #define snd second
「ちょっと長いな」と思った名前たちの略称です.first, second は大して長くはないですが,Haskell の影響かも? 文字数が揃って縦に並べたときに見やすいというのもあるかも.
変数のダンプ
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
これはデバッグ用で,変数名とその中身を標準エラー出力に出力します.
後ろにセミコロンを付けないことによって更にチェインできて,主に
DUMP( x ) << endl;
のようにして空行を入れるのに使っています.
main 関数
int main() { cin.tie( nullptr ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; // {{ cursor }} return 0; }
上側の塊はよくあるやつで,
- std::cin を速くする
- 浮動小数点数の出力を小数点以下 12 桁に固定する
をしています.
下にある
// {{ cursor }}
は sniplate.vim のための記述で,sniplate.vim でこのテンプレを挿入すると,挿入モードになってこの位置にカーソルが来ます.これを利用するには,テンプレ全体を
// BEGIN SNIPLATE template // {{ abbr: my template }} // {{ class: util }} // {{ pattern: ^int\smain\(\) }}
と
// END SNIPLATE
で囲うなどする必要があります.
終わりに
ということで,わたしが普段使っているテンプレを晒してみました.何かの参考になれば幸いです.