2019年11月10日20時54分10秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.


cLay概要(version 20191110-1)

概要

C++っぽい言語をC++言語に変換します.
無駄にライブラリを張るのがめんどくさい,鬱陶しい,ライブラリを整備していても綺麗に書けない処理があるなどを解消したいというのが目的.目的の達成はそのうち….
blogにコード載せる時にライブラリとかincludeとかが長ったらしい,のをなんとかしたいというのも動機の1つです.

#include<bits/stdc++.h>およびgetchar_unlocked,putchar_unlockedなどを使用しているので,それが動かない環境だと動かないし,動かないコードが出てきます.
(その場合は,フラグの欄を見て下さい)

コードの公開ページはこちら.C++っぽいコードを標準入力から食わせるとC++のコードが標準出力から出てきます.

未対応なもの

重要度が高い順に,下線付き太字太字,普通です.重要度が低いものはそもそも対応させる気がないものが多いです.
この欄ではC++ではできるけど…というもの主にリストアップ.

制限

以下の単語は変数名などで使うとやばい.
基本的にバージョンアップするときは互換性を保ちたいけど,此処の欄は普通に増やす.

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;が最後に補われます.

変数宣言や三項演算子 ? : を使っていない部分での,は(適切に{}を補った上で);に置き換えられます.
その結果,for(;;) i++, break; などと書くと for(;;){ i++; break; } に展開されます.

フラグ

途中で(プログラムの先頭が推奨)
//hogehoge
という形式でフラグを立てておくと色々な環境に対応させるために出力されるコードが変更されます.

またmint構造体など使用すると挿入される関数や構造体を挿入されなくするフラグは以下の通りです.
例えば,//no-insert-mintを指定するとmint型が使えなくなる代わりに,mintという変数や関数などを自由に宣言することができるようになります.

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 x; x.setmod(1000000009); とすることで,途中で mod の値を変えることができます.
mintの詳しい仕様はそのうち書きます.

モンゴメリ乗算を使用しないmodint型もあります.
MDが素数でなくても,割り算をしなければmodint型は動くと思います.
mint型とmodint型はほぼ同じ使用方法です.

途中で mod を変更できないバージョンとして1文字目を大文字にした Mint, Modint があります.
こっちのほうが高速なはず.初期化も必要ないので,変数宣言時に代入しても大丈夫なはず.
mint, modint, Mint, Modint はコンストラクタで 0 に設定されるはずです.

入出力

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型,unsigned型,ll型,ull型,double型,mint型,char型(1文字),char型の配列(文字列),string型,vector<T>,Matrix<T>,Permutation,Grid1d<T>,Grid2d<T>にのみに対応.ただし,Tは対応している型でなければならない.他の型もそのうち対応
また,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に直しながら入力するときなど.

A[2], B[4], A[3], B[5], A[4], B[6] に読み込みたい場合は rd(((A+2),(B+4))(3)); で可能です.
A[2], A[3], A[4] に読み込む場合は rd(((A+2))(3)); で可能です(かっこが多すぎる気がしますが,現状これだけ必要です…:(A+2)[0], (A+2)[1], (A+2)[2]でアクセスします).

int len; char buf[100];
len = rdLine(buf); で1行の読み込みを行います.
正確には,\n か EOF に出くわすまでbufに入れていきます(\nは入らない)が,\rだけは無視されます.
lenには基本的に読み込んだ文字数を返しますが,1文字も読み込まずEOFに出くわした場合のみ-1を返します.
bufの最後の文字の次に \0 を入れて返します.

変数に代入しないものとして,rd_int() は次の入力をint型の整数として戻り値で返します.

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(n) は int hoge; for(hoge=0;hoge<n;hoge++) に置き換えられます(hogeは適当な変数名).
rep(i,n) は for(i=0;i<(n);i++) に置き換えられます.
rep(i,a,b) は for(i=(a);i<(b);i++) に置き換えられます.
rep(i,a,b,s) は for(i=(a);i<(b);i+=(s)) に置き換えられます.
REP(n) は int hoge, piyo = n; for(hoge=0;hoge<piyo;hoge++) に置き換えられます(hoge, piyoは適当な変数名).
REP(i,n) は int piyo = n; for(i=0;i<piyo;i++) に置き換えられます(piyoは適当な変数名).
REP(i,a,b) は int piyo = b; for(i=(a);i<piyo;i++) に置き換えられます(piyoは適当な変数名).
REP(i,a,b,s) は int piyo = b, huga = s; for(i=(a);i<piyo;i+=huga) に置き換えられます(piyoは適当な変数名).
また,この際,変数iが宣言されていなかった場合,勝手にint型の変数として宣言されます.
rep では終了条件の変数・式 (n, b) が複数回評価されたり,ループの中で書き換え可能ですが,REP はそうではないことに注意してください.

