Skip to content

Instantly share code, notes, and snippets.

View aximov's full-sized avatar
🐹

Nakayama Daichi aximov

🐹
View GitHub Profile
@aximov
aximov / procon.py
Last active January 14, 2024 14:08
# input
a = input() # str
a = int(input()) # int
a = list(input().split()) # list of str
a = list(map(int, input().split())) # list of int
n, m = list(map(int, input().split())) # pair of int
# output
print(a) # str, int
print(a, b) # multiple
#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 August 14, 2019 15:56
ワーシャルフロイド法。全点対最短距離を求める。O(|V|^3)なので計算量に余裕があるときに使える。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
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 August 14, 2019 15:31
ダイクストラ法。ある頂点を始点とする各頂点までの最短経路を求める。負のコストがある場合はベルマンフォード法を使う。マクロ等は https://gist.github.com/aximov/ff8a13ad8aa6c338ec4f88d8970cc1ad
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 August 13, 2019 14:14
競プロ用テンプレート
#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 / kumiawase-no-kazu.cc
Last active May 9, 2019 15:02
a 個の数から b 個の数を重複ありで選び a^b = c 通りの組をつくるときのための処理。辞書順にはならない。出典: https://beta.atcoder.jp/contests/abc100/submissions/2670489
#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の値に応じて増える
}
@aximov
aximov / gauss-jordan.cc
Created July 6, 2018 04:44
Gauss-Jordan 掃き出し法
#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 July 6, 2018 04:19
モンテカルロ積分 (MCMCではない)
#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 July 6, 2018 04:06
同じシードで初期化されたrand48系関数は毎回同じ数列を返す
#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 July 6, 2018 04:01
合同法による乱数の発生
#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;