2019年08月27日00時22分56秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
cLay概要(version 20190827-1)
概要
C++っぽい言語をC++言語に変換します.
無駄にライブラリを張るのがめんどくさい,鬱陶しい,ライブラリを整備していても綺麗に書けない処理があるなどを解消したいというのが目的.目的の達成はそのうち….
blogにコード載せる時にライブラリとかincludeとかが長ったらしい,のをなんとかしたいというのも動機の1つです.
#include<bits/stdc++.h>およびgetchar_unlocked,putchar_unlockedなどを使用しているので,それが動かない環境だと動かないし,動かないコードが出てきます.
(その場合は,フラグの欄を見て下さい)
コードはこちら(最新版はこちら).C++っぽいコードを標準入力から食わせるとC++のコードが標準出力から出てきます.
未対応なもの
重要度が高い順に,下線付き太字,太字,普通です.重要度が低いものはそもそも対応させる気がないものが多いです.
この欄ではC++ではできるけど…というもの主にリストアップ.
- 構造体 [現在暫定対応]・共用体・クラス [現在暫定対応]・enum
- typedef,defineなどで型を定義するとやばい.他にも括弧使わないと表せない複雑な型(int (*hoge)[10];とか)はダメ
- キャストとかもやばいかも
- 関数を含む式の計算結果の型の推定がうまくいかないはず
- do-while文,最近のC言語/C++の仕様
- invalidなコードを食わせると多分落ちる
- validだけど不自然な書き方とか,他にも色々.書ききれない
制限
以下の単語は変数名などで使うとやばい.
基本的にバージョンアップするときは互換性を保ちたいけど,此処の欄は普通に増やす.
chmax, chmin,
ll, ull, mint, segtree, combination_mint,
rd, reader,
wt, wtLn, wtSp, wtN, wtF, wt_L, writer, writerLn, writerSp, writerN, writerF,
min, max, argmin, argmax, argminL, argmaxL,
gcd, GCD, lcm, LCM, sum, SUM, mul, MUL,
sortA,
reduceFraction, runLength,
wmem, memarr,
malloc1d, malloc2d, free1d, free2d, walloc1d, walloc2d,
int_inf, ll_inf, double_inf, MD, PI
色々
最初に
#include<bits/stdc++.h>
using namespace std;
が強制的に挿入されます.
#includeを書く必要はないですが,GCC以外で動かなくなる.
int main()は省略可能です.
いきなり関数の中じゃなくて{で始まるブロックが最初に出てきたときにint main()が補われます.
int main()で補われたブロック内の最後がreturn文でない場合は,return 0;が最後に補われます.
変数宣言の順番は勝手に変わります.
また,変数宣言はブロックの最初に移動します.
変数宣言と同時に初期化する場合に注意して下さい.
変数宣言をした場所で変数を宣言したい場合は,inplace_L 修飾子をつけるとその場所で宣言されます.
(また,初期値にループを使わないと計算できないものを指定すると,宣言はブロックの最初に移動しますが,初期値の代入はその場所で行われることがあります)
{ {
int i = 1, j = 2; int i = 1, j = 2;
j++; j++;
int a = i + j; inplace_L int a = i + j;
} }
は,それぞれ以下のようになります(必要部分だけ抜粋).
int a=i + j, i=1, j=2; int i=1, j=2;
j++; j++;
int a = i + j;
変数宣言や三項演算子 ? : を使っていない部分での,は(適切に{}を補った上で);に置き換えられます.
その結果,for(;;) i++, break; などと書くと for(;;){ i++; break; } に展開されます.
フラグ
途中で(プログラムの先頭が推奨)
//hogehoge
という形式でフラグを立てておくと色々な環境に対応させるために出力されるコードが変更されます.
- //no-unlocked : getchar_unlocked, putchar_unlocked が getchar, putchar に置き換わります.
- //no-gcd(), //no-GCD() : それぞれ gcd(), GCD() の機能を無効化します
- //no-lcm(), //no-LCM() : それぞれ lcm(), LCM() の機能を無効化します
- //no-min(), //no-MIN() : それぞれ min(), MIN() の機能を無効化します(min[]()の機能は有効のままです)
- //no-max(), //no-MAX() : それぞれ max(), MAX() の機能を無効化します(max[]()の機能は有効のままです)
- //no-sum(), //no-SUM() : それぞれ sum(), SUM() の機能を無効化します
- //no-mul(), //no-MUL() : それぞれ mul(), MUL() の機能を無効化します
またmint構造体など使用すると挿入される関数や構造体を挿入されなくするフラグは以下の通りです.
例えば,//no-insert-mintを指定するとmint型が使えなくなる代わりに,mintという変数や関数などを自由に宣言することができるようになります.
- //no-insert-stdc : #include<bits/stdc++.h>
- //no-insert-namespace : using namespace std;
- //no-insert-define_MD : #define MD 1000000007
- //no-insert-define_PI : #define PI 3.14159265358979323846
- //no-insert-workmemory
- //no-insert-workmemory_init
- //no-insert-walloc1d
- …
型
llはlong longに,ullはunsigned long longに置き換えられます.
mint型が使えます.
mod MDで計算します(MDは#define MD hogeで定義しなければデフォルトでは10^9+7が使用されます.MDは素数でなければ上手く動かない可能性があります.定数の項も参照のこと).
四則演算(割り算も)は使えます.int型やll型などと計算すると結果はmint型になります.
mint型の法の設定などはmain関数の変数宣言後に行うので,変数制限時に代入などすると上手く動かないので,変数制限時に代入するのは避けたほうが良いです.
mint x; x = 1; x /= 2; wt(x); で 500000004 が表示されます.
また,べき乗 pw が使えます.
mint x, p; x = 2; p = x.pw(100); で p に $2^{100} \bmod (10^9+7)$ が代入されます.
mintの詳しい仕様はそのうち書きます.
モンゴメリ乗算を使用しないmodint型もあります.
MDが素数でなくても,割り算をしなければmodint型は動くと思います.
mint型とmodint型はほぼ同じ使用方法です.
入出力
rd(i, j, k)で標準入力からi,j,kが読み込まれます.scanf("%d%d%d",&i,&j,&k);などと似た感じですが,スペース区切りじゃなく,数字以外で区切られます.
rd(i, j(n), k)はrd(i, j[0], j[1], ..., j[n-1], k)に置き換わります(左から処理するのでrd(n, A(n))とか可能です).
また,rd(N, (A,B)(N)) は rd(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります.グラフのエッジの入力とかに.
rdの代わりにreaderでもOK.
rdは今のところint型,ll型,double型,mint型,char型(1文字),char型の配列(文字列),string型にのみに対応.他の型もそのうち対応.
また,char S[1000]; int N; rd(S@N);で文字列 S を読み込むと同時に文字列の長さを N に代入します.複数の文字列の場合は char S[10][1000]; int N[10]; rd(S@N(10)); とS@Nはひとかたまりで扱います.
char型1文字の入力の場合も,空白などは読み飛ばして,次の空白でない文字を読み込みます.
rd(i--) は rd(i); i--; になります.++もできます.2減らすなら rd(i----) です.
rd((A--)(N)) は配列AのN個の要素すべてが1減ります.カッコは必須です.rd(A--(N)) は書けません.
rd((A--,B--,C)(N)) は配列A,Bの要素は1減り,Cの要素はそのままです.
1-originから0-originに直しながら入力するときなど.
int len; char buf[100];
len = rdLine(buf); で1行の読み込みを行います.
正確には,\n か EOF に出くわすまでbufに入れていきます(\nは入らない)が,\rだけは無視されます.
lenには基本的に読み込んだ文字数を返しますが,1文字も読み込まずEOFに出くわした場合のみ-1を返します.
bufの最後の文字の次に \0 を入れて返します.
wt(i, j, k)でスペース区切りでi, j, kを標準出力に吐き出し,改行します.
wt(i, j(n), k)はwt(i, j[0], j[1], ..., j[n-1], k)に置き換わります.
また,wt(N, (A,B)(N)) は wt(N, A[0], B[0], A[1], B[1], ..., A[N-1], B[N-1]) に置き換わります.式の一部がこの形でも同様に置き換わります(以下の例を参照).
最後に改行する代わりにスペースを出力する場合はwtの代わりにwtSpを,改行区切りで出力する場合はwtLnを使います.また区切りに何も出力しない場合はwtNを使います.
wtの代わりにwriter,wtSpの代わりにwriterSp,wtLnの代わりにwriterLnでもOK.
wtは今のところint型,ll型,double型,mint型,char型の配列(文字列)のみに対応.他の型もそのうち対応.
wtFは文字列を出力しますが,変数名を{}で囲むと,その変数の値に置換されて出力されます.文字列中で{または}を出力したい場合はエスケープして\{または\}と書きます.
また,出力に関してオプションで B=n と指定すると整数系のものは n 進数で出力されます.
例えば,wt[B=3]("hello", 10); は hello 101 と出力されます(文字列に関しては基数は無視されます).
62進数まで指定可能で,文字は 01...9ABC...Zabc...z の順番です.
例:
int N, A[10], B[10], res[10];
rd(N, (A,B)(N));
wt(N, 2*res(N)+1);
は以下と同じ意味になります.
int i, N, A[10], B[10], res[10];
scanf("%d", &N);
for(i=0;i<N;i++) scanf("%d%d", A+i, B+i);
printf("%d ", N);
for(i=0;i<N;i++) printf("%d%c", 2*res[i]+1, i==N-1?'\n':' ');
また
int T = 0, res = 10;
wtF("\{Case {++T}: {res}\}\n");
は以下と同じ意味になります.
int T = 0, res = 10;
printf("{Case %d: %d}\n", ++T, res);
また
int N, L[10];
char S[10][1000];
rd(N, S@L(N));
は以下と同じ意味になります.
int i, N, L[10];
char S[10][1000];
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%s",S[i]);
L[i] = strlen(S[i]);
}
標準入出力ではない場合は,readerFile(),writerFile()を利用して入出力先を指定します.
ファイル名(勝手にfopen, fcloseされる)かファイルポインタを引数に指定します.
int i, j, k;
rd(i); // stdinから読み込み
readerFile("input.txt");
rd(j); // input.txtから読み込み
readerFile();
rd(k); // stdinから読み込み
wt(i); // stdoutに書き込み
writerFile("output.txt");
wt(j); // output.txtに書き込み
writerFile("log.txt", "a");
wt(k); // log.txtに追加で書き込み "a"モードで開く
writerFile(stderr);
wt("hoge"); // stderrに書き込み
ループ
rep(i,n)およびREP(i,n)はfor(i=0;i<n;i++)に置き換えられます.
rep(i,a,b)およびREP(i,a,b)はfor(i=a;i<b;i++)に置き換えられます.
また,この際,変数iが宣言されていなかった場合,勝手にint型の変数として宣言されます.
また,括弧内((),[],{}のどれか)で2つ以上のドットで区切ると範囲を指定でき,勝手にループに展開されます.
ドットの数が等しいものが同じ変数だと思われて,同じドットの数のものは2回目以降に登場したときには区間の終わりは省略可能です.
(ドットの数が少ない方が内側のループになります.2次元配列のアクセス順で速度がかなり変わるので気をつけたほうが良い場合があります)
例えば,単位行列を作るコード,行列のコピーのコード,転置しながらコピーするコードは
int A[10][10], B[10][10], C[10][10];
A[0...9][0..9] = 0;
A[0..9][0..9] = 1;
B[0...9][0..9] = A[0...9][0..9];
C[0...9][0..9] = A[0..9][0...9];
のように書け,これは
int i, j, A[10][10], B[10][10];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) A[i][j] = 0;
for(i=0;i<=9;i++) A[i][i] = 1;
for(i=0;i<=9;i++) for(j=0;j<=9;j++) B[i][j] = A[i][j];
for(i=0;i<=9;i++) for(j=0;j<=9;j++) C[i][j] = A[j][i];
と同値です(B[0...9][0..9] = A[0...9][0..9];はB[0...9][0..9] = A[0...][0..];と書くこともできます).
括弧で囲まれていなければならないことに注意して下さい.
A[0..9] = (0..9)
B[0..9] = 50 - (23..)
は
for(i=0;i<=9;i++) A[i] = i;
for(i=0;i<=9;i++) B[i] = 50 - (23 + i);
と同値ですが, A[0..9] = 0..9; などとは書けません.
文字列の中に2個以上ドットが並ぶとバグる実装なのでそのうちなんとかする.
演算子
昔のGCC拡張で存在した<?および>?演算子の同時に代入するバージョンのみ使えます.
つまり,a <?= b; は a = min(a, b); と,a >?= b; は a = max(a, b); と大体同じです.
代入しないバージョンは素直にminおよびmaxを使え.
正の整数に関する繰り上げの割り算演算子 /+ が使えます.
13 /+ 3 は 5 となります.
実際には a /+ b は (a+b-1) / b で定義され,正の整数でないと繰り上げ割り算になる保証はありません.
また,a+b-1 がオーバーフローする可能性があるので要注意です.
負の数を正の数で割った余りを非負の数で返す %% 演算子があります.
(-5) %% 2 は 1 になります.
演算子の優先順位が低いので,-5 %% 2 は-(5 %% 2) = -1になります.
a = a %% b; は a %%= b; と書くこともできます.
べき乗演算子 ** が使えます.
2 ** 3 は $2^3 = 8$ を表します.
点 (x1, y1) と (x2, y2) とのユークリッド距離は sqrt( (x1-x2)**2 + (y1-y2)**2 ) と簡潔に書けるようになります.
バイナリ法を使用します.
x ** y において,y は非負整数である必要があって,結果の型は x の型と同じになります(y が非負整数じゃない場合は標準の pow 関数などを使って下さい).
a = a ** b; は a **= b; と書くこともできます.
数値の後の掛け算の演算子*は省略できることがあります.
z = 2 2x+2(x+5); で z = 2 * 2 * x + 2 * (x+5); の意味になります.
他の解釈ができる場合は*を省略できません.
2u は 2*u ではなくunsigned 型の定数 2 で,3d1 は 3*10 = 30 を表す整数で 3 * d1 などにはなりません.
数値はアルファベットで終わっている場合は,*を(現状では)省略できません.
z = 2u x; は駄目です.
また,数値の後以外の*の省略は(現状では)できません.
例えば,x(x+y) や (2)(x+y) に * が補われることはありません.
また,単純に*が補われるだけなので,x=2 のときに 7%2x は 7%2*x=1*2=2 となることに注意してください(7%(2x)ではない).
等式,不等式の条件を続けるときに && を省略できます.
if(5 < x+y < 10) は if(5 < x+y && x+y < 10) に置き換わります.
if(i <= 5 < k <= 12 > j != m == n) は if(i <= 5 && 5 < k && k <= 12 && 12 > j && j != m && m == n) に置き換わります.
if(5 < x++ < 10) は if(5 < x++ && x++ < 10) に置き換わるので注意してください.
ただし,< hoge > の場合は,テンプレート絡みなどで使用することがあるので,この場合のみ展開されません.
定数
int_inf は 1073709056 ($2^{30}-2^{15}$) に,
ll_inf は 4611686016279904256LL ($2^{62}-2^{31}$) に,
double_inf は 1e150 に置換されます.
int_infおよびll_infはそれぞれ2倍してちょっとした数を足してもint型,long long型でオーバーフローしないという値に設定しています.
また,double_infは2乗してもオーバーフローしないという値に設定しています.
また,MDは1000000007($10^9+7$)に,PIは3.14159265358979323846(円周率)に置換されます(厳密には最初に#define MD 1000000007などが追加されます).
MDとPIはコード中で #define MD 1000000009 などと言う記述が出てきたら置換されずそちらが優先されます.
また,double型の定数の書き方 1e-5 などと同様に,整数型の定数を 1d5 などと書けます.
$x$d$y$ で $\lfloor x \times 10^y \rfloor$ を表します.
$2^{31}$ 未満であれば int 型,$2^{31}$ 以上であれば ll 型,$2^{63}$ 以上であれば ull 型の定数になり,$2^{64}$ 以上の値だと上手く動きません.
$y$ は整数で $-30$ 以上 $30$ 以下でないと正しく動きません.
ワーキングメモリ
ワーキングメモリを必要な関数や機能などを使うと勝手にワーキングメモリを確保します.
void *wmem; に(デフォルトで)96,000,000バイトのメモリが確保されます.
行列
行列は Matrix<mint> m; などで定義します.
m[0][1] で0行1列の成分にアクセスできます(行番号,列番号は0から始まる).
行列の足し算,引き算,かけ算は+,-,*でできます.べき乗演算子 ** なども使えます.定義できない演算をすると0行0列の行列になります.
int, ll, doubleの定数倍も可能です.
m = 1; などと定数を代入すると対角成分が1に,それ以外は0になります.
以下は Matrix<T> でに関してです.
コンストラクタ
- Matrix(): 0行0列の行列
- Matrix(const int rr, const int cc): rr行cc列の行列.要素の初期化はされない.
- Matrix(const Matrix<T> &a)
その他
- void m.changeSize(const int rr, const int cc): 行列のサイズをrr行cc列に変更
Fenwick Tree (Binary Indexed Tree, BIT)
(1次元の)Fenwick treeが使えます.
fenwick<int> t; などで定義します.この場合は各要素や和などを求める時に全てint型で計算されます.
扱う配列の長さの最大値を maxN として,t.malloc(maxN); または t.walloc(maxN); でメモリを確保します.
その後,配列の長さが N の場合に初期化(全要素を0にする)場合,t.init(N); とします.
使える感じの関数は以下の通り(要素数を $N$ として,0番目の要素から$N$-1番目の要素まで存在します):
- t.add(a, val): a番目の要素の値に val を加えます.$O(\log N)$ 時間.
- t.get(a): 0番目の要素,1番目の要素,…,a番目の要素の和を返します.$O(\log N)$ 時間.
- t.range(a, b): a番目の要素,a+1番目の要素,…,b番目の要素の和を返します.$O(\log N)$ 時間.
- t.kth(v): 各要素は全て非負のとき,t.get(a)がvを超える最小のaを求めます.下の例も参照.$O((\log N)^2)$ 時間,現在は良くない実装.
区間は閉区間 [a,b] の形で指定することに注意して下さい.
malloc()を使った場合のメモリの開放は t.free(); です.
{
int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
int arr[20];
int i, s;
fenwick<int> t;
t.walloc(10);
t.init(10);
rep(i,10) t.add(i,d[i]);
s = t.get(3);
wt(s); // d[0]+d[1]+d[2]+d[3] = 3+1+4+1 = 9
s = t.range(5,7);
wt(s); // d[5]+d[6]+d[7] = 9+2+6 = 17
rep(i,20) arr[i] = t.kth(i);
wt(arr(20)); // 0がd[0]個,1がd[1]個,…からなる配列のk番目の要素
// 0 0 0 1 2 2 2 2 3 4 4 4 4 4 5 5 5 5 5 5
}
バイナリヒープ(priority_queueとほぼ同様)
Heap<T> h; もしくは Heap_max<T> hm; で宣言する.
Heapは通常の最小値を取り出せるやつ,Heap_maxは最大値を取り出せるやつ.
大体の操作は $O(\log size)$.
Heap<T> h; について:
- int h.size : ヒープに入っている要素数.
- void h.malloc(const int N) : mallocを使ってN要素分を格納できるだけのメモリを確保.ヒープの中を空に設定する.
- void h.walloc(const int N, void **mem = &wmem) : ワーキングメモリを使ってN要素分を格納できるだけのメモリを確保.ヒープの中を空に設定する.
- void h.free() : mallocで確保したメモリを解放します.
- void h.init() : ヒープを空にします(h.size = 0).
- T h.top() : ヒープの中にある最小値を返します.
- T h.pop() : ヒープの中にある最小値を削除し,その値を返します.
- T h.push(const T x) : ヒープの中にxを入れます.
Heap_max<T> hm; について:
- int hm.size : ヒープに入っている要素数.
- void hm.malloc(const int N) : mallocを使ってN要素分を格納できるだけのメモリを確保.ヒープの中を空に設定する.
- void hm.walloc(const int N, void **mem = &wmem) : ワーキングメモリを使ってN要素分を格納できるだけのメモリを確保.ヒープの中を空に設定する.
- void hm.free() : mallocで確保したメモリを解放します.
- void hm.init() : ヒープを空にします(h.size = 0).
- T hm.top() : ヒープの中にある最大値を返します.
- T hm.pop() : ヒープの中にある最大値を削除し,その値を返します.
- T hm.push(const T x) : ヒープの中にxを入れます.
バイナリヒープ(固定長配列用)
LHeap<int> などで宣言.
$N$ 要素の配列 $A_k = \verb|val[k]|$ を考える.
ヒープにある要素を入れたり値を変えたり($\verb|change|$),ヒープの中に入っている最小の要素を取り出して取り出した要素の番号を返したり($\verb|pop|$)する.
大体の操作の計算時間 $O(\log N)$.
よく使いそうなもの:
- $\verb|malloc(int N)|$:$N$ 要素分のメモリを確保
- $\verb|walloc(int N, void **mem=&wmem)|$:$\verb|mem|$ から $N$ 要素分のメモリを確保して,次のアドレスを返す
- $\verb|free(void)|$:$\verb|malloc(int N)|$で確保したメモリの解放
- $\verb|init(int N)|$:初期化.今後 $N$ 要素の配列を使う.ヒープの中は空.
- $\verb|change(int n, T v)|$:$A_k = v$ に変更する.ヒープに入っていない要素ならヒープに突っ込み,入っている要素だったら,適切な市に移動する.
- $\verb|pop(void)|$:ヒープに入っている最小の要素のインデックスを返し,その要素を消す.最小が $A_k$ なら $k$ を返す.
- $\verb|int size|$:ヒープに入っている要素の数.
- $\verb|int hp[]|$:$\verb|hp[k]|$ でヒープに入っている $k$ 番目の要素のインデックス.$\verb|pop()|$ で取り出される要素のインデックスは $\verb|hp[0]|$.
- $\verb|T val[]|$:$A_k$ の値 $\verb|val[k]|$.
そうではないもの:
- $\verb|int place[]|$:$\verb|place[k]|$ は $A_k$ がヒープに入っているならその位置,入っていないなら $-1$.
int i;
double v;
LHeap<double> hp;
hp.walloc(10);
hp.init(10);
hp.change(0, 100.0);
hp.change(1, 200.0);
hp.change(8, 80.0);
hp.change(1, -200.0);
hp.change(8, 150.0);
while(hp.size){
i = hp.pop(); // 1 -200.000000000000000
v = hp.val[i]; // 0 100.000000000000000
wt(i,v); // 8 150.000000000000000
}
バイナリヒープ(ダイクストラ用)
DijkstraHeap<int> などで宣言.
バイナリヒープ(固定長配列用)のダイクストラ用にチューニングしたもの.
$\verb|pop|$ した時に $\verb|visited[]|$ のフラグを立てる,更新時に訪れたものや長くなったものは更新しないなどを関数の中で判定する.
よく使いそうなもの:
- $\verb|malloc(int N)|$:$N$ 要素分のメモリを確保
- $\verb|walloc(int N, void *mem)|$:$\verb|mem|$ から $N$ 要素分のメモリを確保して,次のアドレスを返す
- $\verb|free(void)|$:$\verb|malloc(int N)|$で確保したメモリの解放
- $\verb|init(int N)|$:初期化.今後 $N$ 要素の配列を使う.ヒープの中は空
- $\verb|change(int n, T v)|$:$A_k$ を既に処理していないなら,$A_k = \min(A_k, v)$ に変更する.ヒープに入っていない要素ならヒープに突っ込み,入っている要素だったら,適切な市に移動する
- $\verb|pop(void)|$:ヒープに入っている最小の要素のインデックスを返し,その要素を消す.最小が $A_k$ なら $k$ を返す
- $\verb|int size|$:ヒープに入っている要素の数
- $\verb|int hp[]|$:$\verb|hp[k]|$ でヒープに入っている $k$ 番目の要素のインデックス.$\verb|pop()|$ で取り出される要素のインデックスは $\verb|hp[0]|$
- $\verb|T val[]|$:$A_k$ の値 $\verb|val[k]|$
- $\verb|char visited[]|$:$A_k$ を始点とする枝たちを処理したなら $1$,そうでないなら $0$
そうではないもの:
- $\verb|int place[]|$:$\verb|place[k]|$ は $A_k$ がヒープに入っているならその位置,入っていないなら $-1$.
int i;
double v;
DijkstraHeap<double> hp;
hp.walloc(10);
hp.init(10);
hp.change(0, 100.0);
hp.change(1, 200.0);
hp.change(8, 80.0);
hp.change(1, -200.0);
hp.change(8, 150.0);
while(hp.size){
i = hp.pop(); // 1 -200.000000000000000
v = hp.val[i]; // 8 80.000000000000000
wt(i,v); // 0 100.000000000000000
}
セグメントツリー
(1次元の)セグメントツリーが使えます.
segtree<int> t; などで定義します.この場合は各要素や和などを求める時に全てint型で計算されます.
1回のみ使用する場合は,配列の長さを N として t.malloc(N, 1); とすると,配列の要素が全て 0 で初期化され,セグメントツリーが使えるようになります.
何回も使いまわす可能性がある場合は,配列の長さの最大値を maxN として,t.malloc(maxN); でメモリを確保します.
その後,配列の長さが N の場合にセグメントツリーを使えるようにするためには,t.setN(N); で使えるようになります.
mallocの代わりにwallocでワーキングメモリを使ってメモリを確保します.
0以外で初期化したい場合は,t.setN(N,0,0);(各要素は全く初期化されない),または,t.setN(N,1,0); (各要素は一応0で初期化される)としておき,
t[hoge] = 要素hogeの初期値;
と適当に初期化した後,t.build();とすれば使えるようになります.
使える感じの関数は以下の通り(要素数を $N$ として,0番目の要素から$N$-1番目の要素まで存在します):
- t.change(a, b, val): a番目の要素,a+1番目の要素,…,b-1番目の要素の値を val にします.$O(\log N)$ 時間.
- t.add(a, b, val): a番目の要素,a+1番目の要素,…,b-1番目の要素の値に val を加えます.$O(\log N)$ 時間.
- t.getSum(a, b): a番目の要素,a+1番目の要素,…,b-1番目の要素の和を返します.$O(\log N)$ 時間.
- t.getMin(a, b): a番目の要素,a+1番目の要素,…,b-1番目の要素の (最小値, その最小値を実現する最初の要素の番号) を返します.$O(\log N)$ 時間.
- t.getMinVal(a, b): a番目の要素,a+1番目の要素,…,b-1番目の要素の最小値を返します.$O(\log N)$ 時間.
- t.getMinInd(a, b): a番目の要素,a+1番目の要素,…,b-1番目の要素の最小値を実現する最初の要素の番号を返します.$O(\log N)$ 時間.
区間は最初は含むが最後は含まない [a,b) の形で指定することに注意して下さい.
malloc()を使った場合のメモリの開放は t.free(); です.
グラフ(構造体)
graph構造体を使えます.graph g; などで定義します.
- int g.N : ノード数
- int *g.es : g.es[i] はノード i から出ている枝の本数
- int **g.edge : g.edge[i][j] はノード i から出ている j 番目の枝が向かう先のノード番号
- void g.setEdge(int N, int M, int A[], int B[], void **mem=&wmem) : ノード数 N,枝数 M の無向グラフをセット(g.N, g.es, g.edgeを書き換え)します.(A[i], B[i])間に枝があります.ワーキングメモリを使用し,wmemは使用した分勝手に進みます.
- void g.setDirectEdge(int N, int M, int A[], int B[], void **mem=&wmem) : ノード数 N,枝数 M の有向グラフをセットします.A[i]からB[i]に向かう枝があります.ワーキングメモリを使用し,wmemは使用した分勝手に進みます.
- graph g.reverse(void **mem=&wmem) : 枝の向きを逆にしたグラフを返す
- void g.getDist(int root, int res[], void *mem=wmen) : ノードrootから各ノードまでの距離をBFSで求めます.辿り着けないノードまでの距離は -1 を返します.ワーキングメモリを使います.
- graph g.reduce(int tn, int ind[], int self_e = 0, int dep_e = 0, void **mem = &wmem) : ノード i を新しくノード番号を ind[i] と付け替えたグラフを返します.複数のノードを1つにまとめることができます.ind[i]=-1とするとノードiは消えます.self_e=0なら結果のグラフでセルフループとなる枝は削除されます.dep_e=0なら結果のグラフで同じノード間をつなぐ枝が複数あるなら1つを残し削除されます.tnは返すグラフのノード数です.
- int g.scc(int res[], void *mem = wmem) : 強連結成分分解.強連結の数が戻り値として返し,res[i]はノードiが何番の強連結に属すか返す.
- int g.bcc(int res[], void *mem = wmem) : 二重連結成分分解.二重連結の数が戻り値として返し,res[i]はノードiが何番の二重連結に属すか返す.
- int g.shortestPath(const int s, const int t, int res[], void *mem=wmem) : ノードsからノードtへの最短路の1つをbfsで求める.戻り値は距離.戻り値3,配列 res={s,0,1,t} のような感じで,配列は距離+1個の要素になる.たどり着けないなら-1を返す.
- int g.TopologicalSort(int res[], void *mem=wmem) : トポロジカルソートした結果をresに格納する.i < j ならノードres[j]からノードres[i]に枝はない.成功したら1を返し,グラフがDAGじゃない場合は0を返す.
- int g.shortestUndirectedCycle_length(void *mem=wmem) : 無向グラフに対して長さ最小のサイクル(同じ枝を2回通らない)の長さを求める.自己ループがあれば1,多重枝があれば2,サイクルが存在しなければ-1を返す.時間計算量は $O(N(N+M))$.
{
int N = 6, M = 7; // 0 → 1 ← 2
int A[7] = {0, 0, 1, 2, 3, 4, 5}; // | ^ |
int B[7] = {1, 3, 2, 5, 4, 1, 4}; // v | v
// 3 → 4 ← 5
int i;
graph g;
int dist[6];
g.setEdge(N, M, A, B); // node 0: degree 2: 1 3
rep(i,N){ // node 1: degree 3: 0 2 4
wtF("node {i}: degree {g.es[i]}: "); // node 2: degree 2: 1 5
wt(g.edge[i](g.es[i])); // node 3: degree 2: 0 4
} // node 4: degree 3: 3 1 5
// node 5: degree 2: 2 4
g.getDist(3, dist);
wt(dist(N)); // 1 2 3 0 1 2
g.setDirectEdge(N, M, A, B); // node 0: degree 2: 1 3
rep(i,N){ // node 1: degree 1: 2
wtF("node {i}: degree {g.es[i]}: "); // node 2: degree 1: 5
wt(g.edge[i](g.es[i])); // node 3: degree 1: 4
} // node 4: degree 1: 1
// node 5: degree 1: 4
g.getDist(3, dist);
wt(dist(N)); // -1 2 3 0 1 4
}
枝に重みのあるグラフ(構造体)
wgraph構造体を使えます.wgraph<T> g; などで定義します.
- int g.N : ノード数
- int *g.es : g.es[i] はノード i から出ている枝の本数
- int **g.edge : g.edge[i][j] はノード i から出ている j 番目の枝が向かう先のノード番号
- T **g.cost : g.cost[i][j] はノード i から出ている j 番目の枝の重み
- graph g : 枝の重みを無視したグラフ
- void g.setEdge(int N, int M, int A[], int B[], T C[], void **mem=&wmem) : ノード数 N,枝数 M の無向グラフをセット(g.N, g.es, g.edgeを書き換え)します.(A[i], B[i])間に枝があります.ワーキングメモリを使用し,wmemは使用した分勝手に進みます.
- void g.setDirectEdge(int N, int M, int A[], int B[], T C[], void **mem=&wmem) : ノード数 N,枝数 M の有向グラフをセットします.A[i]からB[i]に向かう枝があります.ワーキングメモリを使用し,wmemは使用した分勝手に進みます.
- template<class S> void g.getDist(int root, S res[], S unreachable = -1, void *mem=wmen) : ノードrootから各ノードまでの距離をダイクストラ法で求めます.辿り着けないノードまでの距離は unreachable を返します.ワーキングメモリを使います.
- template<class S> void g.getDistForest(int root, S res[], S unreachable = -1, void *mem=wmen) : 森の場合,ノードrootから各ノードまでの距離をBFSで求めます.辿り着けないノードまでの距離は unreachable を返します.ワーキングメモリを使います.
- template<class S> void g.BellmanFord(int root, S res[], S unreachable = -1, S minusInf = -2, int step = -1, void *mem = wmem) : ノードrootから各ノードまでの距離をBellman-Ford法で求めます.辿り着けないノードまでの距離は unreachable を,負閉路のためいくらでも距離が短くなる場合は minusInf を返します.stepが-1でなければ,rootからstep回以下移動する場合の最短距離を返します(minusInfにはならない).ワーキングメモリを使います.
- T g.MST_Prim_cost(void *mem = wmem) : 無向グラフだと仮定して,最小全域木の重み和を返す.Prim法を使う.
- int g.MST_Prim_cost(T &res, void *mem = wmem) : 無向グラフだと仮定して,最小全域木の重み和をresに代入して求める.戻り値は全域木が存在するなら1,存在しないなら0を返す.Prim法を使う.
Heavy-Light Decomposition(HLD,重軽分解)
根付き無向木に対してHeavy-Light Decomposition(HLD)を計算します.
根はノード0を利用します.
計算したHLDを用いて,LCAなどを高速に求めることができます.
また,segtreeを載せることができます.
HLD hld; で定義したとします.
- void hld.init(graph g, void **mem = &wmem) : グラフ g をセットします.以降で graph g を破壊しないでください.
- int hld.lca(int x, int y) : ノードxとノードyのLCAを求める.$O(\log N)$ 時間.
- int hld.depth(int x) : ノードxの深さ(ノード0からの距離)を求める.$O(\log N)$ 時間.
- int hld.dist(int x, int y) : ノードxとノードyの間の距離を求める.$O(\log N)$ 時間.
- int hld.up(int x, int d = 1) : ノードxのd世代親のノード番号を求める.存在しないなら-1.$O(\log N)$ 時間.
以下 HLD hld; の多分使わない情報.
- int hld.N : ノード数.graphと同じ.
- int *hld.es : 次数.graphと同じ.
- int **hld.edge : 枝.graphと同じ.
- int groupNum : グループ(Lightの枝で結ばれるパス)の数
- int *groupSize : i番目のグループに属するノード数が groupSize[i]
- int **groupNode : i番目のグループに属するj番目のノード番号が groupNode[i][j]
- int *groupUpNode : i番目のグループから根に向かってHeavyの枝を伝って登った先のノード番号が groupUpNode[i](一番上のグループなら-1)
- int *groupDepth : グループを1つのノードと見たときに,i番目のグループの根からの距離 groupDepth[i]
- int *group : ノードiが属するグループ番号が group[i]
- int *groupind : ノードiはグループ group[i] の groupind[i] 番目のノード
Fenwick treeを載せるときは,HLD_fenwick<T> t; を定義します.
ノードに値を持ちます.
(枝に値をもたせたい場合は,すぐ上に向かう枝の値をノードに持たせて,LCAでパスを分割したりするとできるかも)
- void t.init(HLD *hld__, void **mem = &wmem) : 初期設定.全節点は0で初期化されます.
- void t.add(int u, int v, T val) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値にvalを足します
- T t.get(int u, int v) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値の和を求めます
以下 HLD_fenwick<T> t; の多分使わない情報.
- HLD *t.hld : そうです.
- fenwick<T> *fen : fen[i]はグループiのfenwickです.
segtreeを載せるときは,HLD_segtree<T> t; を定義します.
ノードに値を持ちます.
(枝に値をもたせたい場合は,すぐ上に向かう枝の値をノードに持たせて,LCAでパスを分割したりするとできるかも)
- void t.init(HLD *hld__, T initval[], void **mem = &wmem) : 初期設定.initval[i] はノード i の初期値です.0で初期化するなら initval は NULL でも良い.
- void t.change(int u, int v, T val) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値をvalに置き換えます
- void t.add(int u, int v, T val) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値にvalを足します
- T t.getSum(int u, int v) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値の和を求めます
- pair<T,int> t.getMin(int u, int v) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値の(最小値,その最小値を達成するノード番号の1つ)を求めます
- T t.getMinVal(int u, int v) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値の最小値を求めます
- int t.getMinInd(int u, int v) : ノードuからノードvに向かうバス上の全てのノード(uもvも含む)の値の最小値を達成するノード番号の1つを求めます
以下 HLD_segtree<T> t; の多分使わない情報.
- HLD *t.hld : そうです.
- segtree<T> *seg : seg[i]はグループiのsegtreeです.
最大流(maxflow, Dinic)
最大流は maxflow<int,ll> flow; などで定義します.この場合,各辺の流量は int 型ですが,合計で流れる流量は ll 型です.
以下の説明では maxflow<T,S> flow; とします.
- int flow.node : ノード数
- T flow.eps : これ以下だと 0 だと思う閾値(S = double のときなどに使われる,デフォルトだと 1e-9.init() 関数,setGraph() 関数などでセットされる)
- int *flow.es : flow.es[i] でノード i から出ている枝の本数
- int **flow.edge : flow.edge[i][j] はノード i から出ている j 番目の枝が向かう先のノード番号
- int **flow.rev : ノード i から出ている j 番目の枝の逆向きの枝がノード j から出ている flow.edge[i][j] 番目の枝
- T **flow.flow : ノード i から出ている j 番目の枝にそって後どれぐらい流せるか
- flow.malloc(int N) : ノード数 N のグラフを確保できるメモリを確保(枝の分のメモリは確保しない)
- flow.walloc(int N, void**mem = &wmem) : ノード数 N のグラフを確保できるメモリを確保(枝の分のメモリは確保しない)
- flow.init(int N) : グラフを初期化,ノード数を N に設定
- flow.addEdge(int n1, int n2, T f1, T f2 = 0) : ノード n1 から n2 に向かって流量 f1,ノード n2 から n1 に向かって流量 f2 の枝を張る
- flow.setGraph(int N, int M, int n1[], int n2[], T f1[], T f2[]) : ノード数 N,枝数 M のグラフを設定
- void setGraph_w(int N, int M, int n1[], int n2[], T f1[], T f2[], void **mem = wmem) : ノード数 N,枝数 M のグラフを設定
- S solve(int st, int ed) : ノード st からノード ed までflowを流して,流れた量を返す
以下のコードは http://www.spoj.com/problems/FASTFLOW/ を解くコード.
int A[30000], B[30000], C[30000];
{
int N, M;
ll res;
maxflow<int,ll> f;
rd(N,M);
rd((A,B,C)(M));
A[0..M-1]--;
B[0..M-1]--;
f.malloc(N);
f.init(N);
f.addEdge(A[0..M-1],B[0..],C[0..],C[0..]);
res = f.solve(0, N-1);
wt(res);
}
最小費用流(minCostFlow)
最大流は minCostFlow<int,double> flow; などで定義します.この場合,流量は int 型で,コストは double 型です.
以下の説明では minCostFlow<FT,CT> flow; とします.
徐々に流していくアルゴリズムを適当に実装したもので,少なくても現状は良い実装ではないと思います.
負の閉路などがあると動きません.
- int flow.node : ノード数
- FT flow.eps : これ以下だと 0 だと思う閾値(FT = double のときなどに使われる,デフォルトだと 1e-9.init() 関数などでセットされる)
- int *flow.es : flow.es[i] でノード i から出ている枝の本数
- int **flow.edge : flow.edge[i][j] はノード i から出ている j 番目の枝が向かう先のノード番号
- int **flow.rev : ノード i から出ている j 番目の枝の逆向きの枝がノード j から出ている flow.edge[i][j] 番目の枝
- FT **flow.flow : ノード i から出ている j 番目の枝にそって後どれぐらい流せるか
- flow.malloc(int N) : ノード数 N のグラフを確保できるメモリを確保(枝の分のメモリは確保しない)
- flow.init(int N) : グラフを初期化,ノード数を N に設定
- flow.addEdge(int n1, int n2, FT f, CT c) : ノード n1 から n2 に向かって流量 f,コスト c の枝を張る
- template<class FTS, class CTS> void solve(int st, int ed, FTS &fres, CTS &cres, FT flim = -1) : ノード st からノード ed までflowを流して,流れた量をfresに,コストをcresに代入する.ただし,最大で流量flimまでしか流さない.flim=-1なら流せるだけ流す,flim=-2ならコストが負の間だけ流す.
AhoCorasick
あまりちゃんと verify してません.
AhoCorasick aho; で定義したとします.
最終的なノード数の上限を n(例えば食わせる文字列の文字数の和),アルファベットのサイズ(文字の種類数)を k として,aho.malloc(n, k); でメモリの確保+初期化します.
アルファベットは0からk-1までの数値です.
文字列を addWord でいくつか加えてTrieぽいグラフを作る.
そして,construct で failedリンクを作って準備完了です.
- int aho.node : グラフのノード数
- void aho.init(void) : 初期化(空文字を表すノード1個のみに戻す)
- template<class T> void aho.addWord(const T word[], const int len, const int id)
- void aho.construct(void *mem = wmem)
- template<class T> inline void next(const int n, const T c) : ノードnにいるときに次にcの文字で遷移した先のノードを返す.constructを呼び出した後に使える.
- int aho.indsz[n] : ノードnが終端となるような文字列の数
- int aho.ind[n][k] : ノードnが終端となるようなk個目の文字列のid(idはaddWordで食わせたもの)
全ての文字列を区別する必要がなければ以下のもので十分かもしれません.
AhoCorasick_Sum<class S> aho; で定義したとします.
最終的なノード数の上限を n(例えば食わせる文字列の文字数の和),アルファベットのサイズ(文字の種類数)を k として,aho.malloc(n, k); でメモリの確保+初期化します.
アルファベットは0からk-1までの数値です.
文字列を addWord でいくつか加えてTrieぽいグラフを作る.
そして,construct で failedリンクを作って準備完了です.
- int aho.node : グラフのノード数
- void aho.init(void) : 初期化(空文字を表すノード1個のみに戻す)
- template<class T> void aho.addWord(const T word[], const int len, const S val)
- void aho.construct(void *mem = wmem)
- template<class T> inline void next(const int n, const T c) : ノードnにいるときに次にcの文字で遷移した先のノードを返す.constructを呼び出した後に使える.
- S aho.sum[n] : ノードnが終端となるような文字列のvalの和
AhoCorasickの使い方の参考:
AtCoder Beginner Contest #122 D問題 - We Like AGC
その他色々な関数など
- walloc1d(T **arr, int x, void **mem = &wmem): 配列arrに要素数xだけワーキングメモリから割り当てる(ワーキングメモリは割当てた分は勝手に進む)
- walloc2d(T ***arr, int x, int y, void **mem = &wmem): 二次元配列arrに要素数x*yだけワーキングメモリから割り当てる(ワーキングメモリは割当てた分は勝手に進む)
- malloc1d(T **arr, int x): 配列arrに要素数xだけmallocを使ってメモリを割り当てる
- malloc2d(T ***arr, int x, int y): 二次元配列arrに要素数x*yだけmallocを使ってメモリを割り当てる
- free1d(T *arr): malloc1d() で確保したメモリを開放
- free2d(T **arr): malloc2d() で確保したメモリを開放
int i, j;
int *a, **m, **hoge;
walloc1d(&a, 100);
walloc2d(&m, 50, 100);
rep(i,100) a[i] = i;
rep(i,50) rep(j,100) m[i][j] = i+j;
// ↓出力 *例* (sizeof(*a)=4の環境)
printf("%p %d\n",a,a); // 0x404040 4210752
printf("%p %d\n",m,m); // 0x4041d0 4211152
printf("%p %d\n",m[0],m[0]); // 0x404298 4211352
printf("%p %d\n",m[1],m[1]); // 0x404428 4211752
malloc2d(&hoge, 50, 100);
free2d(hoge);
int *a;
void *mem;
mem = wmem; // ワーキングメモリの先頭アドレスを覚えておく
walloc1d(&a, 1d6); // 10^6要素の配列を確保
/* 何かする */
wmem = mem; // ワーキングメモリの先頭アドレスを戻すことによって,配列aを解放
Rand構造体.乱数生成に使う.xorshift.
Rand rnd; で宣言したとして以下の通り.
何回か実行したとき,うまく種を設定しないと最初の数十回ぐらいは似た系列が出てくるので,気になる場合は,最初にgetを100回呼び出すなど空打ちすると良い.
一部仕様は未決定.
種を設定しない場合は,time(NULL)を使って設定.
- int rnd.get(int a): 0以上a未満の整数を一様にランダムに返す
- int rnd.get(int a, int b): a以上b以下の整数を一様にランダムに返す
- ll rnd.get(ll a): 0以上a未満の整数を一様にランダムに返す
- ll rnd.get(ll a, ll b): a以上b以下の整数を一様にランダムに返す
- double rnd.get(double a, double b): a以上b未満の実数を一様にランダムに返す
以下は微妙に仕様を決めきれてない.
- ll rnd.get(void): 0以上2^32未満の整数を一様にランダムに返す
- ll rnd.getExp(int a): 0以上a未満の整数をランダムに返す.ただし,小さい値がでやすい.exp(k)の形に書いたとき,kの値が一様に分布な感じ.
- ll rnd.getExp(int a, int b): a以上b以下の整数をランダムに返す.ただし,小さい値がでやすい.exp(k)+aの形に書いたとき,kの値が一様に分布な感じ.
以下はそのうち実装予定でまだ作ってない
- void rnd.set(unsigned w): 種をセット
- void rnd.set(unsigned x, unsigned y, unsigned z, unsigned w): 種をセット
unionfind構造体.unionFind uf; で宣言したとして以下の通り.
- void malloc(const int n): メモリ確保
- void free(void): mallocで確保したメモリの解放
- void walloc(const int n, void **mem=&wmem): メモリ確保
- void init(const int n): 初期化
- void init(void): 確保したメモリの要素数で初期化
- int get(int a): ノードaの一番親のノードを返す(uf.get(a)==uf.get(b)ならa,bは同じグループに属す)
- int connect(int a, int b): aとbを同じグループにまとめる.aとbが既に同じグループなら0を返し,そうでなければ1を返す
- int operator()(int a): get(a)と同じ
- int operator()(int a, int b): connect(a,b)と同じ
以下あまり使わないやつ
- int &operator[](const int a): 内部の配列の値
- int sizeList(int res[]): 各グループのサイズからなる配列を返す.返り値はグループ数.
Timer構造体.時間を測るために使う.Timer timer;で宣言したとして以下の通り.gettimeofdayを使用する.
- void timer.set(): 初期化.
- double timer.get(): 最後にset()を呼び出してからの経過秒数を返す.
int i;
ll sum = 0;
Timer timer;
double tm;
timer.set();
rep(i,1,1d8) sum += 1d9 /+ i;
tm = timer.get();
wtF("time: {tm}, sum: {sum}\n"); // time: 0.678610086441040, sum: 19048729277
- sortA(int N, S A[], T B[], ...): 要素数Nの2個~4個の配列を (A[i], B[i], ...) が辞書式順序で小さい順にソートします.ワーキングメモリを使用します.
- sortF(int N, unsigned A[]): 基数ソートする.ただしNが256未満ならばstd::sortでソートする.こっちの方が速い気がするけど,環境・入力依存.配列の要素が大幅偏っているとstd::sortに負けるかも.
- sortF(int N, int A[]): 基数ソートする.ただしNが256未満ならばstd::sortでソートする.こっちの方が速い気がするけど,環境・入力依存.配列の要素が大幅偏っているとstd::sortに負けるかも.大体大丈夫だと思うけどもしかしたら正常に動かない環境があるかも.
- sortF(int N, ull A[]): 基数ソートする.ただしNが512未満ならばstd::sortでソートする.こっちの方が速い気がするけど,環境・入力依存.配列の要素が大幅偏っているとstd::sortに負けるかも.
- sortF(int N, ll A[]): 基数ソートする.ただしNが512未満ならばstd::sortでソートする.こっちの方が速い気がするけど,環境・入力依存.配列の要素が大幅偏っているとstd::sortに負けるかも.大体大丈夫だと思うけどもしかしたら正常に動かない環境があるかも.
- sortE(a, b, c, ...): バブルソートで昇順にするコードに展開します.現状 a, b, c, ... は全て同じ型でないと動きません.
- rsortE(a, b, c, ...): バブルソートで降順にするコードに展開します.現状 a, b, c, ... は全て同じ型でないと動きません.
int i; // (1,2) ←出力結果
int A[5] = {3,1,3,5,2}; // (2,5)
int B[5] = {1,2,3,4,5}; // (3,1)
sortA(5,A,B); // (3,3)
rep(i,5) wtF("({A[i]},{B[i]})\n"); // (5,4)
- template<class S> void arrErase(int k, int &sz, S a[]): 要素数szの配列aのk番目の要素を消す.szは勝手に1減る.a[0]=1, a[1]=3, a[2]=4, sz=3 のとき arrErase(1,sz,a) によって a[0]=1, a[1]=4, sz=2 に変更される.
- template<class S, class T> void arrErase(int k, int &sz, S a[], T b[]): 要素数szの配列aと配列bのk番目の要素を消す.
- template<class S, class T, class U> void arrErase(int k, int &sz, S a[], T b[], U c[]): 要素数szの配列aと配列bと配列cのk番目の要素を消す.
x if[c1,s1,c2,s2,e] y; は if(c1){ x s1 y; } else if(c2){ x s2 y; } else { x e y; } に展開される.(c1,s1)のペアはいくつ合っても良い.eは空なら省略可能.
ただし,現状if文などの()の中では使用不可能.
例えば
a[i] = x if[i%2==0,+,-] y;
s[i] = b[i] if[i,+s[i-1]];
は以下のように展開されます:
if(i%2==0){
a[i] = x + y;
} else {
a[i] = x - y;
}
if(i){
s[i] = b[i] + s[i-1];
} else {
s[i] = b[i];
}
- min[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最小値を返します.i, j 動かす場合は min[i=a---b, j=c---d](式).i は変数として定義されてなくても構いません(この式の評価にのみ用います).
- max[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最小値を返します.i, j 動かす場合は max[i=a---b, j=c---d](式).
- argmin[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最小値を与えるような最小の i を返します.
- argmax[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最大値を与えるような最小の i を返します.
- argminL[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最小値を与えるような最大の i を返します(argminLのLはLast).
- argmaxL[i=a---b](式): 式において i を a から b まで(両端含む)動かしたときの最大値を与えるような最大の i を返します.
- argmin(arr(n)): argmin[var=0---n-1](arr(var)) 長さnの配列arrの最小値の添え字を返す.複数存在するなら最小の添え字を返す.
- argmax(arr(n)): argmax[var=0---n-1](arr(var)) 長さnの配列arrの最大値の添え字を返す.複数存在するなら最大の添え字を返す.
- argminL(arr(n)): argminL[var=0---n-1](arr(var)) 長さnの配列arrの最小値の添え字を返す.複数存在するなら最小の添え字を返す.
- argmaxL(arr(n)): argmaxL[var=0---n-1](arr(var)) 長さnの配列arrの最大値の添え字を返す.複数存在するなら最大の添え字を返す.
int i;
i = min[k=1---100](abs(4*k-50));
wt(i); // 2 と表示
i = argmin[k=1---100](abs(4*k-50));
wt(i); // 12 と表示
- bseach_min[type,name,minval,maxval(,option)][block](cond): 「blockを実行した上でcondを満たす」最小の minval ≤ name ≤ maxval の値を返す.(,option),[block]は省略可能.
- bseach_max[type,name,minval,maxval(,option)][block](cond): 「blockを実行した上でcondを満たす」最大の minval ≤ name ≤ maxval の値を返す.(,option),[block]は省略可能.
それぞれ単調性が成り立たなければならない.
例えば,bsearch_minの場合,name=10のときcondが成り立つならば,name=10以上(maxval以下)のときもcondは成り立たなければならない.
typeは変数nameの型を指定し,float, doubleの場合は実数の二分探索,それ以外は整数の二分探索を行う.
bsearch_minでは,name=minvalでは評価されず,name=minvalより大きい場合に常に偽ならminvalが返ってくる(name=minvalのときはblock, condが未定義になるようなものでも良い).
今のところ,minval, maxvalは省略不可能.
optionは以下の通り.
- AE=val : 実数の二分探索で,絶対誤差でval以下が保証できるようになったら打ち切る.
- RE=val : 実数の二分探索で,相対誤差でval以下が保証できるようになったら打ち切る.
- E=val : 実数の二分探索で,絶対誤差または相対誤差でval以下が保証できるようになったら打ち切る.
実数の二分探索で,許容誤差を指定しない場合は,見ている範囲を[x,y]としたとき,(x+y)/2が(計算機上で)xまたはyに一致したら打ち切る(許容誤差を指定してもこの判定は行う).
int i, j, k, t;
double x, y;
k = -1;
i = bsearch_max[int,k,0,100](k*k<=10);
j = bsearch_min[int,k,0,100][
t = 0;
rep(j,1,k+1) t += k / j;
](t >= 100);
x = bsearch_max[double,x,0,100](x*x<=10);
y = bsearch_max[double,x,0,100,E=1e-1](x*x<=10);
wt(i,j,k,x,y); // 3 28 -1 3.162277660168380 3.222656250000000
- template<class T> inline int isPrime(T N): Nが素数なら1,そうでないねら0を返す.$O(\sqrt{N})$ 時間.
- int Prime(int N, int res[], void *mem = wmem): N未満の素数を列挙する.
- template<class T> void intervalSieve(ll st, int len, T res[], int ps, int p[]) : 区間篩.res[i]はst+iが素数なら1,そうでないなら0が代入される(i=0,1,...,len-1).ps, p[]としてsqrt(st+len-1)以下の素数を列挙しておく必要がある.
- template<class T> int Factor(int N, T fac[], int fs[]): 素因数と重複度を求める.下記の例を参照.Tはint, llなどの整数.
- template<class T> int Factor(int N, T fac[]): 相異なる素因数を求める.下記の例を参照.Tはint, llなどの整数.
- template<class T> int FactorM(int N, T fac[]): 重複を含めて素因数を求める.下記の例を参照.Tはint, llなどの整数.
- template<class T> int Divisor(int N, T dv[], void *mem = wmem): 約数を求める.下記の例を参照.Tはint, llなどの整数.
facは異なる素因数,fsはその素因数を何個持つか.
int fac[100], fs[100], fsz;
int dv[100], dsz;
fsz = Factor(1500, fac, fs); // 1500 = 2^2 * 3^1 * 5^3
rep(i,fsz) wt(fac[i], fs[i]); // fsz=3, fac={2,3,5}, fs={2,1,3}
fsz = Factor(1500, fac);
wt(fac(fsz)); // 2 3 5
fsz = FactorM(1500, fac);
wt(fac(fsz)); // 2 2 3 5 5 5
dsz = Divisor(24, dv);
wt(dv(dsz)); // 1 2 3 4 6 8 12 24
- gcd(), GCD(): 引数の最大公約数を返します.rd, wtのように配列を指定可能です.
- lcm(), LCM(): 引数の最小公倍数を返します.rd, wtのように配列を指定可能です.
- min(), MIN(): 引数の最小値を返します.rd, wtのように配列を指定可能です.
- max(), MAX(): 引数の最大値を返します.rd, wtのように配列を指定可能です.
- sum(), SUM(): 引数の和を返します.rd, wtのように配列を指定可能です.
- mul(), MUL(): 引数の積を返します.rd, wtのように配列を指定可能です.
関数名がよく使う名前なのでこの機能を無効化するフラグがあります(フラグの欄を参照のこと).
引数の型は違っても構いませんが,計算途中でどのような型になるかは不明です(オーバーフローなどに注意).
今のところ,整数と浮動小数点数ぐらいでしか上手く動かないと思います.例外的にsum()はstring型でも動くはずです(文字列を連結します).
配列は長さ0の配列を与えると上手く動かないことがあります.
int i = 10, j = 75;
int k[3] = {100, 200, 300};
wt(gcd(i,j,k(3))); // gcd(10,75,100,200,300) = 5
wt(min(i,j,k(3))); // min(10,75,100,200,300) = 10
wt(sum(i,j,k(3))); // sum(10,75,100,200,300) = 685
- template<class T> void slideMin(int n, int k, T in[], T res[], void *mem = wmem) : スライド最小値.長さnの配列inに対して,長さkの区間の最小値を全て求めます.res[i] = min(in[i], ..., in[i+k-1]) になります(i=0,1,...,n-k).時間計算量 $O(n)$.
- template<class T> void slideMax(int n, int k, T in[], T res[], void *mem = wmem) : スライド最大値.長さnの配列inに対して,長さkの区間の最大値を全て求めます.res[i] = max(in[i], ..., in[i+k-1]) になります(i=0,1,...,n-k).時間計算量 $O(n)$.
combination_mint は階乗とその逆数を前計算することで二項係数を高速に求めます.mint型で答えを返します.
構造体を使用しているので combination_mint comb; と最初に宣言して下さい.
- comb.init(int n, void **mem = &wmem) : 階乗とその逆数をを 0 乗から n-1 乗まで計算します.ワーキングメモリを使用します.
- mint comb.fac[] : fac[i] に i の階乗を格納しています.
- mint comb.ifac[] : ifac[i] に i の階乗の逆元を格納しています.
- mint comb.C(int a, int b) : C(a,b) = $\frac{a!}{b!(a-b)!}$ を返します(bが負,a以上のときは0を返します).aはnより小さい必要があります.
- mint comb.P(int a, int b) : P(a,b) = $\frac{a!}{(a-b)!}$ を返します.aはnより小さい必要があります.
- mint comb.H(int a, int b) : H(a,b) = C(a+b-1, b) を返します.a+b-1はnより小さい必要があります.
combination_mint comb;
mint res;
comb.init(101); // 100の階乗までを計算.以降 C(100,hoge) まで計算可能
res = comb.C(5,2);
wt(res); // 10 = 5*4/2 = 5個から2個を選ぶ選び方
- reduceFraction(a,b) : aとbをgcd(a,b)で割ります(分数a/bを約分します).
int a = 32, b = 24;
reduceFraction(a,b);
wtF("{a}/{b}\n"); // 4/3 と表示
- int fibonacci_mod(ull n, int md), int fib_mod(ull n, ind md) : フィボナッチ数の第 n 項を mod md で求めます.mdを省略するとmd = MDが指定されます.
int i, f[10];
rep(i,10) f[i] = fib_mod(i);
wt(f(10)); // 0 1 1 2 3 5 8 13 21 34
- template<class T> inline int Digit(T n) : 正の整数nを10進数で書いたときの桁数を返す(0に対しては現状0を返す)
- template<class T, class S> inline S Digit(T n, S b) : 正の整数nをb進数で書いたときの桁数を返す
- template<class T> inline int sod(T n) : nを10進数で書いたときの各桁の和を返す
- template<class T, class S> inline S sod(T n, S b) : nをb進数で書いたときの各桁の和を返す
- b[t](a,b,c):t進数でabcの値を表す.これは (((a)*(t)+(b))*(t)+(c)) に展開されます.
- b[x,y](a,b,c,d):((a*x+b)*x+c)*y+d を表す.[]および()の中の引数の数は任意.下の桁から y,x,x,x,... パターンの数を取るような進数を考えている感じ.
- template<class T> int LIS_length(int n, T a[], void *mem = wmem) : 要素数nの配列aの最長増加部分列の長さを返す
- template<class T> int weaklyLIS_length(int n, T a[], void *mem = wmem) : 要素数nの配列aの最長非減少部分列の長さを返す
- template<class T> int coordcomp(int n, T arr[], int res[] = NULL, void *mem = wmem) : 座標圧縮.arrの各要素の大きさの順番を維持したまま小さな非負整数に変換したものをresに格納.res = NULLのときはarrに上書き.異なる要素の数を戻り値として返す.coordcomp()の代わりにcoord_comp()も可能.$O(n \log n)$ 時間.
- template<class T> int coordcomp(int n1, T arr1[], int n2, T arr2[], int res1[] = NULL, int res2[] = NULL, void *mem = wmem) : 座標圧縮.2つの配列を連結してから処理する.異なる要素の数を戻り値として返す.coordcomp()の代わりにcoord_comp()も可能.
int n;
int C[5] = {1000, 100, 1, 8, 100};
n = coordcomp(4, C);
wt(n); // 4
wt(C(5)); // 3 2 0 1 2
int A[5] = {100, 4, 8, 4, 100};
int B[4] = {8, 2, 1200, 8};
int rA[5], rB[4];
n = coordcomp(5, A, 4, B, rA, rB);
wt(n); // 5
wt(A(5)); // 100 4 8 4 100
wt(B(4)); // 8 2 1200 8
wt(rA(5)); // 3 1 2 1 3
wt(rB(4)); // 2 0 4 2
- template<class T> void Unique(int &N, T A[], int sorted=0) : 要素数Nの配列Aの重複する要素を削除する.要素数,配列は書き換えられる.勝手にソートする.既にソート済みならsorted=1にするとソートしなくなり速くなる.
- template<class T, class S> void Unique(int &N, T A[], S B[], int sorted=0) : 上と同じ.A[i]はB[i]個あると思って,要素の数もカウントする.実際は個数じゃないのでB[i]は整数値じゃなくても良い.
{
int N = 7;
int A[7] = {7,4,1,4,1,4,1};
Unique(N,A);
// N = 3, A = {1, 4, 7}
}
{
int N = 7;
int A[7] = {7,4,1,4,1,4,1};
int B[7] = {1,2,2,2,2,2,2};
Unique(N,A,B);
// N = 3
// A = {1, 4, 7}
// B = {6, 6, 1}
}
- ll inversion_range(int N, int A[], int mn, int mx, void *mem=wmem) : 要素数Nの配列A[]の転倒数を求めます.Fenwick Treeを使うやつ.配列A[]の要素の最小値はmn以上,最大値はmx以下でなければなりません.時間計算量は $O(N \log (mx-mn) + (mx-mn))$ 程度で,$mx-mn \approx N$ ならば以下のinversionより高速なはずです.
- template<class T> ll inversion(int N, T A[], void *mem=wmem) : 要素数Nの配列A[]の転倒数を求めます.マージソートしながら数えるやつ.時間計算量は $O(N \log N)$ です.
{
int d[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
int inv;
inv = inversion_range(10, d, 1, 9);
wt(inv); // 14
}
{
double d[10] = {1e3, 1e1, 1e4, 1e1, 1e5, 1e9, 1e2, 1e6, 1e5, 1e4};
int inv;
inv = inversion(10, d);
wt(inv); // 14
}
- template<class T> void ZetaTransform(int N, T A[], T res[] = NULL) : 高速ゼータ変換します.resがNULLのときは結果を配列Aに上書きします.時間計算量は $O(N \log N)$.
- template<class T> void MobiusTransform(int N, T A[], T res[] = NULL) : 高速メビウス変換します.resがNULLのときは結果を配列Aに上書きします.時間計算量は $O(N \log N)$.
int i, A[6] = {2,5,9,4,1,8}, B[6], C[6];
ZetaTransform(6, A, B);
MoebiusTransform(6, B, C);
rep(i,6) printf("%d %d%d%d %02d %02d %02d\n", i, (i>>2)%2, (i>>1)%2, i%2, A[i], B[i], C[i]);
// 0 000 02 02 02
// 1 001 05 07 05
// 2 010 09 11 09
// 3 011 04 20 04
// 4 100 01 03 01
// 5 101 08 16 08
- int runLength(int N, T A[], T val[], int len[]) : 長さNの配列Aをランレングス圧縮します.要素val[i]がlen[i]個続くという感じに求めます.配列val, lenの要素数を返します.
int N = 10;
int A[10] = {0,0,1,1,1,0,0,3,2,1}; // 0が2個 - 1が3個 - 0が2個 - 3が1個 - 2が1個 - 1が1個
int e, val[10], len[10];
e = runLength(N,A,val,len);
wt(e); // 6 と表示されます
wt(val(e)); // 0 1 0 3 2 1
wt(len(e)); // 2 3 2 1 1 1
- template<class T> T popFirst(multiset<T> &a), template<class T> T popFirst(set<T> &a) : aの最初の要素を削除し,その要素の値を返す
- template<class T> T getFirst(multiset<T> &a), template<class T> T getFirst(set<T> &a) : aの最初の要素の値を返す
- template<class T> T popLast(multiset<T> &a), template<class T> T popLast(set<T> &a) : aの最後の要素を削除し,その要素の値を返す
- template<class T> T getLast(multiset<T> &a), template<class T> T getLast(set<T> &a) : aの最後の要素の値を返す
いずれの関数も,空のmultiset, setを引数に取ってはいけません.
- inline int isLeapYear(const int y) : y年がうるう年のときに1,そうじゃないときに0を返す
- inline int numOfDaysInMonth(const int m) : うるう年じゃない年のm月の日数を返す
- inline int numOfDaysInMonth(const int y, const int m) : y年m月の日数を返す
基本的にグレゴリオ暦を仮定
- inline int isVowel(const char c) : 母音のとき1,そうじゃないときに0を返す(母音はaiueoでyは含まない)
- template<class T, class S> int KMP(T A[], int As, T B[], int Bs, S res[] = NULL, int *fail = (int*)wmem) : KMP法.AsはAの配列の長さ,BsはBの配列の長さ.Aの連続する部分列として何個Bがあるかを返す.res[i]=1はA[i]から始まる連続する部分文字列がBであるという意味.failは内部で利用するが,例えば,Bs-fail[Bs]は配列Bの周期になっているなどの利用価値がある.配列Bの周期がpであるとはB[i]=B[i-p]が全ての p ≤ i < Bs で成り立つこと(pはBsの約数でなくても良い).
- template<class T>int isSubsequence(int As, T A[], int Bs, T B[]) : 配列Bが配列Aの部分列ならば1,そうでなければ0を返す.
- template<class T>int longestSuffixPrefix(int As, T A[], int Bs, T B[], void *mem = wmem) : KMP法で「配列Aのsuffix = 配列Bのprefix」となる最大の長さを返す.
int A[10] = {1,2,3,1,2,3,1,2,3,1};
int B[4] = {1,2,3,1};
int res[10], cnt;
cnt = KMP(A, 10, B, 4, res);
wt(cnt); // 3
wt(res(10)); // 1 0 0 1 0 0 1 0 0 0
- template<class T> void SuffixArray(T *s, int N, int K, int *SA, int *LCP = NULL, void *mem = wmem) : 配列sのSuffixArrayを求める.sの長さはNで,sの各要素は1以上K-1以下である必要がある.LCPも必要であれば求めることができる.末尾に0を付加して計算するため,配列s,SA,LCPはN+1要素以上メモリが確保されていないといけない.時間計算量は $O(N+K)$.Kが大きかったり,0以下の要素を含む場合などは先に座標圧縮を行う.
char S[12] = "abracadabra";
int SA[12], LCP[12];
SuffixArray(S, 11, 128, SA, LCP);
rep(i,12) printf("%4d %4d %4d %s\n", i, SA[i], LCP[i], S+SA[i]);
/*
0 11 -1
1 10 0 a
2 7 1 abra
3 0 4 abracadabra
4 3 1 acadabra
5 5 1 adabra
6 8 0 bra
7 1 3 bracadabra
8 4 0 cadabra
9 6 0 dabra
10 9 0 ra
11 2 2 racadabra
*/
Grid1d構造体.
Grid1d<int> g; などで定義し,g.malloc(n); でメモリを確保する.メモリ解放するときは g.free(); .
すると,g[i]が使えるようになり,それぞれint型.
g[i] にデータを代入して,g.setSum(),g.setDir() 等で累積和などのテーブルを作成して,利用する.
データを変更した場合は,g.setSum() などを再度呼び出せば良い.
行の数,列の数を変更する場合は,現状,g.free()→g.malloc(n)とやり直すしかない.
以下は,Grid1d<T> g;を想定.
- void g.malloc(const int n) : n固のデータ領域を確保(g[0]からg[n-1]まで使える)
- void g.free(void) : メモリ解放(以下の機能で確保したメモリも全て解放)
累積和関係
- void g.setSum(void) : 累積和のテーブルを作成(以下の機能を使う前に呼び出す)
- inline T g.getSum(const int a, const int b) : g[i] (a ≤ i ≤ b) の和を返す.ただし,a > b の場合は正しく動かない
- T *g.d_s : g.d_s[i] には g.d[0]+...+g.d[i-1] が入っている.
縦横に連続する数
- void g.setDir(void) : 以下の up, dw, lf, rg をセットする.g[i]と同じ値が左右に何個続くかを求める
- void g.setDirMatch(const T v) : 以下の up, dw, lf, rg をセットする.g[i]がvとなるようなセルが上下左右に何個続くかを求める
- int *lf : lf[i] は g[i], g[i-1], ..., g[i-k+1] が全て条件を満たすような最大のkが入っている(自分のマスから左方向に連続して何マスが条件を満たすか)
- int *rg : rg[i] は g[i], g[i+1], ..., g[i+k-1] が全て条件を満たすような最大のkが入っている(自分のマスから右方向に連続して何マスが条件を満たすか)
- int *up : rgと同じ.
- int *dw : lfと同じ.
Grid2d構造体.
Grid2d<int> g; などで定義し,g.malloc(r,c); でメモリを確保する.メモリ解放するときは g.free(); .
すると,g[i][j]が使えるようになり,それぞれint型.
g[i][j] にデータを代入して,g.setSum(),g.setDir() 等で累積和などのテーブルを作成して,利用する.
データを変更した場合は,g.setSum() などを再度呼び出せば良い.
行の数,列の数を変更する場合は,現状,g.free()→g.malloc(r,c)とやり直すしかない.
以下は,Grid2d<T> g;を想定.
- void g.malloc(const int r, const int c) : r行c列のデータ領域を確保(g[0][0]からg[r-1][c-1]まで使える)
- void g.free(void) : メモリ解放(以下の機能で確保したメモリも全て解放)
累積和関係
- void g.setSum(void) : 累積和のテーブルを作成(以下の機能を使う前に呼び出す)
- inline T g.getSum(const int r1, const int c1, const int r2, const int c2) : g[i][j] (r1 ≤ i ≤ r2, c1 ≤ j ≤ c2) の和を返す.ただし,r1 > r2 または c1 > c2 の場合は正しく動かない
- T **g.d_s : g.d_s[i][j] には g.d[0][0]+...+g.d[i-1][j-1] が入っている.
縦横に連続する数
- void g.setDir(void) : 以下の up, dw, lf, rg をセットする.g[i][j]と同じ値が上下左右に何個続くかを求める
- void g.setDirMatch(const T v) : 以下の up, dw, lf, rg をセットする.g[i][j]がvとなるようなセルが上下左右に何個続くかを求める
- int **up : up[i][j] は g[i][j], g[i-1][j], ..., g[i-k+1][j] が全て条件を満たすような最大のkが入っている(自分のマスから上方向に連続して何マスが条件を満たすか)
- int **dw : dw[i][j] は g[i][j], g[i+1][j], ..., g[i+k-1][j] が全て条件を満たすような最大のkが入っている(自分のマスから下方向に連続して何マスが条件を満たすか)
- int **lf : lf[i][j] は g[i][j], g[i][j-1], ..., g[i][j-k+1] が全て条件を満たすような最大のkが入っている(自分のマスから左方向に連続して何マスが条件を満たすか)
- int **rg : rg[i][j] は g[i][j], g[i][j+1], ..., g[i][j+k-1] が全て条件を満たすような最大のkが入っている(自分のマスから右方向に連続して何マスが条件を満たすか)
- BIT_ith(i) : (1<<(i)) に展開されます.
- BIT_lowest(i) : (-(i) & (i)) に展開されます.
- BIT_nonlowest(i) : ((i) & ((i)-1)) に展開されます.
FFTを用いて畳み込みを行います.
誤差がそれなりにのるので使用する際には注意.
- void convolution(double A[], int As, double B[], int Bs, double res[], int Rs, void *mem = wmem) : res[k] = A[0]*B[k] + A[1]*B[k-1] + ... + A[k]*B[0] を k = 0, 1, ..., Rs-1 まで計算します.AsとBsは配列A, Bの長さです.
- void convolution(double A[], int As, double res[], int Rs, void *mem = wmem) : res[k] = A[0]*A[k] + A[1]*A[k-1] + ... + A[k]*A[0] を k = 0, 1, ..., Rs-1 まで計算します.Asは配列Aの長さです.
double a[3] = {1,2,3}, b[3] = {1,2,3}, c[6];
convolution(a, 3, b, 3, c, 6);
wt(c(6)); // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001
convolution(a, 3, c, 6);
wt(c(6)); // 0.999999999999999 3.999999999999999 10.000000000000000 12.000000000000000 9.000000000000000 0.000000000000001
グラフの隣接リスト(隣接配列?)のようなものを作ります.
時間ごとにイベントを処理する場合などの整理などにも多分便利.
- template<class S> void wAdjEdge(const int N, const int M, const int *A, const S *B, int **res_sz, S ***res_B, void **mem = &wmem)
- template<class S, class T> void wAdjEdge(const int N, const int M, const int *A, const S *B, const T *C, int **res_sz, S ***res_B, T ***res_C, void **mem = &wmem)
- template<class S, class T, class U> void wAdjEdge(const int N, const int M, const int *A, const S *B, const T *C, const U *D, int **res_sz, S ***res_B, T ***res_C, U ***res_D, void **mem = &wmem)
- template<class S, class T, class U, class V> void wAdjEdge(const int N, const int M, int *A, const S *B, const T *C, const U *D, const V *E, int **res_sz, S ***res_B, T ***res_C, U ***res_D, V ***res_E, void **mem = &wmem)
int A[5] = {1,1,3,3,0}, B[5] = {10,30,30,30,50};
int *es, **edge;
wAdjEdge(4, 5, A, B, &es, &edge);
rep(i,4) wt(i, ':', es[i], ':', edge[i](es[i]));
// 0 : 1 : 50
// 1 : 2 : 10 30
// 2 : 0 :
// 3 : 2 : 30 30
更新履歴
- 20190827-1:
【機能追加っぽいの】
intervalSieve() を追加.
isSubsequence() を追加.
slideMin(), slideMax() を追加.
sum() において,string型に対応.
【バグ修正っぽいの】
hoge ** piyo で,piyo の部分に _ が含まれているとうまく動かなかったのを修正.
if文の中などで,''や""に囲まれた ( や ) を使うと,文の区切りの判定をミスるのを修正.
Grid1d において,setSum, getSum の機能がバグって使えなかったのを修正.
【その他っぽいの】
graph, wgraph において,構造体を使っても,構造体内の使ってない関数をある程度挿入しないようにして,ソースコードが短くなるようにした. - 20190822-2:
【バグ修正っぽいの】
wAdjEdge() がバグっていたのを修正.
20190822-1の更新履歴が一部間違っていたのを修正. - 20190822-1:
【機能追加っぽいの】
グラフの隣接リスト(隣接配列?)っぽいのを作る関数 wAdjEdge() を追加.
Heap, Heap_max を追加(機能はほぼpriority_queue).
【ドキュメントに追記したもの(元々使えるもの)】
三項演算子を使わない場合は基本的に , は ; に置き換えられるので,for(;;) i++, break; などと書けることを追記. - 20190820-1:
【機能追加っぽいの】
SuffixArray() を追加.
graph に shortestUndirectedCycle_length() を追加.
【バグ修正っぽいの】
#pragma hoge を判定していなくてバグることがあったのを修正. - 20190818-1:
【バグ修正っぽいの】
maxflowが動かなくなっていたのを修正. - 20190817-1:
【機能追加っぽいの】
コードの先頭に #pragma GCC optimize ("Ofast") を追加するようにした.
演算子 %% に対する %%= を追加.
wgraph に BellmanFord() を追加.
arrErase() を追加.
longestSuffixPrefix() を追加.
【バグ修正っぽいの】
Grid1d の free() で同じ配列を2回メモリ解放しようとするバグを修正. - 20190810-2:
【バグ修正っぽいの】
#undefに対応. - 20190810-1:
【機能追加っぽいの】
Grid1d を追加.
Digit() を追加.
【その他っぽいの】
一部の関数にinlineをつけた. - 20190802-2:
【バグ修正っぽいの】
Grid2dのsetDirMatch()がバグってたのを修正. - 20190802-1:
【機能追加っぽいの】
rdでchar型1文字の入力を追加(実は出力は今まででも可能だった).
1行の入力 rdLine() を追加.
sortEを追加.
graphにトポロジカルソート TopologicalSort() を追加.
wgraphにPrim法による最小全域木の重み和を求める関数 MST_Prim_cost() を追加.
Grid2d を追加.
二分探索 bsearch で,double型の終了条件で絶対誤差,相対誤差を指定できるようにした.
KMP (Knuth-Morris-Pratt) を追加.
FFTを用いた畳み込み convolution() を追加.
ビットに関して BIT_ith(), BIT_get_lowest(), BIT_get_nonlowest() を追加.
【バグ修正っぽいの】
展開の順番を変更.(bsearch_min[]の中で>?=が使えなかったのを修正)
set_a = 1; など書くと,変数宣言と勘違いして set _a = 1; と分解されるのを修正.
【その他っぽいの】
rep(i,a) および rep(i,a,b) で a, b に括弧をつけるようにした.( for(i=a;i<b;i++) → for(i=(a);i<(b);i++) )
主にワーキングメモリまわりをメモリアライメントを考慮して,ところどころ変更した.
これ以前の更新履歴はこちら.
Current time: 2024年03月29日04時58分36秒
Last modified: 2019年08月27日00時22分56秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)