[ コピペ OK ] AtCoder でたまに欲しくなる C++ ライブラリ

はじめに

この記事に載っているコードはコピペ OK です。著作権表示も書かなくて OK です。

競プロをやっていると、これライブラリにしてなかった〜みたいな計算をする機会が稀によくあります。というわけで、ここにはわざわざライブラリにするまでもないけど、コピペできたら便利みたいなコードを貼っていこうと思います。

注意

バグってたらごめんなさい。使用は自己責任ということで、よろしくお願いします。

メニュー

• 文字列 $\leftrightarrow$ 数
• 進数変換
• 日付の差分/数値化
• 区間の重複部分
• 円環上の移動

文字列 <-> 数

文字列と数を変換するやつです。

// string -> num
long long toInt(string s) {
    long long v; 
    istringstream ss;
    ss>>v;
    return v;
}
// string -> double
double toReal(string s){
    if(s.find('.') == s.size())return double(toInt(s));
    string t = s.substr(s.find('.')+1);
    return double(toInt(s.substr(0,s.find('.')))) + double(toInt(t))*pow(0.1,double(t.size()));
}
// num -> string
template<class T> // 少数の場合、精度を precision_ に渡す。
string toString(T x , unsigned int precision_ = 25){
    ostringstream sout;
    sout.precision(precision_);
    sout<<x;
    return sout.str();
}

進数変換

非負整数の基数を色々いじるやつです。ただし対応しているのは $36$ 進数までです。

計算テーブル

進数変換系ライブラリで共通してしようするデータです。冒頭にペタリするだけで OK です。

struct RadixTable{
private:
    static const int limit_ = 36;
    const string alphabets = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int alphabets_order[255];// [x] := 文字 x を 10 進法の値に直した値 ( 例えば D := 13 )
    public:
    RadixTable(){
        for(int i = 0 ; i < 255 ; i++)alphabets_order[i] = -1;
        for(int i = 0 ; i < limit_ ; i++)alphabets_order[alphabets[i]] = i;
    }
    // 小さい方から i 番目の記号 (0-index)
    char alphabet(int i){
        assert(0 <= i && i < limit_);
        return alphabets[i];
    }
    // 記号 c が小さい方から何番目か (0-index)
    int order(char c){
        assert(alphabets_order[c] != -1);
        return alphabets_order[c];
    }
    // 記号の種類数
    int limit(){return limit_;}
} RadixTable;   

3 種類の進数変換

文字列が整数を表す時、左から桁が大きいものとする ([$0$] が最大桁、back() が最小桁)。記号は $0$~$9$ と $A$~$Z$ の $36$ 文字。

// r 進数表記の 64 bit 整数を、10 進表記の整数型として返す。(1 進法は禁止)
unsigned long long toDecimal(string s , int r){
    assert(2 <= r && r <= RadixTable.limit());
    unsigned long long res = 0;
    unsigned long long digit = 1;
    reverse(s.begin() , s.end());
    for(char c : s){
        res += digit*RadixTable.order(c);
        digit*=r;
    }
    return res;
}

// 10 進整数 x を r 進数の文字列にして返す (1 進法は禁止)
string RadixConvert(unsigned long long x , int r){
    assert(2 <= r && r <= RadixTable.limit());
    string res = "";
    while(x > 0){
        res.push_back(RadixTable.alphabet(x%r));
        x/=r;
    }
    while(res.size() > 1 && res.back() == '0')res.pop_back();
    reverse(res.begin(),res.end());
    if(res.size()==0)res = "0";
    return res;
}

// p 進数表記の 64 bit 整数 s を、q 進数表記の 64 bit 整数を表す文字列に変換して返す
string RadixConvert(string s , int p , int q){
    assert(2 <= p && p <= RadixTable.limit());
    assert(2 <= q && q <= RadixTable.limit());
    return RadixConvert(toDecimal(s,p),q);
}   

日付の計算

西暦 $0$ 年 $1$ 月 $1$ 日 $0$ 時 $0$ 分 $0$ 秒 時点を基準として、そこからの時間の差分を計算する。ここで、グレゴリオ暦を採用して愚直計算している。

よって、グレゴリオ暦の採用 ($1582$ 年) 以前の日付の計算を含んでいるので、正確ではないかも。詳しくはわかりませんが、グレゴリオ暦の導入時に修正が入っているみたいなので、おそらく世界スタンダード通りかと。

また、大抵の場合はグレゴリオ暦の採用以降の日時の差分の計算に使用されるので、問題ない。