同じ範囲をループで逆順で回す場合は以下があります(sを指定した場合,必ずしも同じ範囲ではないかもしれない).
rrep(n) は int hoge; for(hoge=(n)-1;hoge>=0;hoge--) に置き換えられます(hogeは適当な変数名):使う意味はないです.
rrep(i,n) は for(i=(n)-1;i>=0;i--) に置き換えられます.
rrep(i,a,b) は for(i=(b)-1;i>=(0);i--) に置き換えられます.
rrep(i,a,b,s) は for(i=(b)-1;i>=(a);i-=(s)) に置き換えられます.
RREP(n) は int hoge, piyo = n; for(hoge=piyo-1;hoge>=0;hoge--) に置き換えられます(hoge, piyoは適当な変数名):使う意味はないです.
RREP(i,n) は int piyo = n; for(i=piyo-1;i>=0;i--) に置き換えられます(piyoは適当な変数名).
RREP(i,a,b) は int piyo = a; for(i=(b)-1;i>=piyo;i--) に置き換えられます(piyoは適当な変数名).
RREP(i,a,b,s) は int piyo = a, huga = s; for(i=(b)-1;i>=piyo;i-=huga) に置き換えられます(piyoは適当な変数名).

配列の中身を変数に代入して使用したい場合は,例えば rep[arr](i,n) hoge; および rep[arr](i,n){ hoge; } は
rep(tekitouna_namae, n){
auto &i = arr[tekitouna_namae];
hoge;
}
に展開されます.rep, REP, rrep, RREP それぞれ,引数の数も自由です.
また,インデックスも利用する場合,例えば rep[arr,ind](i,n) hoge; および rep[arr,ind](i,n){ hoge; } は
rep(ind, n){
auto &i = arr[ind];
hoge;
}
に展開されます.
変数 i は既に宣言されていても,ブロックの中で再び定義されます.

ループから抜ける break について,二重ループから抜ける break_break などがあります.
break_break は break した後,その直後に break したのと同じ挙動になるはずです.
3重ループを抜ける break_break_break や,一つ上のループに対して直接continueをする break_continue などがあります.
break_ を何回か繰り返して break または continue を最後に付けた文があり,break_A は break を行って,ループを抜けた直後に A を行う感じです.

また,括弧内((),[],{}のどれか)で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 関数などを使って下さい).
ただし,x, y ともに double 型のときは,標準の pow(x,y) が呼び出されます.
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> でに関してです.

コンストラクタ

その他

置換

置換は Permutation p; などで定義します.
p[i] = j は第i要素を第j番目に飛ばす,という意味です.
i も j も 0-origin です.
現状 p ** n の計算は(他の型と同様に)バイナリ法です.

コンストラクタ

デストラクタ

演算子

メンバ関数

{
  int A[10] = {5,2,8,9,1,1,100,800,9,10};
  int B[10];
  int sz;
  int pp1[10] = {1,2,3,4,5,6,7,8,9,0};
  int pp2[10] = {1,0,3,2,5,4,7,6,9,8};

  Permutation p1, p2, m, id;
  p1.changeSize(10);
  p2.changeSize(10);
  rep(i,10) p1[i] = pp1[i];
  rep(i,10) p2[i] = pp2[i];



  wt(A(10));           // 5 2 8 9 1 1 100 800 9 10
  p1.apply(A, B);
  wt(B(10));           // 10 5 2 8 9 1 1 100 800 9
  p2.apply(A, B);
  wt(B(10));           // 2 5 9 8 1 1 800 100 10 9



  m = p1 ** 13;
  m.apply(A, B);
  wt(B(10));           // 800 9 10 5 2 8 9 1 1 100



  m = p1 * p2;
  m.apply(A, B);
  wt(B(10));           // 9 2 5 9 8 1 1 800 100 10

  p2.apply(A);
  p1.apply(A);
  wt(A(10));           // 9 2 5 9 8 1 1 800 100 10


  id.changeSize(10);
  id = 1;              // identity
  rep(i,100){
    m = p1 ** i;
    if(m==id) wt(i);   // i = 0, 10, 20, ..., 90
  }
  rep(i,100){
    m = p1 ** i;
    if(m==p1) wt(i);   // i = 1, 11, 21, ..., 91
  }


  sz = p1.cycle_len(B);
  wt(B(sz));              // 10
  sz = p2.cycle_len(B);
  wt(B(sz));              // 2 2 2 2 2
  sz = id.cycle_len(B);
  wt(B(sz));              // 1 1 1 1 1 1 1 1 1 1
}

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番目の要素まで存在します):

