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


cLay概要(version 20170910-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;が最後に補われます.

変数宣言の順番は勝手に変わります.
また,変数宣言はブロックの最初に移動します.
変数宣言と同時に初期化する場合に注意して下さい.
変数宣言をした場所で変数を宣言したい場合は,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;

フラグ

途中で(プログラムの先頭が推奨)
//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の詳しい仕様はそのうち書きます.

入出力

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型の配列(文字列)にのみに対応.他の型もそのうち対応
また,char S[1000]; int N; rd(S@N);で文字列 S を読み込むと同時に文字列の長さを N に代入します.複数の文字列の場合は char S[10][1000]; int N[10]; rd(S@N(10)); とS@Nはひとかたまりで扱います.

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

ループ

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 がオーバーフローする可能性があるので要注意です.

べき乗演算子 ** が使えます.
2 ** 3 は $2^3 = 8$ を表します.
点 (x1, y1) と (x2, y2) とのユークリッド距離は sqrt( (x1-x2)**2 + (y1-y2)**2 ) と簡潔に書けるようになります.
バイナリ法などは使っておらず,愚直にやります.その為,1.0001**1d9 などは酷く時間がかかるので止めて下さい.
x ** y において,y は非負整数である必要があって,結果の型は x の型と同じになります(y が非負整数じゃない場合は標準の pow 関数などを使って下さい).

数値の後の掛け算の演算子*は省略できることがあります.
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) に * が補われることはありません.

不等式の条件を続けるときに && を省略できます.
if(5 < x+y < 10) は if(5 < x+y && x+y < 10) に置き換わります.
if(i <= 5 < k <= 12 > j) は if(i <= 5 && 5 < k && k <= 12 && 12 > j) に置き換わります.
if(5 < x++ < 10) は if(5 < x++ && x++ < 10) に置き換わるので注意してください.

定数

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; に(デフォルトで)64,000,000バイトのメモリが確保されます.

セグメントツリー

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

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

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

グラフ(構造体)

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
}

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

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

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

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

その他色々な関数など

  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を解放

  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)

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

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

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

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

更新履歴


Current time: 2024年03月29日10時36分53秒
Last modified: 2017年09月10日21時18分46秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン: