Skip to content

Instantly share code, notes, and snippets.

Avatar
🐹
In sunlight

Akimoto Daichi aximov

🐹
In sunlight
View GitHub Profile
View insertionSort.cc
#include <iostream>
#include <vector>
using namespace std;
void printVector(vector<int> A) {
for (int i = 0; i < A.size() - 1; ++i) {
cout << A[i] << " ";
}
cout << A.back() << endl;
@aximov
aximov / warshall_floyd.cpp
Created Aug 14, 2019
ワーシャルフロイド法。全点対最短距離を求める。O(|V|^3)なので計算量に余裕があるときに使える。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
View warshall_floyd.cpp
const int MAX_V = (int)200;
int d[MAX_V][MAX_V]; // d[u][v]は辺(u,v)のコスト。0-origin. 初期化忘れずに
int V;
void warshall_floyd() {
REP(k, V)
REP(i, V)
REP(j, V) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
@aximov
aximov / dijkstra.cpp
Last active Aug 14, 2019
ダイクストラ法。ある頂点を始点とする各頂点までの最短経路を求める。負のコストがある場合はベルマンフォード法を使う。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
View dijkstra.cpp
const int MAX_V = (int)1e5;
struct edge {
int to, cost;
};
typedef pair<int,int> P; // 最短距離、頂点番号
int V; // 頂点数
vector<edge> G[MAX_V]; // グラフ i -> .to by .cost
int d[MAX_V]; // s からの最短距離。0-origin に注意
@aximov
aximov / procon.cpp
Last active Aug 13, 2019
競プロ用テンプレート
View procon.cpp
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define DEC(i, a, b) for (int i = (a); i > (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
typedef long long ll;
@aximov
aximov / gauss-jordan.cc
Created Jul 6, 2018
Gauss-Jordan 掃き出し法
View gauss-jordan.cc
#include <bits/stdc++.h>
using namespace std;
void printmatrix(double a[10][11], int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n+1; ++j) {
cout << a[i][j] << " ";
}
cout << endl;
}
@aximov
aximov / MC.cc
Created Jul 6, 2018
モンテカルロ積分 (MCMCではない)
View MC.cc
#include <bits/stdc++.h>
using namespace std;
int main() {
int seed;
seed = 1533627;
srand48(seed);
double x, y, z;
int cnt;
int n = 10000;
@aximov
aximov / drand48.cc
Created Jul 6, 2018
同じシードで初期化されたrand48系関数は毎回同じ数列を返す
View drand48.cc
#include <bits/stdc++.h>
using namespace std;
int main() {
int i, seed;
double r;
seed = 1533627;
srand48(seed);
for (i = 0; i < 5; ++i) {
r = drand48();
@aximov
aximov / goudouhou.cc
Created Jul 6, 2018
合同法による乱数の発生
View goudouhou.cc
#include <bits/stdc++.h>
using namespace std;
int irand(int ir) {
int a = 5, c = 1, m = 16;
return (a * ir + c) % m;
}
int main() {
int r = 0;
@aximov
aximov / kumiawase-no-kazu.cc
Last active May 9, 2019
a 個の数から b 個の数を重複ありで選び a^b = c 通りの組をつくるときのための処理。辞書順にはならない。出典: https://beta.atcoder.jp/contests/abc100/submissions/2670489
View kumiawase-no-kazu.cc
#include <iostream>
using namespace std;
int main() {
int a = 2, b = 3, c = 8; //何通りか事前に計算しておく。 e.g. 2^3=8
for (int i = 0; i < c; i++) {
for (int j = 0; j < b; j++) {
if((i/(1 << j))%a == 0) cout << "0";
else cout << "1"; //if分岐はaの値に応じて増える
}
View zundoko.js
(function() {
"use strict";
let arr = [];
for (let i = 0; i < 1e10; ++i) {
if (Math.random() < 0.5) {
arr.push(0);
console.log("ズン");
} else {
arr.push(1);
console.log("ドコ");
You can’t perform that action at this time.