区間は閉区間 [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; について:

Heap_max<T> hm; について:

バイナリヒープ(固定長配列用)

LHeap<int> などで宣言.
$N$ 要素の配列 $A_k = \verb|val[k]|$ を考える.
ヒープにある要素を入れたり値を変えたり($\verb|change|$),ヒープの中に入っている最小の要素を取り出して取り出した要素の番号を返したり($\verb|pop|$)する.
大体の操作の計算時間 $O(\log N)$.

よく使いそうなもの:

そうではないもの:

  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[]|$ のフラグを立てる,更新時に訪れたものや長くなったものは更新しないなどを関数の中で判定する.

よく使いそうなもの:

そうではないもの:

  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();とすれば使えるようになります.

segtree<T> t; とした場合,使える感じの関数は以下の通り(要素数を $N$ として,0番目の要素から$N$-1番目の要素まで存在します):

区間は最初は含むが最後は含まない [a,b) の形で指定することに注意して下さい.

malloc()を使った場合のメモリの開放は t.free(); です.

セグメントツリー(亜種?)

初期化の仕方などは標準的な segtree と同じですが,機能が制限されていたり,変な機能がついているものです.
基本的に必要な機能のみがついているものを使うと,速くて省メモリのはずです.
基本的に構造体の名前が segtree_[変更に対する対応クエリの羅列]_[取得に関する対応クエリの羅列] という形式になっています(長い…).
例えば,
segtree_Point_SumMin<T> t;
だと,変更に関するクエリの
void t.add(int x, T val)
void t.change(int x, T val)
と取得に関するクエリの
T t.getSum(int a, int b)
pair<T, int> t.getMin(int a, int b)
T t.getMinVal(int a, int b)
int t.getMinInd(int a, int b)
が使用できます.

変更に関するクエリと構造体の名前に含まれていたら使用できるという文字列(,で区切られている場合どれかが含まれていれば使用可能)

取得に関するクエリと構造体の名前に含まれていたら使用できるという文字列(,で区切られている場合どれかが含まれていれば使用可能)

定義されている構造体

その他の事項:
segtree_ChangeAdd_SumMin は通常の segtree を使ってください.
segtree_Point_Sum(1点更新で和を求めるだけのもの)はfenwickでできます(が,t.change(int x, T val) に対応するには値を配列などに保持し,差分を足してください).

グラフ(構造体)

graph構造体を使えます.graph g; などで定義します.

{
  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; などで定義します.

Heavy-Light Decomposition(HLD,重軽分解)

根付き無向木に対してHeavy-Light Decomposition(HLD)を計算します.
根はノード0を利用します.
計算したHLDを用いて,LCAなどを高速に求めることができます.
また,segtreeを載せることができます.
HLD hld; で定義したとします.

以下 HLD hld; の多分使わない情報.

Fenwick treeを載せるときは,HLD_fenwick<T> t; を定義します.
ノードに値を持ちます.
(枝に値をもたせたい場合は,すぐ上に向かう枝の値をノードに持たせて,LCAでパスを分割したりするとできるかも)

以下 HLD_fenwick<T> t; の多分使わない情報.

segtreeを載せるときは,HLD_segtree<T> t; を定義します.
ノードに値を持ちます.
(枝に値をもたせたい場合は,すぐ上に向かう枝の値をノードに持たせて,LCAでパスを分割したりするとできるかも)

以下 HLD_segtree<T> t; の多分使わない情報.

最大流(maxflow, Dinic)

最大流は maxflow<int,ll> flow; などで定義します.この場合,各辺の流量は int 型ですが,合計で流れる流量は ll 型です.
以下の説明では maxflow<T,S> 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; とします.
徐々に流していくアルゴリズムを適当に実装したもので,少なくても現状は良い実装ではないと思います.
負の閉路などがあると動きません.

AhoCorasick

あまりちゃんと verify してません.
AhoCorasick aho; で定義したとします.
最終的なノード数の上限を n(例えば食わせる文字列の文字数の和),アルファベットのサイズ(文字の種類数)を k として,aho.malloc(n, k); でメモリの確保+初期化します.
アルファベットは0からk-1までの数値です.
文字列を addWord でいくつか加えてTrieぽいグラフを作る.
そして,construct で failedリンクを作って準備完了です.

全ての文字列を区別する必要がなければ以下のもので十分かもしれません.

AhoCorasick_Sum<class S> aho; で定義したとします.
最終的なノード数の上限を n(例えば食わせる文字列の文字数の和),アルファベットのサイズ(文字の種類数)を k として,aho.malloc(n, k); でメモリの確保+初期化します.
アルファベットは0からk-1までの数値です.
文字列を addWord でいくつか加えてTrieぽいグラフを作る.
そして,construct で failedリンクを作って準備完了です.

AhoCorasickの使い方の参考:
AtCoder Beginner Contest #122 D問題 - We Like AGC

Polynomial(1変数多項式)

あまりちゃんと作っていません.
Polynomial<T> P; で作ります.定義域,値域ともにTです.
疎構造ではないので,次数の高い多項式は問答無用でたくさんの項を扱うことになって遅いです.
今のところ愚直な実装です.

コンストラクタ

デストラクタ

その他関数 [メンバ関数]

オペレーター [メンバ関数]

オペレーター [メンバ関数以外]

使わなさそうなの

  double x;
  Polynomial<double> P, Q, R1, R2; // P = Q = 0

  P.change(2, 1); // P = x^2
  P.change(1, 2); // P = x^2 + 2*x
  P.change(0, 1); // P = x^2 + 2*x + 1

  x = P(2); // P(2) = 2^2 + 2*2 + 1 = 9

  Q.change(1, 1); // Q = x
  Q.change(0, 4); // Q = x + 4

  // x^2 + 2*x + 1 = (x-2) (x+4) + 9
  R1 = P / Q;  // x - 2
  R2 = P % Q;  // 9

  Q *= 2.0; // 2x + 8

  // x^2 + 2x + 1 = (0.5x - 1) (2x + 8) + 9
  R1 = P / Q; // 0.5x - 1
  R2 = P % Q; // 9

  Q.change(1, 0); // Q = 8
  R1 = P / Q; // (1/8) x^2 + (1/4) x + (1/8);
  R2 = P % Q; // 0

その他色々な関数など

  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)を使って設定.

以下は微妙に仕様を決めきれてない.

以下はそのうち実装予定でまだ作ってない


unionfind構造体.unionFind uf; で宣言したとして以下の通り.

以下あまり使わないやつ


Timer構造体.時間を測るために使う.Timer timer;で宣言したとして以下の通り.gettimeofdayを使用する.

  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

  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)


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];
  }

  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 と表示

それぞれ単調性が成り立たなければならない.
例えば,bsearch_minの場合,name=10のときcondが成り立つならば,name=10以上(maxval以下)のときもcondは成り立たなければならない.
typeは変数nameの型を指定し,float, doubleの場合は実数の二分探索,それ以外は整数の二分探索を行う.
bsearch_minでは,name=maxvalでは評価されず,name=maxvalより小さい場合に常に偽ならmaxvalが返ってくる(name=maxvalのときはblock, condが未定義になるようなものでも良い).
今のところ,minval, maxvalは省略不可能.

optionは以下の通り.

