HackerRankのがっぽコンについて+Bitcoinの使い道
はじめに
この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの3日目の記事です。(遅れてしまいすみませんでした。)
皆様はHackerRankというコンテストサイトをご存知でしょうか。12/4現在、日本人登録者が490名で、他コンテストサイトに比べると国内ではまだまだ知名度が低そうです。
HackerRankでは様々なコンテストが開かれています:
- 1~2時間の短時間コンテスト(HourRank, 101 Hack)
- 1~3日のコンテスト(Codesprint, Ad Infinitum)
- 1週間に渡って毎日問題が追加されていくコンテスト(Week of Code)など。
また、コンテスト以外にも、特定のプログラミング言語や正規表現等様々なジャンルの学習にも使える教材がたくさんあるようです。(こちらは使ったことがないため、内容については分かりません。)
賞品つきコンテスト(通称:がっぽコン)
HackerRankではCodesprintと呼ばれる24-48時間コンテストが1-2ヶ月に1度くらい開催されていて、100位以内に入れば賞金(75ドル)とTシャツがもらえます。
前述のとおり知名度があまり高くないためか、100位以内を目指すのは他コンテストに比べて楽です。
賞金自体はBitcoinで送金されていますが、日本人参加者の感想を見ていると、Bitcoinをもらっても使い道に困る(hackos並にどうでもいい)、換金には海外口座がいるらしい、など色々な発言を見かけました。
普通にお金でもらうより使い所が限られていて不便そうですが、調べてみると意外と使い所があります。
Bitcoinの使い道の一例
使い道1: 食事
支払いにBitcoinが使えるお店が国内にいくつかあります。参考: ビットコインが使える日本のお店
実際にBitcoinでの支払いを試すのも兼ねて、にくがとうというお店に行きました。
お店のレビューはさておき(おいしかったです)、Bitcoinでの支払いはとても簡単で、QRコードをスマホで読み込むだけでした。
Bitcoinで支払う物好きな客は月に1,2人とのことでしたので、事前にBitcoinで支払う旨を伝えておいたほうがスムーズに会計が進んで良いと思います。
使い道2: ゲーム
SteamはBitcoinによる支払いに公式で対応しています。指定されたアドレスに指定されたBTCを送るだけで簡単にウォレットにチャージできます。
三が日までウィンターセールが開催されているので、今は買い時ですね。自分が買ってよかったと思うゲームを少し挙げます。
- La-Mulana
- 謎解き+アクション、どちらも難しくやりごたえがかなりある。セール中こんなにすごいゲームがコンビニ弁当より安く買えてしまってよいのだろうかと逆に申し訳なくなるレベル。
- Crypt of Necrodancer
- テンポに合わせて行動するローグライク。中毒性が高い。キャラクター別(10種くらい)で難易度がぜんぜん異なるので幅広く楽しめそう。
- Sid Meier's Civilization® V
- 文明の主導者となって、開拓したり他文明と交流しつつ勝利を目指すゲーム。セール中にDLCとまとめて買うのがよさそう。秋セールで一緒に買った人達が皆休日を溶かしてしまい、危険。
他にも面白そうなゲームはたくさんあるので、色々探してみるのも面白そうですね。
使い道3: 換金する
食事にもゲームにもあまり気が進まない方に朗報ですが、普通に換金できます。国内の口座に振り込んでくれる取引所を使います。私はcoincheckを使いました。
BTCで入金後、取引所で日本円に変えた後に自分の銀行口座に振り込みます。アカウント登録が必要だったり、振込手数料がかかったりはしますが、あまり手間はかからなかったように思います。
さらに野心のある方はcoincheck上でBitcoinでFXをすることもできます。私はFXでGTX1080を買う資金を捻出しようとして、逆にGTX1080相当以上の損失をしてしまったので、人におすすめはしません。なかなかうまくいかないものですね。
おわりに
- HackerRankのがっぽコンでがっぽがっぽしましょう。
- これからBitcoinの価値がどうなるか分かりませんが、幸いにも今は過去最高レベルで価値が高い状態なので、忘れていた方は使ってみてもいいかもしれませんね。
いろんな人のテンプレートを観察
この記事はCompetitive Programming Advent Calender(その2) 23日目の記事です。
はじめに
競技プログラミングでいろんな人のコードを読んでみると、前半部分には人によって色々なマクロや関数が定義されていたりいなかったりします。(参考: Quora)
この部分にはその人が快適にコーディングするための工夫が見られて面白いので、今回いろんな人のテンプレートを眺めてみることにしました。
実際に見たテンプレートはここ(Codeforces)とここ(KUPC)にまとめました。時間の都合上、それぞれ約50人、約30人しか見ていません。しかも途中で疲れてコメントがかなり雑です。すいません。
これらを見てどのような機能がテンプレートにあったか挙げていきたいと思います。
※この記事は競技プログラミングにある程度参加している人が読者であることを想定しています。そうではなくて、どうしてこんなものを使うの?と疑問がある方は、インターネットで検索するとQuoraにある質問等がヒットしますので、そちらを御覧ください。それでも尚分からない方にとっては、記事の内容が不健全に見えるでしょうから、注意して下さい。
よく見かける定番機能
指定回数ループして現時点の回数も分かるrepマクロ
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
定番のrepマクロです。マクロなので作法として大文字にする人がいたり、よく使うし最早rep文なので小文字にする人がいたりします。
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
これはnatsugiriさんのテンプレートから引用しました。repを使う時はほとんどの場合で第二引数の値が変わらないことを前提として使われますが、第二引数が何らかの関数(vectorのsize()とか)である場合にいちいち呼ぶと、例えそれがO(1)のsize()であっても、ループ回数が非常に多い場合はTLEしてしまう事が過去にありました。 これを避けるのが上記のマクロで、二重repの場合でもrepの第一引数に同じ名前の変数を使わない限りは変数名が被っていると怒られることはありません。
class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n; public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
こちらはrepマクロではないですが、機能が似ているのでここで紹介します。pythonのrangeみたいなものをC++でも扱うことができます。これはir5先生のテンプレートから引用しました。repマクロですが、冷静になると変数の宣言を一切してない点が気持ち悪いです。rangeクラスを使えば、変数を宣言していない問題は解決されます。
#define _overload3(_1,_2,_3,name,...) name #define _rep(i,n) repi(i,0,n) #define repi(i,a,b) for(int i=int(a);i<int(b);++i) #define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
こちらは可変長引数のrepマクロです。repの引数が2つの場合と3つの場合で_overload3
のnameが変わって挙動が変わります。(すごい) stqnさん、evimaさんのテンプレートにありました。
もう全部だしallマクロ
#define all(x) (x).begin(),(x).end()
sortやlower_boundする時に先頭と末尾のイテレータを渡すことはよくありますが、あまりにも頻出なためマクロで一纏めにしておくと便利です。
型名長杉、省略させて
using ll = long long; typedef long long ll; typedef long long int64; typedef long long lint; typedef long long lli;
long longはあまりにも頻出なので、もっと打ちやすく見た目もよい型名にエイリアスしている人が多いです。C++11から一番上みたいな記法もできるようになりました。 私事ですいません、自分はlint派なのですが、skyさんもlint派で感激しました。国内外問わずll派が圧倒的に多く、海外ではint64派も存在します。lintにしてるのは打ちやすさとintっぽさを残したかったからです。
size()がunsignedでつらい
#define SZ(x) ((int)(x).size())
unsignedなので加減算して思わぬバグを踏むことがあったり、intが絡む計算をするといちいち警告が出たりするので、それらを防ぐ目的のマクロです。
好みが分かれる機能
memsetマクロ
#define m0(x) memset(x,0,sizeof(x)) #define m1(x) memset(x,63,sizeof(x)) #define fill(x,y) memset(x,y,sizeof(x)) #define clr(ar,val) memset(ar, val, sizeof(ar)) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MEMSET(v, h) memset((v), h, sizeof(v))
いろんな人がいろんな名前でmemset絡みのマクロを作っています。 配列を何かで埋めたい場合に使う事が多いmemsetですが、第一引数と第三引数に大抵同じものを書くことになるので、マクロにするのも一つの手です。 埋める内容も大抵0, -1, 0x3fの3通りなので、それら毎にマクロを作ってもいいかもしれません。
デバッグ出力マクロ
#ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif
手元の環境でのみLOCALをdefineしておいて、上のように書くと手元ではデバッグ出力が見えて、ジャッジサーバーでの実行時には(LOCALが定義されていない限り)出力されません。
コンパイルオプションに-Dhogehoge
とするとhogehoge
がdefineされます。
海外勢のテンプレートでは上のようなeprintf
をよく見かけましたが、それ以外にも手元の環境でのみデバッグ出力用の関数が書かれたヘッダをインクルードして使う人もいます。
#ifdef LOCAL #include "dump.hpp" #else #define dump(...) #endif
最大値、最小値を更新する関数
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
sune2さんのテンプレートからの引用です。
if(hoge < fuga + piyo) hoge = fuga + piyo;
みたいなコードを書くと同じ部分が2箇所出てきて、配列の添字などが絡んでくると同じものを2つ書きたくないので、更新用の関数があると便利です。 また、値が更新された時に限りtrueを返すようにしておけば、例えばDPの経路を復元したい場合にきれいに書けます。
名前も色々付け方があり、umax(update?), amax(assign) とかにしている人がいます。
長いのは全部短く
#define pcnt __builtin_popcount #define buli(x) __builtin_popcountll(x) #define pb push_back #define mp make_pair #define F first #define S second
いろんな人からの引用です。 この辺はかなり好みが分かれますが、長いと打つのにも時間がかかるので、短く省略するのも一つの手です。
名前が被るのが嫌
#define y0 y3487465 #define y1 y8687969 #define j0 j1347829 #define j1 j234892 #define next asdnext #define prev asdprev
いろんな人からの引用です。 y0等は標準ライブラリ関数として存在しているので、変数名にy0等を使うと怒られます。それを避けるためにy0等を別の名前に置き換えます。
自前の入出力関数
AOJだと、readで全部入力を読んで自分でパースすると、入力が非常に大きい時には実行速度が結構速くなります。 getcharなどを使って入力を読んでパースしている人も少数ですが存在します。こだわりが垣間見えます。
確かに、scanfはやや長いし、cinは速度面で不満があるので、このような関数を自前で準備するのは一つの手です。
repの変種
#define REP(i,x) for(int i=0;i<(int)(x);i++) #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--)
zerokugiさんのテンプレートから引用です。名前は異なりますが同じようなマクロはそこそこ見かけました。zerokugiさんの場合は頭にRつけると逆向き、最後にSつけると1-originになるみたいです。
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
これは私のテンプレートからの引用です。順列を全通り試したい時に使います。
あると便利な機能は一応入れる
int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1};
jcvbさんから引用、冪乗計算やgcdやdxdyが必要な時にいちいち書かなくて済むという利点があります。
void precalc() { /*for (int i = 2; i < C; ++i) { if (!least_prime[i]) { least_prime[i] = i; for (li j = i * 1LL * i; j < C; j += i) { least_prime[j] = i; } } }*/ /*fact[0] = revfact[0] = 1; for (int i = 1; i < 100500; ++i) { fact[i] = fact[i - 1] * i % curMod; revfact[i] = binpow(fact[i], curMod - 2, curMod); }*/ /*for (int w = 0; w < 2; ++w) { powers[w][0] = 1; for (int j = 1; j < C; ++j) { powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w]; } }*/ /*catalan[0] = 1; for (int n = 0; n < 200500 - 1; ++n) { catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD; }*/ /*for (int i = 0; i < 5010; ++i) { c[i][i] = c[i][0] = 1; for (int j = 1; j < i; ++j) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD; } }*/ /*for (int i = 0; i < 100; ++i) { doubleC[i][i] = doubleC[i][0] = 1.0; for (int j = 1; j < i; ++j) { doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j]; } }*/ }
Kostromaさんから引用です。precalcの中に素数篩、階乗とあるmodでのその逆元、カタラン数、二項係数などがあり、アンコメントすることで使えるようになっています。
突き詰めるとライブラリを全部貼るのが一番便利なのかもしれません。
マイナーだけど面白いと思った機能
cauto
#define cauto const auto&
climpetさんのテンプレートからの引用です。結構使うのであると便利そうです。
bit(x)
#define bit(n) (1LL<<(n))
Mi_Sawaさんのテンプレートからの引用です。ビット演算の優先順序は正直覚えてなくて、書くといっつも括弧だらけになるし、たまにLLを忘れるので、あると便利そうです。
uniqueどうやるんだっけ?
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
zerokugiさんのテンプレートからの引用です。 長いし、(私は使い方を忘れるので、)マクロにしておくのも一つの手です。
打ち間違えても安心
#define itn int
Golovanov399さんから引用です。打ち間違いを直す時間すら惜しい。
最後は神頼み
提出したコードにバグがないことを祈り、バグを踏むケースがないことを祈りましょう。 hackしようとして開いていきなりこれが表示されると、なかなかインパクトを受けます。
その他
たまに見かけるおまじない
#pragma comment (linker, "/STACK:256000000")
スタック領域を拡張するおまじないだそうですが、MSVC++でしか効果がないそうです。
#define _CRT_SECURE_NO_WARNINGS
これもMSVC++だとscanf等のセキュリティが弱い古い関数を使った時の警告を抑制する効果があるそうですが、GNU g++ではおそらく無意味です。
#define _USE_MATH_DEFINES
これもMSVC++だとM_PIが使えるようになるらしいです。
ヘッダ
#include <bits/stdc++.h>
大抵のマシンでは<bits/stdc++.h>
で全部インクルードしても問題ないのですが、ICPC等でマシン環境がポンコツだった場合にこれをするとコンパイルに時間がかかるので注意が必要です。
やや脱線しますが、gnu g++では__gcd()
がstl_algo.h内で定義されているから自分でgcdは書かなくてもよいことはよく知られていますが、__lg()
という関数もあります。こちらは例えばセグメントツリーを作る時の配列のサイズを計算する時などに短く書けたりします。ここで挙げた機能は全てC++標準の機能ではありません。
main関数より先に呼びたい関数がある場合
例えばcin高速化などをしたい時など、main関数の冒頭部で必ず呼ぶ関数は別の箇所にまとめて記述することもできます。
struct aaa{ aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;
こういう構造体を実際に作ることでコンストラクタが呼ばれ、main関数より先に実行されます。
テンプレートが長すぎて見た目によくない場合
大抵のエディタには折りたたみ機能がついているのでそれで畳んであげると見た目はよくなります。
テンプレートの中身をあまりに常用するのでシンタックスハイライトで色を付けたい場合
私と同じエディタを使っている場合、私の設定がこちらにありますので、参考になるか分かりませんがご自由にお使い下さい。
デバッグ出力の見た目をよくしたい場合
私は(こんな感じ1), (こんな感じ2)にデバッグ用出力関数を書いてますが、まだ試行錯誤している段階です。便利そうなデバッグ出力の方法をご存知の方はどうか教えて下さい。
おわりに
明日はuvarimeronさんによる「実際に日常生活で役立った競技プログラミング」です。伊東家の食卓もびっくりなやつを期待しています。
2/24追記: コード片を着色・注意書きを追加
テンプレート観察メモ(KUPC)
敬称略、KUPC2015の提出(CFで見た人除く)、まとめはこちら。
kawatea
#include <cstdio> #include <cstdlib> #include <vector> using namespace std;
- なし
yutaka1999
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <functional> #include <map> #include <stack> #include <set> #include <string> #include <cmath> #define SIZE 105 using namespace std; typedef long long int ll; typedef pair <int,int> P;
- ll派
zerokugi
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <ctime> #include <queue> #include <stack> #include <algorithm> #include <list> #include <vector> #include <set> #include <map> #include <iostream> #include <deque> #include <complex> #include <string> #include <iomanip> #include <sstream> #include <bitset> #include <valarray> #include <unordered_map> #include <iterator> #include <functional> #include <cassert> using namespace std; typedef long long int ll; typedef unsigned int uint; typedef unsigned char uchar; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; #define REP(i,x) for(int i=0;i<(int)(x);i++) #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++) #define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++) #define ALL(container) (container).begin(), (container).end() #define RALL(container) (container).rbegin(), (container).rend() #define SZ(container) ((int)container.size()) #define mp(a,b) make_pair(a, b) #define pb push_back #define eb emplace_back #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } template<class T> ostream& operator<<(ostream &os, const vector<T> &t) { os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os; } template<class T> ostream& operator<<(ostream &os, const set<T> &t) { os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os; } template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";} template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);} template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);} const int INF = 1<<28; const double EPS = 1e-8; const int MOD = 1000000007;
- ll派
- pairの足し算引き算
- chmax, chmin
- REPマクロ、頭にRつけると逆向き、最後にSつけると1-origin
- uniqueは一連の操作をマクロに
sugim48
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { int u, v; ll w; }; ll MOD = 1000000007; ll _MOD = 1000000009; int INF = INT_MAX / 3; double EPS = 1e-10;
- 一行目はMSVC++だとM_PIが使えるようになる、他に意味があるかは不明
- repなし
- ll派
- MODが1e9+7と1e9+9の二種類をサポート
stqn
#include <bits/stdc++.h> using namespace std; #define _overload3(_1,_2,_3,name,...) name #define _rep(i,n) repi(i,0,n) #define repi(i,a,b) for(int i=int(a);i<int(b);++i) #define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
- repが引数の個数で変わる(2引数だと0からn-1, 3引数だとaからb-1) すごい
tomerun
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <vector> #include <map> #include <algorithm> #include <utility> #include <sys/time.h> using namespace std; typedef long long ll;
- ll派
__math
#define _CRT_SECURE_NO_DEPRECATE #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <limits> #include <ctime> #include <cassert> #include <map> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <stack> #include <queue> #include <numeric> #include <iterator> #include <bitset> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Pii; typedef pair<ll, ll> Pll; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) template<typename ...> static inline int getchar_unlocked(void) { return getchar(); } template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); } #define mygc(c) (c)=getchar_unlocked() #define mypc(c) putchar_unlocked(c) void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; } void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; } int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; } template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); } template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); } template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); } void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); } void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); } void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); } void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); } template<class T> void writerLn(T x) { writer(x, '\n'); } template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); } template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); } template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
- 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
- ll派
- 入出力が高速化されてそう
logicmachine
#include <string> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long ll;
- ll派
mamekin
#include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> using namespace std;
- なし
snuke
#include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <string.h> #include <cstdlib> #include <ctime> #include <cmath> #include <map> #include <set> #include <iostream> #include <sstream> #include <numeric> #include <cctype> #define fi first #define se second #define rep(i,n) for(int i = 0; i < n; ++i) #define rrep(i,n) for(int i = 1; i <= n; ++i) #define drep(i,n) for(int i = n-1; i >= 0; --i) #define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define rng(a) a.begin(),a.end() #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define pb push_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcount #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define df(x) int x = in() using namespace std; typedef long long int ll; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; inline int in() { int x; scanf("%d",&x); return x;} inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');} const int MX = 100005, INF = 1000010000; const ll LINF = 1000000000000000000ll; const double eps = 1e-10;
- rep, rrep, drep
- rngがいわゆるall
- snukeがsrand
- __builtin_popcount は確かに長い、pcnt
- ll派
- df(x)がxをintとして宣言して入力もとる
yuusti
#include <iostream> #include <algorithm> #include <string> #include <set> #include <vector> #include <queue> #include <tuple> #include <numeric> #include <sstream> #include <cassert> using namespace std;
- なし
こくりつくるめどうぶつえん
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define int long long
- 一番下はオーバーフローを防ぐ最終兵器
nisshy
// * template #include <bits/stdc++.h> #ifdef LOCAL #include "dump.hpp" #else #define dump(...) #endif using namespace std; template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; } template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; } template<class T, class U> inline void fill_array(T &e, const U &v) { e = v; } template<class T, class U, size_t s> inline void fill_array(T (&a)[s], const U &v) {for(auto&e:a)fill_array(e,v);} template<class T, class U, size_t s> inline void fill_array(array<T, s> &a, const U &v) {for(auto&e:a)fill_array(e,v);} template<class T, class U> inline void fill_array(vector<T> &a, const U &v) {for(auto&e:a)fill_array(e,v);}
- 手元でのみdump.hppをincludeしてデバッグ出力用のdump関数を使えるように
- 各種埋め関数
sky58
#include<vector> #include<cmath> #include<map> #include<cstdlib> #include<iostream> #include<sstream> #include<fstream> #include<string> #include<algorithm> #include<cstring> #include<cstdio> #include<set> #include<stack> #include<bitset> #include<functional> #include<ctime> #include<queue> #include<deque> #include<complex> using namespace std; #define pb push_back #define pf push_front typedef long long lint; typedef complex<double> P; #define mp make_pair #define fi first #define se second typedef pair<int,int> pint; #define All(s) s.begin(),s.end() #define rAll(s) s.rbegin(),s.rend() #define REP(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) REP(i,0,n) #define N 262144
- lint派だ!!(握手)
yuizumi
#include <iostream> #include <vector> #include <algorithm> using namespace std;
- なし
hongrock
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int T; typedef long long LL;
- LL派
Mi_Sawa
#include <bits/stdc++.h> #define all(x) begin(x),end(x) #define rall(x) (x).rbegin(),(x).rend() #define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i) #define rep(i,n) REP(i,0,n) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define repsz(i,v) rep(i,(v).size()) #define aur auto& #define bit(n) (1LL<<(n)) #define eb emplace_back #define mt make_tuple #define fst first #define snd second using namespace std; typedef long long ll; //#define int long long template<class C>int size(const C &c){ return c.size(); } template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;} template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
kmjp
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<to;x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //-------------------------------------------------------
- _Pがデバッグ出力用
- ZERO, MINUS がmemsetで0, -1埋め
(team)kirutos
#include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> #include<cmath> #include<climits> #include<string> #include<set> #include<map> using namespace std; #define rep(i,n) for(int i=0;i<((int)(n));i++) #define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++) #define irep(i,n) for(int i=((int)(n))-1;i>=0;i--) #define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--) typedef long long int lli; typedef pair<int,int> mp; #define fir first #define sec second #define IINF INT_MAX #define LINF LLONG_MAX
- lli派
- IINF, LINF
evima
// Enjoy your stay. #include <bits/stdc++.h> #define long long long #define LOOPVAR_TYPE long #define all(x) (x).begin(), (x).end() #define sz(x) ((LOOPVAR_TYPE)(x).size()) #define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++) #define GET_MACRO(_1, _2, _3, NAME, ...) NAME #define _rep(i, n) _rep2(i, 0, n) #define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++) #define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__) #define fir first #define sec second #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back const double EPS = 1e-9; const double PI = acos(-1.0); const long INF = 1070000000LL; const long MOD = 1000000007LL; using namespace std; typedef istringstream iss; typedef stringstream sst; typedef pair<LOOPVAR_TYPE, LOOPVAR_TYPE> pi; typedef vector<LOOPVAR_TYPE> vi;
#define long long long
なるほど (long double使う時は邪魔になる?)- repマクロが可変長引数で引数の個数によって変わる
amylase
#include <vector> #include <iostream> #include <algorithm> #include <set> #include <map> #include <queue> #include <cmath> using namespace std; typedef long long li; typedef long double real; #define rep(i, n) for(int i = 0; i < (int)(n); ++i)
- li派
climpet
#include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <deque> #include <complex> #include <stack> #include <queue> #include <cstdio> #include <cctype> #include <cstring> #include <ctime> #include <iterator> #include <bitset> #include <numeric> #include <list> #include <iomanip> #include <cassert> #if __cplusplus >= 201103L #include <array> #include <tuple> #include <initializer_list> #include <unordered_set> #include <unordered_map> #include <forward_list> #define cauto const auto& #define ALL(v) begin(v),end(v) #else #define ALL(v) (v).begin(),(v).end() #endif using namespace std; namespace{ typedef long long LL; typedef pair<int,int> pii; typedef pair<LL,LL> pll; typedef vector<int> vint; typedef vector<vector<int> > vvint; typedef vector<long long> vll, vLL; typedef vector<vector<long long> > vvll, vvLL; #define VV(T) vector<vector< T > > template <class T> void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){ v.assign(a, vector<T>(b, t)); } template <class F, class T> void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #define REP(i,n) for(int i=0;i<int(n);++i) #define RALL(v) (v).rbegin(),(v).rend() #define MOD 1000000007LL #define EPS 1e-8
- cauto よく使うし欲しい
- LL派
tanakh
#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std;
- なし
ここからはジャッジのみ見れるコードなのでリンクなし。
asi1024
#include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ALL(x) (x).begin(),(x).end() using namespace std; typedef long long ll;
- ll派
natsugiri
#include<cassert> #include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
- LL派
- amin, amax
- REPの第二引数を変数に代入
- eprintf
cos65535
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> #include <assert.h> #include <vector> #include <queue> #include <string> #include <map> #include <set> using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-9; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v))
- ll派
- memset 第一引数と第三引数は大抵こうなるのでこのマクロは欲しいかも
sune2
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);++i) #define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() #define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w) #define tpl(...) make_tuple(__VA_ARGS__) const int INF = 0x3f3f3f3f; const double EPS = 1e-8; const double PI = acos(-1); const int dy[] = {-1,0,1,0}; const int dx[] = {0,1,0,-1}; typedef long long ll; typedef pair<int,int> pii; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os, const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';} template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';} template<int N,class Tp>void output(ostream&,const Tp&){} template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);} template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';} template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20]; int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);} template<class T>void outputs(T t){output(t);} template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);} template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');} template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);} template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;); if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;} template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);} template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}
- chmin, chmax
#define tpl(...) make_tuple(__VA_ARGS__)
おもしろい- 入出力用の関数
ir5
#include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <vector> #include <sstream> #include <set> using namespace std; using ll = long long; class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n; public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
- ll派
- rangeクラス
chir
#include <iostream> #include <bitset> using namespace std; typedef long long ll;
- ll派
ichyo
// Template {{{ #include <bits/stdc++.h> #define REP(i,n) for(int i=0; i<(int)(n); ++i) using namespace std; typedef long long LL; #ifdef LOCAL #include "contest.h" #else #define dump(x) #endif const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; inline bool valid(int x, int w) { return 0 <= x && x < w; } void iostream_init() { ios::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(12); } //}}}
- LL派
- cin高速化
テンプレート観察メモ(Codeforces)
Codeforces上位50名のテンプレート、C++のみ、敬称略、まとめはこちら。
tourist
#include <bits/stdc++.h> using namespace std;
- テンプレートなし
TooSimple
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <cassert> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} // head
- rep, それを逆順にしたper
- all
- push_back, make_pair -> pb, mp
- first, second -> fi, se
- powmodがテンプレートにある
- vector, long long, pairをtypedef
rng_58
#include <iostream> #include <sstream> #include <fstream> #include <string> #include <vector> #include <deque> #include <queue> #include <stack> #include <set> #include <map> #include <algorithm> #include <functional> #include <utility> #include <bitset> #include <cmath> #include <cstdlib> #include <ctime> #include <cstdio> using namespace std; #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
- REP
- snuke
subscriber
#include<stdio.h> #include<iostream> #include<vector> #include<cmath> #include<algorithm> #include<memory.h> #include<map> #include<set> #include<queue> #include<list> #include<sstream> #include<cstring> #define mp make_pair #define pb push_back #define F first #define S second #define SS stringstream #define sqr(x) ((x)*(x)) #define m0(x) memset(x,0,sizeof(x)) #define m1(x) memset(x,63,sizeof(x)) #define CC(x) cout << (x) << endl #define pw(x) (1ll<<(x)) #define buli(x) __builtin_popcountll(x) #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
- first, second -> F, S
- memset0埋めマクロ
- forn: いわゆるrepマクロ
- CC(x) で出力, デバッグ用?
Petr
#include <vector> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long ll;
- long long -> ll
vepifanov
#include <cstdio> #include <numeric> #include <iostream> #include <vector> #include <set> #include <cstring> #include <string> #include <map> #include <cmath> #include <ctime> #include <algorithm> #include <bitset> #include <queue> #include <sstream> #include <deque> #include <cassert> using namespace std; #define mp make_pair #define pb push_back #define rep(i,n) for(int i = 0; i < (n); i++) #define re return #define fi first #define se second #define sz(x) ((int) (x).size()) #define all(x) (x).begin(), (x).end() #define sqr(x) ((x) * (x)) #define sqrt(x) sqrt(abs(x)) #define y0 y3487465 #define y1 y8687969 #define fill(x,y) memset(x,y,sizeof(x)) #define prev PREV #define j0 j1347829 #define j1 j234892 typedef vector<int> vi; typedef long long ll; typedef long double ld; typedef double D; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef vector<vi> vvi; template<class T> T abs(T x) { re x > 0 ? x : -x; }
- return -> re 普通にコード内でも使われている
- size()がunsignedなのをマクロ内でキャスト
- sqrt(x) 引数を0以上に
- y0, y1, j0, j1,prevを標準ライブラリ関数名などと被せないように
- 各種typedef
Um_nik
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <set> using namespace std; typedef long long ll; typedef pair<ll, int> pli; #define mp make_pair
- typedef
- make_pair -> mp
Endagorion
#include <iostream> #include <tuple> #include <sstream> #include <vector> #include <cmath> #include <ctime> #include <cassert> #include <cstdio> #include <queue> #include <set> #include <map> #include <fstream> #include <cstdlib> #include <string> #include <cstring> #include <algorithm> #include <numeric> #define mp make_pair #define mt make_tuple #define fi first #define se second #define pb push_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define forn(i, n) for (int i = 0; i < (int)(n); ++i) #define for1(i, n) for (int i = 1; i <= (int)(n); ++i) #define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i) using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii> vpi; typedef vector<vi> vvi; typedef long long i64; typedef vector<i64> vi64; typedef vector<vi64> vvi64; typedef pair<i64, i64> pi64; typedef double ld; template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
- forn, for1, ford, fore ループのマクロ fornとfordが順番逆、for1は右端含む、foreは区間
- uin, umax -> updateminの略?更新が起きた時に限りtrue
- all, rall
- 各種typedef
WJMZBMR
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> using namespace std; const int MOD = int(1e9) + 7; typedef long long int64;
- MOD
- long long -> int64
mnbvmar
#include <bits/stdc++.h> using namespace std; typedef long long LL; template<typename TH> void debug_vars(const char* data, TH head){ cerr << data << "=" << head << "\n"; } template<typename TH, typename... TA> void debug_vars(const char* data, TH head, TA... tail){ while(*data != ',') cerr << *data++; cerr << "=" << head << ","; debug_vars(data+1, tail...); } #ifdef LOCAL #define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #endif #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).begin())
- デバッグ用のマクロが可変長引数
- size()がunsignedなのでintにキャスト
scott_wu
#include <iostream> #include <algorithm> #include <cstdio> #include <vector> #include <string> #include <queue> using namespace std; typedef long long ll;
- ほぼなし
Egor
#include<cstdio> #include<cmath> #include<iostream> using namespace std;
- ほぼなし
Merkurev
#include <iostream> #include <vector> #include <cstdio> #include <algorithm> #include <set> #include <map> #include <cassert> #include <numeric> #include <string> #include <cstring> #include <cmath> using namespace std; #ifdef LOCAL #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif typedef long long int int64;
- デバッグ出力
qwerty787788
#include <bits/stdc++.h> using namespace std;
- なし
ecnerwal
#include<bits/stdc++.h> using namespace std; typedef double ld;
- double -> ld
niyaznigmatul
#include <cstdio>
- なし
yeputons
#include <iostream> #include <cstring> using namespace std;
- なし
PavelKunyavskiy
//#include <iostream> #include <fstream> #include <vector> #include <set> #include <map> #include <cstring> #include <string> #include <cmath> #include <cassert> #include <ctime> #include <algorithm> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <cstdlib> #include <cstdio> #include <iterator> #include <functional> #include <bitset> #define mp make_pair #define pb push_back #ifdef LOCAL #define eprintf(...) fprintf(stderr,__VA_ARGS__) #else #define eprintf(...) #endif #define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC) #define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, clock()*1.0/CLOCKS_PER_SEC) #if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L) #define LLD "%I64d" #else #define LLD "%lld" #endif using namespace std; #define TASKNAME "E" #ifdef LOCAL static struct __timestamper { string what; __timestamper(const char* what) : what(what){}; __timestamper(const string& what) : what(what){}; ~__timestamper(){ TIMESTAMPf("%s", what.data()); } } __TIMESTAMPER("end"); #else struct __timestamper {}; #endif typedef long long ll; typedef long double ld;
- aa
al13n
#define _CRT_SECURE_NO_DEPRECATE #define _USE_MATH_DEFINES #include <array> #include <iostream> #include <fstream> #include <cstdio> #include <cstdlib> #include <cassert> #include <climits> #include <ctime> #include <numeric> #include <vector> #include <algorithm> #include <bitset> #include <cmath> #include <cstring> #include <iomanip> #include <complex> #include <deque> #include <functional> #include <list> #include <map> #include <string> #include <sstream> #include <set> #include <unordered_set> #include <unordered_map> #include <stack> #include <queue> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef unsigned int uint; typedef unsigned char uchar; typedef double ld; typedef pair<int, int> pii; typedef pair<short, short> pss; typedef pair<LL, LL> pll; typedef pair<ULL, ULL> puu; typedef pair<ld, ld> pdd; template<class T> inline T sqr(T x) { return x * x; } template<class T> inline string tostr(const T & x) { stringstream ss; ss << x; return ss.str(); } inline LL parse(const string & s) { stringstream ss(s); LL x; ss >> x; return x; } #define left asdleft #define right asdright #define link asdlink #define unlink asdunlink #define next asdnext #define prev asdprev #define y0 asdy0 #define y1 asdy1 #define mp make_pair #define MT make_tuple #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define clr(ar,val) memset(ar, val, sizeof(ar)) #define istr stringstream #define forn(i,n) for(int i=0;i<(n);++i) #define forv(i,v) forn(i,sz(v)) #define X first #define Y second const ld EPS = 1e-12; const int INF = 1000*1000*1000; const LL LINF = INF * 1ll * INF; const ld DINF = 1e200; const ld PI = 3.1415926535897932384626433832795l; int gcd(int a,int b){return a?gcd(b%a,a):b;} LL gcd(LL a,LL b){return a?gcd(b%a,a):b;} LL powmod(LL a,LL p,LL m){LL r=1;while(p){if(p&1)r=r*a%m;p>>=1;a=a*a%m;}return r;} bool isprime(LL a){if(a<=1)return false;for (LL i=2;i*i<=a;++i){if(a%i==0)return false;}return true;} LL sqrtup(LL a){if(!a)return 0;LL x=max(0ll,(LL)sqrt((ld)a));while(x*x>=a)--x;while((x+1)*(x+1)<a)++x;return x+1;} LL sqrtdown(LL a){LL x=max(0ll,(LL)sqrt((ld)a));while(x*x>a)--x;while((x+1)*(x+1)<=a)++x;return x;} template<class T> ostream& operator<<(ostream &s, const vector<T> &v); template<class A,class B> ostream& operator<<(ostream &s, const pair<A,B> &p); template<class K,class V> ostream& operator<<(ostream &s, const map<K,V> &m); template<class T,size_t N> ostream& operator<<(ostream &s, const array<T,N> &a); template<class T> ostream& operator<<(ostream &s, const vector<T> &v){s<<'[';forv(i,v){if(i)s<<',';s<<v[i];}s<<']';return s;} template<class A,class B> ostream& operator<<(ostream &s, const pair<A,B> &p){s<<"("<<p.X<<","<<p.Y<<")";return s;} template<class K,class V> ostream& operator<<(ostream &s, const map<K,V> &m){s<<"{";bool f=false;for(const auto &it:m){if(f)s<<",";f=true;s<<it.X<<": "<<it.Y;}s<<"}";return s;} template<class T,size_t N> ostream& operator<<(ostream &s, const array<T,N> &a){s<<'[';forv(i,a){if(i)s<<',';s<<a[i];}s<<']';return s;} template<size_t n,class... T> struct put1 { static ostream& put(ostream &s, const tuple<T...> &t){s<<get<sizeof...(T)-n>(t);if(n>1)s<<',';return put1<n-1,T...>::put(s,t);} }; template<class... T> struct put1<0,T...> { static ostream& put(ostream &s, const tuple<T...> &t){return s;} }; template<class... T> ostream& operator<<(ostream &s, const tuple<T...> &t){s<<"(";put1<sizeof...(T),T...>::put(s,t);s<<")";return s;} ostream& put2(ostream &s, const tuple<> &t){return s;} template<class U> ostream& put2(ostream &s, const tuple<U> &t){return s<<get<0>(t);} template<class U,class V,class... T> ostream& put2(ostream &s, const tuple<U,V,T...> &t){return s<<t;} #ifdef __ASD__ #define dbg(...) do { cerr << #__VA_ARGS__ << " = "; put2(cerr, make_tuple(__VA_ARGS__)); cerr << endl; }while(false) #else #define dbg(...) do{}while(false) #endif
- 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
- 二番目はM_PI使う用
izrak
#include <bits/stdc++.h> #define FO(i,a,b) for (int i = (a); i < (b); i++) #define sz(v) int(v.size()) using namespace std;
- FO: ループ
- size()をintにキャスト
jcvb
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> #include<map> #include<set> #include<queue> #include<bitset> using namespace std; typedef long long ll; typedef double db; const db pi=acos(-1); void gn(int &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } void gn(ll &x){ int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-'); if(c=='-')sg=-1,x=0;else x=c-'0'; while((c=getchar())>='0'&&c<='9')x=x*10+c-'0'; x*=sg; } const int mo=1000000007; const int inf=1061109567; //const ll inf=1000000000000000000ll; int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;} int gcd(int a,int b){return b?gcd(b,a%b):a;} int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; #define x1 x192837465 #define x2 x123456789 #define y1 y192837465 #define y2 y123456789 using namespace std;
- 自前の入力関数
- qp: 累乗の高速計算、MODありなしどっちも
- gcd
- dx, dy
- x1, y1が被らないように
dreamoon
#include <bits/stdc++.h> #define SZ(X) ((int)(X).size()) #define ALL(X) (X).begin(), (X).end() #define REP(I, N) for (int I = 0; I < (N); ++I) #define REPP(I, A, B) for (int I = (A); I < (B); ++I) #define RI(X) scanf("%d", &(X)) #define RII(X, Y) scanf("%d%d", &(X), &(Y)) #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z)) #define DRI(X) int (X); scanf("%d", &X) #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y) #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z) #define RS(X) scanf("%s", (X)) #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0) #define MP make_pair #define PB push_back #define MS0(X) memset((X), 0, sizeof((X))) #define MS1(X) memset((X), -1, sizeof((X))) #define LEN(X) strlen(X) #define PII pair<int,int> #define VI vector<int> #define VPII vector<pair<int,int> > #define PLL pair<long long,long long> #define VPLL vector<pair<long long,long long> > #define F first #define S second typedef long long LL; using namespace std;
- size()をintにキャスト
- all
- rep, repp
- 入力がマクロ
- 変数宣言して入力するマクロ
Kostroma
#pragma comment (linker, "/STACK:1280000000") #define _CRT_SECURE_NO_WARNINGS //#include "testlib.h" #include <cstdio> #include <cassert> #include <algorithm> #include <iostream> #include <memory.h> #include <string> #include <vector> #include <set> #include <map> #include <cmath> #include <bitset> #include <deque> #include <unordered_map> #include <unordered_set> #include <ctime> #include <stack> #include <queue> #include <fstream> #include <sstream> #include <complex> using namespace std; //#define FILENAME "" #define mp make_pair #define all(a) a.begin(), a.end() typedef long long li; typedef long double ld; void solve(); void precalc(); clock_t start; //int timer = 1; int testNumber = 1; bool todo = true; int main() { #ifdef room111 freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #else //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); //freopen(FILENAME".in", "r", stdin); //freopen(FILENAME ".out", "w", stdout); #endif start = clock(); int t = 1; cout.sync_with_stdio(0); cin.tie(0); precalc(); cout.precision(10); cout << fixed; //cin >> t; int testNum = 1; while (t--) { //cout << "Case #" << testNum++ << ": "; solve(); ++testNumber; //++timer; } #ifdef room111 cerr << "\n\n" << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n"; #endif return 0; } //BE CAREFUL: IS INT REALLY INT? //#define int li /*int pr[] = { 97, 2011 }; int mods[] = { 1000000007, 1000000009 }; const int C = 300500; int powers[2][C];*/ //int MOD = 1000000007; //int c[5010][5010]; //int catalan[200500]; //ld doubleC[100][100]; template<typename T> T binpow(T q, T w, T mod) { if (!w) return 1 % mod; if (w & 1) return q * 1LL * binpow(q, w - 1, mod) % mod; return binpow(q * 1LL * q % mod, w / 2, mod); } /*int curMod = 1000000009; int fact[100500], revfact[100500]; int getC(int n, int k) { int res = fact[n] * revfact[n - k] % curMod * revfact[k] % curMod; return res; }*/ //const int C = 500500; //int least_prime[C]; void precalc() { /*for (int i = 2; i < C; ++i) { if (!least_prime[i]) { least_prime[i] = i; for (li j = i * 1LL * i; j < C; j += i) { least_prime[j] = i; } } }*/ /*fact[0] = revfact[0] = 1; for (int i = 1; i < 100500; ++i) { fact[i] = fact[i - 1] * i % curMod; revfact[i] = binpow(fact[i], curMod - 2, curMod); }*/ /*for (int w = 0; w < 2; ++w) { powers[w][0] = 1; for (int j = 1; j < C; ++j) { powers[w][j] = (powers[w][j - 1] * 1LL * pr[w]) % mods[w]; } }*/ /*catalan[0] = 1; for (int n = 0; n < 200500 - 1; ++n) { catalan[n + 1] = catalan[n] * 2 * (2 * n + 1) % MOD * binpow(n + 2, MOD - 2, MOD) % MOD; }*/ /*for (int i = 0; i < 5010; ++i) { c[i][i] = c[i][0] = 1; for (int j = 1; j < i; ++j) { c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD; } }*/ /*for (int i = 0; i < 100; ++i) { doubleC[i][i] = doubleC[i][0] = 1.0; for (int j = 1; j < i; ++j) { doubleC[i][j] = doubleC[i - 1][j - 1] + doubleC[i - 1][j]; } }*/ } template<typename T> T gcd(T q, T w) { while (w) { q %= w; swap(q, w); } return q; } template<typename T> T lcm(T q, T w) { return q / gcd(q, w) * w; } //#define int li //const int mod = 1000000007; typedef double ldd; #define double ld
- 一番上の行はスタックを拡張するおまじないだが、MSVC++でしか意味が無い
- 二行目はこれまたMSVC++にしか関係なくて、scanf等のバッファオーバーランが発生する可能性のある関数を使った時の警告を抑制するらしい
- precalcの中に素数篩、階乗とあるmodでのその逆元、カタラン数、二項係数などがあり、コメントアウトすることで使えるようになってる
- gcd, lcm
Marcin_smu
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long LL; typedef double D; #define FI first #define SE second #define MP make_pair #define PB push_back #define R(I,N) for(int I=0;I<N;I++) #define F(I,A,B) for(int I=A;I<B;I++) #define FD(I,N) for(int I=N-1;I>=0;I--) #define make(A) scanf("%d",&A) #define make2(A,B) scanf("%d%d",&A,&B) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) template<typename C> void maxi(C& a,C b){if(a<b)a=b;} template<typename C> void mini(C& a,C b){if(a>b)a=b;} template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a){ while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } #ifdef LOCAL #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #define debugv(C) {for(auto&c:C)cerr<<c<<",";cerr<<endl;} #else #define debug(...) (__VA_ARGS__) #define debugv(C) {} #define cerr if(0)cout #endif
- R, F, FDがループマクロ
- デバッグ用関数
overtroll
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> #include <set> #include <map> #include <cmath> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <queue> #include <stack> #include <bitset> #define fs first #define sc second #define mp make_pair #define pb push_back #define mt make_tuple #define NAME "" using namespace std; typedef long long ll; typedef long double ld; const ld PI = acos(-1.0);
- first, second -> fs, sc
- make_tuple -> mt
RAD
#define _CRT_SECURE_NO_DEPRECATE #define _SECURE_SCL 0 #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <map> #include <set> #include <string> #include <utility> #include <vector> #include <iostream> #include <queue> #include <deque> #include <stack> #include <list> #include <cctype> #include <sstream> #include <cassert> #include <bitset> #include <memory.h> #include <complex> #include <iomanip> using namespace std; #pragma comment(linker, "/STACK:200000000") typedef long long int64; #define forn(i, n) for(int i = 0; i < (int)(n); i++) #define ford(i, n) for(int i = (int)(n) - 1; i >= 0; i--) #define fore(i, a, n) for(int i = (int)(a); i < (int)(n); i++) #define pb push_back #define mp make_pair #define fs first #define sc second #define last(a) (int(a.size()) - 1) #define all(a) a.begin(), a.end() const double EPS = 1E-9; const int INF = 1000000000; const int64 INF64 = (int64) 1E18; const double PI = 3.1415926535897932384626433832795; const int CMAX = 1100000; const int64 MOD = INF + 7;
- 一番上はscanf等の警告抑制?GNU g++で効果あるかは不明
- last: 最後のインデックス
TankEngineer
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;
- なし
Swistakk
#include <bits/stdc++.h> #define MP make_pair #define PB push_back #define st first #define nd second #define rd third #define FOR(i, a, b) for(int i =(a); i <=(b); ++i) #define RE(i, n) FOR(i, 1, n) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) using namespace std; template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; } template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) { while(*sdbg != ',')cerr<<*sdbg++; cerr<<"="<<h<<","; _dbg(sdbg+1, t...); } #ifdef LOCAL #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }} #else #define debug(...) (__VA_ARGS__) #define debugv(x) #define cerr if(0)cout #endif #define make(type, x) type x; cin>>x; #define make2(type, x, y) type x, y; cin>>x>>y; #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z; #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t; #define next ____next #define prev ____prev #define left ____left #define hash ____hash typedef long long ll; typedef long double LD; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VLL; typedef vector<pair<int, int> > VPII; typedef vector<pair<ll, ll> > VPLL; template<class C> void mini(C&a4, C b4){a4=min(a4, b4); } template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); } template<class T1, class T2> ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";} template<class A, class B, class C> struct Triple { A first; B second; C third; bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } }; template<class T> void ResizeVec(T&, vector<int>) {} template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) { vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; } for (T& v : vec) { ResizeVec(v, sz); } } typedef Triple<int, int, int> TIII; template<class A, class B, class C> ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; } template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; } typedef pair<int, bool> PIB;
- next, prev, left, hash
anta
#include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <cassert> #include <limits> #include <functional> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll; template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
- aut
- amin, amax
- rep, rer, reu
sdya
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <string> #include <queue> #include <set> #include <map> #include <bitset> #include <cmath> #include <stack> #include <ctime> #include <unordered_map> #include <unordered_set> #pragma comment (linker, "/STACK:256000000") using namespace std;
- 下から二番目はスタックを拡張するおまじないだが、MSVC++でしか意味が無い
bmerry
#include <bits/stdc++.h> /*** TEMPLATE CODE STARTS HERE ***/ using namespace std; typedef vector<int> vi; typedef vector<string> vs; typedef long long ll; typedef complex<double> pnt; typedef pair<int, int> pii; #define RA(x) begin(x), end(x) #define FE(i, x) for (auto i = begin(x); i != end(x); ++i) #define SZ(x) ((int) (x).size()) template<class T> void splitstr(const string &s, vector<T> &out) { istringstream in(s); out.clear(); copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out)); } template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } static void redirect(int argc, const char **argv) { ios::sync_with_stdio(false); if (argc > 1) { static filebuf f; f.open(argv[1], ios::in); cin.rdbuf(&f); if (!cin) { cerr << "Failed to open '" << argv[1] << "'" << endl; exit(1); } } if (argc > 2) { static filebuf f; f.open(argv[2], ios::out | ios::trunc); cout.rdbuf(&f); if (!cout) { cerr << "Failed to open '" << argv[2] << "'" << endl; } } } /*** TEMPLATE CODE ENDS HERE */
- redirect: main関数の最初に呼び出してリダイレクトする
TeaPot
#include <cstdio> #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <set> #include <map> #include <ctime> #include <cstring> #include <cassert> #include <bitset> #include <sstream> #include <queue> #define pb push_back #define mp make_pair #define fs first #define sc second #define sz(a) ((int) (a).size()) #define eprintf(...) fprintf(stderr, __VA_ARGS__) using namespace std; typedef long long int64; typedef long double ldb; const long double eps = 1e-9; const int inf = (1 << 30) - 1; const long long inf64 = ((long long)1 << 62) - 1; const long double pi = acos(-1); template <class T> T sqr (T x) {return x * x;} template <class T> T abs (T x) {return x < 0 ? -x : x;}
- eprintf
- sqr, abs
Shik
// {{{ by shik #include <bits/stdc++.h> #include <unistd.h> #define SZ(x) ((int)(x).size()) #define ALL(x) begin(x),end(x) #define REP(i,n) for ( int i=0; i<int(n); i++ ) #define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ ) #define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ ) #define MP make_pair #define PB push_back using namespace std; typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; #ifdef SHIK template<typename T> void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; } template<typename T, typename... Args> void _dump( const char* s, T&& head, Args&&... tail ) { int c=0; while ( *s!=',' || c!=0 ) { if ( *s=='(' || *s=='[' || *s=='{' ) c++; if ( *s==')' || *s==']' || *s=='}' ) c--; cerr<<*s++; } cerr<<"="<<head<<", "; _dump(s+1,tail...); } #define dump(...) do { \ fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \ _dump(#__VA_ARGS__, __VA_ARGS__); \ } while (0); template<typename Iter> ostream& _out( ostream &s, Iter b, Iter e ) { s<<"["; for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it; s<<"]"; return s; } template<typename A, typename B> ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; } template<typename T> ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); } template<typename T, size_t N> ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); } template<typename T> ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); } template<typename A, typename B> ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); } #else #define dump(...) #endif template<typename T> void _R( T &x ) { cin>>x; } void _R( int &x ) { scanf("%d",&x); } void _R( long long &x ) { scanf("%" PRId64,&x); } void _R( double &x ) { scanf("%lf",&x); } void _R( char &x ) { scanf(" %c",&x); } void _R( char *x ) { scanf("%s",x); } void R() {} template<typename T, typename... U> void R( T& head, U&... tail ) { _R(head); R(tail...); } template<typename T> void _W( const T &x ) { cout<<x; } void _W( const int &x ) { printf("%d",x); } template<typename T> void _W( const vector<T> &x ) { for ( auto i=x.cbegin(); i!=x.cend(); i++ ) { if ( i!=x.cbegin() ) putchar(' '); _W(*i); } } void W() {} template<typename T, typename... U> void W( const T& head, const U&... tail ) { _W(head); putchar(sizeof...(tail)?' ':'\n'); W(tail...); } // }}}
- 入出力
Golovanov399
#include <bits/stdc++.h> #define itn int #define LL long long #define pb push_back #define mp make_pair #define x first #define y second #define all(x) (x).begin(), (x).end() using namespace std; inline int nxt(){ int x; scanf("%d", &x); return x; }
- nxt
#define itn int
おもしろい
izban
#include <sstream> #include <vector> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <string> #include <cassert> #include <ctime> #include <map> #include <math.h> #include <cstdio> #include <set> #include <deque> #include <memory.h> #include <queue> #pragma comment(linker, "/STACK:64000000") typedef long long ll; using namespace std; const int MAXN = -1; const int MOD = 1; // 1000 * 1000 * 1000 + 7;
- なし
kcm1700
#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <set> #include <map> #include <climits> #include <cstdint> #include <string> #include <cstring> using namespace std;
- なし
enot.1.10
/** * author: enot.1.10, (concealed) * created: 19.12.2015 13:55:16 **/ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <ctime> #include <cassert> #include <queue> #define fs first #define sc second #define F first #define S second #define pb push_back #define mp make_pair #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i) #define forit(it,v) for(typeof((v).begin()) it = v.begin() ; it != (v).end() ; ++it) #define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define sz(a) ((int)(a).size()) #define all(a) (a).begin(),a.end() #define pw(x) (1LL<<(x)) using namespace std; typedef long long ll; typedef double dbl; typedef vector<int> vi; typedef pair<int, int> pi; const int inf = (int)1.01e9; const dbl eps = 1e-9; /* --- main part --- */
- 本名日時が入るようになってる
- eprintf 可変長引数のデバッグ出力用マクロ
Belonogov
#include <iostream> #include <cmath> #include <vector> #include <map> #include <set> #include <string> #include <cstring> #include <queue> #include <ctime> #include <cassert> #include <cstdio> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <bitset> using namespace std; #define fr first #define sc second #define mp make_pair #define pb push_back #define epr(...) fprintf(stderr, __VA_ARGS__) #define db(x) cerr << #x << " = " << x << endl #define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; #define all(a) (a).begin(), (a).end() #define equal equalll #define less lesss const int N = -1; const long long INF = 1e9 + 19; typedef unsigned long long ull;
- equal, lessが被らないように
- このデバッグ出力結構見るなぁ
-XraY-
#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <set> #include <map> #include <cassert> #include <ctime> #include <string> #include <queue> using namespace std; #ifdef _WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif typedef long double ld; long long rdtsc() { long long tmp; asm("rdtsc" : "=A"(tmp)); return tmp; } inline int myrand() { return abs((rand() << 15) ^ rand()); } inline int rnd(int x) { return myrand() % x; } #define pb push_back #define mp make_pair #define eprintf(...) fprintf(stderr, __VA_ARGS__) #define sz(x) ((int)(x).size()) #define TASKNAME "text" const int INF = (int) 1.01e9; const ld EPS = 1e-9;
- rdtsc()はインラインアセンブラでrdtsc命令してる、時間計測用
mR.ilchi
#include <bits/stdc++.h> using namespace std;
- なし
hogloid
#include<bits/stdc++.h> #define REP(i,m) for(int i=0;i<(m);++i) #define REPN(i,m,in) for(int i=(in);i<(m);++i) #define ALL(t) (t).begin(),(t).end() #define CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; #ifndef ONLINE_JUDGE #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} #else #define dump(x) ; #define prl ; template<class T> void debug(T a,T b){ ;} #endif template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<int,int> pi; namespace std{ template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.fr<<','<<a.sc<<')'; return out; } } lint readL(){ lint res; #ifdef ONLINE_JUDGE scanf("%I64d",&res); #else scanf("%lld",&res); #endif return res; } void printL(lint res){ #ifdef ONLINE_JUDGE printf("%I64d",res); #else printf("%lld",res); #endif }
- CFは%lldが入ってると警告が出るけど無視しても問題ないらしい(警告を二度と表示しないというチェックボックスがあるので選択)
wjh720
#include <bits/stdc++.h> #define fi first #define se second #define PA pair<int,int> #define VI vector<int> #define VP vector<PA > #define mk(x,y) make_pair(x,y) #define int64 long long #define db double #define N 300010 #define P 100000000001101ll #define wei 31 #define For(i,x,y) for (i=x;i<=y;i++) using namespace std;
- int64
RomaWhite
#include <string> #include <vector> #include <map> #include <list> #include <iterator> #include <set> #include <queue> #include <iostream> #include <sstream> #include <stack> #include <deque> #include <cmath> #include <memory.h> #include <cstdlib> #include <cstdio> #include <cctype> #include <algorithm> #include <utility> #include <cassert> #include<complex> #include <time.h> using namespace std; #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i) #define FILL(A,value) memset(A,value,sizeof(A)) #define ALL(V) V.begin(), V.end() #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define Pi 3.14159265358979 #define x0 ikjnrmthklmnt #define y0 lkrjhkltr #define y1 ewrgrg typedef long long Int; typedef unsigned long long UInt; typedef vector<int> VI; typedef pair<int, int> PII; typedef complex<double> base;
- Int派
step4
#include<bits/stdc++.h> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define FZ(n) memset((n),0,sizeof(n)) #define FMO(n) memset((n),-1,sizeof(n)) #define MC(n,m) memcpy((n),(m),sizeof(n)) #define F first #define S second #define MP make_pair #define PB push_back #define FOR(x,y) for(__typeof(y.begin())x=y.begin();x!=y.end();x++) #define IOS ios_base::sync_with_stdio(0); cin.tie(0) // Let's Fight!
- IOS; でcin高速化()
Zlobober
#include <cstdio> #include <cassert> #include <memory.h> #include <iostream> #include <tuple> using namespace std; typedef long long llong;
- llong派
W4yneb0t
#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<map> #include<queue> #include<cassert> #define PB push_back #define MP make_pair #define sz(v) (in((v).size())) #define forn(i,n) for(in i=0;i<(n);++i) #define forv(i,v) forn(i,sz(v)) #define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i) #define all(v) (v).begin(),(v).end() using namespace std; typedef long long in; typedef vector<in> VI; typedef vector<VI> VVI;
- in派
ershov.stanislav
#include <bits/stdc++.h> #define mp make_pair #define fs first #define sc second #define pb push_back #define eb emplace_back #define all(s) (s).begin(), (s).end() #define sz(s) ((int) ((s).size())) typedef long long ll; typedef long double ld; const int INF = 1e9; const ll lINF = 1e18; const double EPS = 1e-12; #ifdef _WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif using namespace std;
- ll派
- CF環境では_WIN32が定義されている
ilyakor
#include <string> #include <algorithm> #include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <sstream> #include <cmath> #include <cassert> #include <queue> #include <bitset> #include <map> #include <set> #define pb push_back #define mp make_pair #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() using namespace std; typedef long long int64; typedef pair<int, int> ii; typedef vector<int> vi;
- int64派
AOJ 1334 Cubic Colonies
これはAOJ-ICPC Advent Calendar 2015の2日目の記事です。
AOJ自体長らく触っていませんが、自分が解いたことのある問題の中で「AOJ (問題番号)」でぐぐっても解説記事が出てこない問題がないか探して、この問題について書くことにしました。
問題: Cubic Colonies | Aizu Online Judge
2012年のICPC地区予選の最終防衛問題で、本番中に解かれた問題です。
複数の立方体からなる物体があり、物体の表面にはケーブルを敷くことができます。物体の表面上の2点が与えられるので、その間を結ぶ長さ最小のケーブルを求めて下さい。
内容把握したと思いつつ問題文の下にある図が目に入ると「そんなところも通れるんかーい!」とツッコまずにはいられません。
物理的に可能かどうかはさておき、表面であれば自由にケーブルを敷けるということで、表面に頂点と辺を追加して最短経路問題にして解けます。
解法
どこに面があるか調べる
隣り合ったマスの片方のみに物体があれば面ができます。
面に頂点と辺を加える
ケーブルがどのように敷かれるか展開図で考えてみると、2つの格子点間を結ぶ線分の組み合わせになることが分かります。サイズもと小さいので、一つの線分もせいぜい程度に収まりそうです。で、ひとつの面だけ取り出してみると、長さ1の線分を[0,1]とみなして0,1,{n/m; 0 < n < m <= D}に頂点を置く、というのを全ての辺についてやって、異なる辺にある2つの頂点間に辺を張ればよいです。分母の最大値をDと置いてますが、そんなに大きくなりそうにないのでコード内ではとりあえず9にしています。
感想
やることを挙げると大した事はないですが、実装量は意外とあって、その割にはライブラリで殴る問題でもない不思議な問題でした。デバッグがつらい。
コード
2年前のクソコード
#include <bits/stdc++.h> #define iter(i,s,n) for(int i=int(s);i<int(n);i++) #define rep(i,n) iter(i,0,n) #define all(c) (c).begin(), (c).end() using namespace std; typedef long long ll; template<class T>void chmin(T &t, T f){if(t > f)t = f;} int gcd(int a,int b){return b?gcd(b,a%b):a;} vector<double> frac; struct edge{int to;double cost;}; struct edgeid{int x,y,z,d;}; vector<edge> G[8000]; int edge_id(int x,int y,int z,int d){return ((x*4+y)*4+z)*3+d;} int edge_ide(edgeid e){return edge_id(e.x,e.y,e.z,e.d);} int node_id(int x,int y,int z, int d,int f){return edge_id(x,y,z,d)*frac.size()+f;} int node_ide(edgeid e, int f){return node_id(e.x,e.y,e.z,e.d,f);} struct node{double x,y,z;}; node no[8000]; void print_node(node a){printf("%f %f %f\n",a.x,a.y,a.z);} void print(int id){print_node(no[id]);} double d[8000]; void connect(int x,int y,int z,int d){ int S = frac.size(); int added = 0; //printf("<%d %d %d %c>\n",x,y,z,d+'x'); //x //e[x,y,z,2], e[x,y,z,3], e[x,y+1,z,2], e[x,y,z+1,3] vector<edgeid> f; if(d==0){ //printf("<%d %d %d x>\n",x,y,z); f.push_back({x,y,z,1}); f.push_back({x,y,z,2}); f.push_back({x,y,z+1,1}); f.push_back({x,y+1,z,2}); } //y if(d==1){ //printf("<%d %d %d y>\n",x,y,z); f.push_back({x,y,z,0}); f.push_back({x,y,z,2}); f.push_back({x,y,z+1,0}); f.push_back({x+1,y,z,2}); } //z if(d==2){ //printf("<%d %d %d z>\n",x,y,z); f.push_back({x,y,z,0}); f.push_back({x,y,z,1}); f.push_back({x,y+1,z,0}); f.push_back({x+1,y,z,1}); } //mukaiau rep(i1,2){ //printf("[[%s++]]\n",d==1?i1?"z":"y":d==2?i1?"z":"x":i1?"y":"x"); rep(j1,S){ int s = node_ide(f[i1],j1); rep(j2,S){ int t = node_ide(f[i1+2],j2); double d = hypot(1.0,frac[j1]-frac[j2]); G[s].push_back({t,d}); G[t].push_back({s,d}); //print(s); print(t); printf("%f\n",d); added++; } } } //tonariau rep(j1,S){ int s = node_ide(f[0],j1); rep(j2,S){ int t = node_ide(f[1],j2); double d = hypot(frac[j1],frac[j2]); G[s].push_back({t,d}); G[t].push_back({s,d}); added++; } } rep(j1,S){ int s = node_ide(f[0],j1); rep(j2,S){ int t = node_ide(f[3],j2); double d = hypot(1-frac[j1],frac[j2]); G[s].push_back({t,d}); G[t].push_back({s,d}); added++; } } rep(j1,S){ int s = node_ide(f[1],j1); rep(j2,S){ int t = node_ide(f[2],j2); double d = hypot(1-frac[j1],frac[j2]); G[s].push_back({t,d}); G[t].push_back({s,d}); } } rep(j1,S){ int s = node_ide(f[2],j1); rep(j2,S){ int t = node_ide(f[3],j2); double d = hypot(1-frac[j1],1-frac[j2]); G[s].push_back({t,d}); G[t].push_back({s,d}); } } //cout << added << endl; } int main(){ //init for(int i=2; i<=9; i++){ for(int j=1; j<i; j++){ if(gcd(i,j) > 1) continue; frac.push_back((double)j/i); } } frac.push_back(0); frac.push_back(1); sort(all(frac)); //cout << frac.size() << endl; rep(x,4) rep(y,4) rep(z,4) rep(f,frac.size()){ //printf("%d %d %d\n",node_id(x,y,z,0,f),node_id(x,y,z,1,f),node_id(x,y,z,2,f)); no[node_id(x,y,z,0,f)] = {x+frac[f],(double)y,(double)z}; no[node_id(x,y,z,1,f)] = {(double)x,y+frac[f],(double)z}; no[node_id(x,y,z,2,f)] = {(double)x,(double)y,z+frac[f]}; } //repl int sx,sy,sz,tx,ty,tz; while(cin >> sx >> sy >> sz >> tx >> ty >> tz, sx|sy|sz|tx|ty|tz){ char bl[5][5][5]; memset(bl,'.',sizeof(bl)); iter(z,1,4) iter(y,1,4) iter(x,1,4){ int c = getchar(); while(c == 32 || c == 10) c = getchar(); bl[x][y][z] = c; } //rep(i,5){ // rep(j,5){ // rep(k,5) putchar(bl[i][j][k]); // puts(""); // } // puts("------------"); //} //edge_init rep(i,8000) G[i].clear(); rep(x,4) rep(y,4) rep(z,4){ vector<int> same; same.push_back(node_id(x,y,z,0,0)); same.push_back(node_id(x,y,z,1,0)); same.push_back(node_id(x,y,z,2,0)); if(x>0) same.push_back(node_id(x-1,y,z,0,frac.size()-1)); if(y>0) same.push_back(node_id(x,y-1,z,1,frac.size()-1)); if(z>0) same.push_back(node_id(x,y,z-1,2,frac.size()-1)); rep(i,same.size()) rep(j,same.size()){ if(i==j) continue; G[same[i]].push_back({same[j],0.0}); } //G[node_id(x,y,z,0,0)].push_back({node_id(x,y,z,0,frac.size()-1),1.0}); //G[node_id(x,y,z,1,0)].push_back({node_id(x,y,z,1,frac.size()-1),1.0}); //G[node_id(x,y,z,2,0)].push_back({node_id(x,y,z,2,frac.size()-1),1.0}); } rep(x,4) rep(y,4) rep(z,4){ if(bl[x+1][y][z] != bl[x][y][z]) connect(x,y-1,z-1,0); if(bl[x][y+1][z] != bl[x][y][z]) connect(x-1,y,z-1,1); if(bl[x][y][z+1] != bl[x][y][z]) connect(x-1,y-1,z,2); } //dist init rep(i,8000) d[i] = 1e9; d[node_id(sx,sy,sz,0,0)] = 0; //G[node_id(sx+1,sy+1,sz+1,0,0)].push_back({node_id(sx+1,sy+1,sz+1,1,0),0.0}); priority_queue<pair<double,int>, vector<pair<double,int>>,greater<pair<double,int>>> pq; pq.push({0.0, node_id(sx,sy,sz,0,0)}); int goal = node_id(tx,ty,tz,0,0); int zz = 0; while(!pq.empty()){ zz++; //printf("[%d]",zz); auto p = pq.top(); pq.pop(); int v = p.second; if(d[v] < p.first) continue; if(v == goal){ cout << fixed << setprecision(12) << d[goal] << endl; break; } //printf("((%d))",G[v].size()); rep(i,G[v].size()){ edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; pq.emplace(d[e.to],e.to); } } } //cout << fixed << setprecision(12) << d[goal] << endl; } }