// グレゴリオ暦で、西暦 0 年 1 月 1 日 0 時 0 分 0 秒から、西暦 Y 年 Mo 月 D 日 H 時 Mi 分 S 秒までの経過時間を計算
// ただし、0/1/1 00:00:00 は数値計算用の絶対的な値として採用しているだけで、グレゴリオ暦は 1582 年スタートであることに注意
long long timecount(long long Y , long long Mo , long long D , long long H = 0 , long long Mi = 0 , long long S = 0){
    // datecount for month [x] := x月の日数。ただし閏年ではない
    static const int d4m[13] = {0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    static const int accum_d4m[14] = {0 , 0 , 31 , 59 , 90 , 120 , 151 , 181 , 212 , 243 , 273 , 304 , 334 , 365};// [x] := その年から x 月の初めまでの日数
    // キャスト用に long long にしておく
    static const long long h4d = 24;// 一日あたりの時刻数
    static const long long m4h = 60;// 一時間あたりの分数
    static const long long s4m = 60;// 一分あたりの秒数
    assert(0 <= Y);
    assert(1 <= Mo && Mo <= 12);
    if(Mo == 2 && ((Y%4 == 0 && Y%100 != 0) || Y%400 == 0))assert(1 <= D && D <= d4m[Mo]+1);
    else assert(1 <= D && D <= d4m[Mo]);
    assert(0 <= H && H <= 23);
    assert(0 <= Mi && Mi <= 59);
    assert(0 <= S && S <= 59);

    long long daycount = 0;
    if(Y>=1)daycount += (long long)((Y-1)/400)*366 + ((long long)((Y-1)/100)-(long long)((Y-1)/400))*365 + ((long long)((Y-1)/4)-(long long)((Y-1)/100))*366 + ((Y-1)-(long long)((Y-1)/4))*365;
    daycount += accum_d4m[Mo] + D - 1;
    if(Mo > 2 && ((Y%4 == 0 && Y%100 != 0) || Y%400 == 0))daycount += 1;
    return daycount*h4d*m4h*s4m + H*m4h*s4m + Mi*s4m + S;
}

// 0/1/1 から　Y/Mo/D までの日数 (!!!Y/Mo/D を含まない!!!)
// つまり、0/1/1 から何日経過すると Y/Mo/D になるかを計算
long long datecount(long long Y , long long Mo , long long D){
    return (long long)((timecount(Y,Mo,D)-timecount(0,1,1))/86400) + 1;
}

使用例としては、ある時点からある時点までの経過時間を知りたい時に使う。このとき、どちらの時点もグレゴリオ暦導入以降なら、先の懸念点は一切関係ない。

// 記事投稿日までに僕が生きた日数
std::cout << datecount(2024,10,20) - datecount(2000,1,6)<< std::endl;

2 つの区間の交差

$2$ つの半開区間 $[l1,r1)$ , $[l2,r2)$ に対して、交差判定と共通部分のサイズを計算する。

// 二つの区間 [ l1 , r1 ) と [ l2 , r2 ) が交差するか
template<typename T>
bool intersect(T l1 , T r1 , T l2 , T r2){
    return (l1 <= l2 && l2 < r1) || (l2 <= l1 && l1 < r2);
}

// 二つの区間 [ l1 , r1 ) と [ l2 , r2 ) の共通部分の大きさ
template<typename T>
T intersection_size(T l1 , T r1 , T l2 , T r2){
    if(!intersect_range(l1,r1,l2,r2))return 0;
    return min<T>(r1,r2)-max<T>(l1,l2);
}

円環上の移動

円周の長さが $S$ の円環上で、ある地点から右回りに $x$ 進んだ地点を地点 $x$ ということにする。ここで、地点 $S$ は地点 $0$ とする。

この円環で、地点 $a$ から地点 $b$ まで、地点 $c$ を通らずに移動する距離を計算する。

// 円周が S の円環上で地点 a から地点 b まで移動する最短距離
template<typename T>
T dist_on_ring(T a , T b , T S){
    if(a > b)swap(a,b);// 対称性より swap して OK
    return min<T>(b-a,a+S-b);
}
// 円周が S の円環上で地点 a から地点 b まで、地点 c を通らずに移動する距離
template<typename T>
T dist_on_ring(T a , T b , T c , T S){
    assert(a!=c && b!=c);// c と重複してしまう場合はエラー
    if(a > b)swap(a,b);// 対称性より swap して OK
    if(a < c && c < b)return a+S-b;
    return b-a;
}

最後に

これからも新しくいいのができたら追加していきます。