実数の二分探索で,許容誤差を指定しない場合は,見ている範囲を[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

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

関数名がよく使う名前なのでこの機能を無効化するフラグがあります(フラグの欄を参照のこと).
引数の型は違っても構いませんが,計算途中でどのような型になるかは不明です(オーバーフローなどに注意).
今のところ,整数と浮動小数点数ぐらいでしか上手く動かないと思います.例外的に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


Comb 構造体は(1つ下のconbination_mintのように)階乗などを前計算しておき組合せ的な数を求める構造体です.
Comb<T> comb; で定義したとします.T は mint, modint, Mint, Modint のどれかを想定しています.
必要な値がない場合は,必要になったときに勝手に計算します.

使いそうなの

使わなさそうなの:変数

使わなさそうなの:関数


combination_mint は階乗とその逆数を前計算することで二項係数を高速に求めます.mint型で答えを返します.
構造体を使用しているので combination_mint comb; と最初に宣言して下さい.

  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個を選ぶ選び方

  int a = 32, b = 24;
  reduceFraction(a,b);
  wtF("{a}/{b}\n");         // 4/3 と表示

  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



  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

次元圧縮.多次元のグリッドでのBFSなどに.
構造体で,[x]次元のものは dimcomp[x] c; で定義したとする.2次元~5次元まで.

2次元 dimcomp2 c; で定義.

3次元 dimcomp3 c; で定義.

4次元 dimcomp4 c; で定義.

5次元 dimcomp5 c; で定義.

  int dx, dy, mask;
  dimcomp2 c(20,15);    // size = 20 x 15 (dimcomp2 c(15) でもほぼ同じ)
  dx = 3; dy = 9;
  mask = c(dx,dy);
  wt(mask);             // 3 * 15 + 9 = 54
  mask = c(dx+1, dy);
  wt(mask);             // 4 * 15 + 9 = 69
  c(mask,dx,dy);
  wt(dx,dy);            // dx = 4, dy = 9

  {
    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}
  }

  {
    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
  }

非負整数 x, y を2進数で書いたとき,xの1の桁がyの1の桁に包含されているとき,xはyに含まれると呼ぶことにする.
ZetaTransform は res[i] は jがiに包含されている整数を動くとき A[j] の和が代入されます.
メビウス変換はゼータ変換の逆変換です.

  int 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

res[i] は jがiに包含されている整数を動くとき A[j] の最小値 | 最大値を求めるのは以下の関数です.
小さい方から2個,3個求めるものもあります.この場合は,要素数が足りない場合は,numeric_limits<S>::max();が代入されます.


  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

いずれの関数も,空のmultiset, setを引数に取ってはいけません.


基本的にグレゴリオ暦を仮定



  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

  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;を想定.

累積和関係

縦横に連続する数


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;を想定.

累積和関係

縦横に連続する数


ビットに関すること.


FFTを用いて畳み込みを行います.
誤差がそれなりにのるので使用する際には注意.

  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

グラフの隣接リスト(隣接配列?)のようなものを作ります.
時間ごとにイベントを処理する場合などの整理などにも多分便利.

    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

ハンガリアン法.n ≤ m と仮定.
mat[0][c[0]] + mat[1][c[1]] + ... + mat[n-1][c[n-1]] の最小値を求める.ただし,c[i]は互いに異なる(c[i]は0以上m未満).
それを達成する配列cはmatch[]に代入して返す.matchにNULLにしておくと最小値だけ返す.


多項式補間(ラグランジュ補間).
f(x[i]) = y[i] (i=0,1,...,n-1)となる n-1 次以下の多項式 f を考える.


効率的な実装にはなっていない(遅い)です.
Explode("hoge,piyo,,123,", ",") は {"hoge", "piyo", "", "123", ""} を返します.
Explode("hoge,,,piyo,,123,", ",,") は {"hoge", ",piyo", "123,"} を返します.
v = {"hoge", "piyo", "", "123", ""} のとき Implode(v, "-") は "hoge-piyo--123-" を返します.


整数の平方根.(ただし n として ll でオーバーフロー直前みたいなのを引数に与えると動かない可能性が高い)

整数の立方根.
現在は非負整数に対応だが,将来的に負の整数に対応する可能性がある.その場合,Icbrt_s(-8) などは答えが変わる可能性があるので注意.



更新履歴

これ以前の更新履歴はこちら


Current time: 2021年10月28日00時20分06秒
Last modified: 2019年11月10日20時54分10秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン: