Skip to content

Instantly share code, notes, and snippets.

@gghatano

gghatano/Dockerfile

Last active Mar 6, 2021
Embed
What would you like to do?
atcoderで戦う環境

atcoder環境

ubuntu@docker で atcoder-toolsを使ってc++17環境を作ります。 公式のatcoder-libraryも入ります

[環境構築]

  • docker環境を用意して、dockerとdocker-composeを使えるようにする
  • Dockerfile, docker-compose.ymlを同じフォルダに置く
  • docker-compose up -d する
  • VSCodeをインストールする
  • VSCodeのRemote developで、containerにattachする

[コマンド]

  • agen : atcoder-tools --without-login gen (ex: agen abc002)
  • agenlogin atcoder-tools gen
  • atest: atcoder-tools test
  • asub: atcoder-tools submit

[TODO]

  • gdbでデバッグできるようにする
// いろいろ貼ってあるけど、ACL使った方がいいものもあります
#include <bits/stdc++.h>
using namespace std;
# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){cout << (v[i]) << " ";} cout << endl;
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long ll;
// pq
template<class T>
using MaxHeap = std::priority_queue<T>;
template<class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<typename T>
T gcd(T a, T b) {
if(a < b) swap(a,b);
if(b == 0) return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b){
ll g = gcd(a,b);
return (a/g)*b;
}
// 素数判定 O(√n)
bool is_prime(ll n){
if(n == 1) return false;
for(ll i = 2; i * i <= n; i++){
if(n % i == 0) return false;
}
return true;
}
// 約数列挙 O(√n)
vector<ll> divisor(ll n){
vector<ll> res;
for(ll i = 1; i * i <= n; i++){
if(n % i == 0){
res.push_back(i);
if(i != n / i) res.push_back(n / i);
}
}
return res;
}
template<typename T>
// エラトステネスの篩
// return lp[i] := iの最小素因数(lp[i] == iならば素数)
vector<int> SieveOfEratosthenes(int N = 10000000){
vector<int> lp(N + 1, 0);
vector<int> pr;
for (int i=2; i<=N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back(i);
}
for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
lp[i * pr[j]] = pr[j];
}
return lp;
}
ll mypow(ll x, ll n){
if(n == 0)
return 1;
if(n % 2 == 0)
return mypow(x * x, n / 2);
else
return x * mypow(x, n - 1);
}
// 素因数分解
long long MOD = 1000000000 + 7;
template<typename T>
map<T, ll> prime_factorize(T x){
map<T, ll> res;
while(x%2==0){
x/=2;
res[2]++;
}
for(ll i=3;i*i<=x;i+=2){
while(x%i==0){
x/=i;
res[i]++;
}
}
if(x!=1) res[x]++;
return res;
}
// ランレングス圧縮
vector<pair<char,int>> run_comp(string S){
vector<pair<char,int>> v;
char now = S[0];
int num = 1;
char tmp = S[S.size()-1];
for(int i = 1; i < S.size(); i++){
tmp = S[i];
if(now == tmp){
num++;
} else {
v.push_back(make_pair(now, num));
num = 1;
now = tmp;
}
}
v.push_back(make_pair(tmp, num));
return v;
}
/* 大文字を小文字に変換 */
char tolower(char c) {
return (c + 0x20);
}
/* 小文字を大文字に変換 */
char toupper(char c) {
return (c - 0x20);
}
// dijkstra法
ll INF = 10000000000000000;
vector<vector<int>> v;
vector<ll> dist;
map<pii, ll> len;
bool operator>(pil x, pil y){
return x.second > y.second;
}
void shortest_path(int s){
// sから各点への最短距離計算
dist.assign(N,INF);
priority_queue<pil, vector<pil>, greater<pil>> q;
dist[s] = 0;
map<int,int> check;
q.push(make_pair(s, dist[s]));
check[s] = 1;
while(!q.empty()){
pil now = q.top();
int now_v = now.first;
ll now_dist = now.second;
check[now_v] = 1;
q.pop();
if(dist[now_v] < now_dist) continue;
for(int next_v: v.at(now_v)){
if(dist[next_v] > dist[now_v] + len[make_pair(now_v, next_v)]){
dist[next_v] = dist[now_v] + len[make_pair(now_v, next_v)];
q.push(make_pair(next_v, dist[next_v]));
}
}
}
}
// LCS
string LCS(string s, string t){
int n, m;
n = s.length();
m = t.length();
// dp[i][j] : sのi文字目、tのj文字目のLCSの長さ
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
// dp配列を逆からたどってLCSを作成する
// LCSの長さが更新されたときの文字を追加していく
string ans = "";
int x = n;
int y = m;
while(x > 0 && y > 0){
if(dp[x][y] == dp[x-1][y]){
x--;
}else if(dp[x][y] == dp[x][y-1]){
y--;
}else{
x--;
y--;
ans += s[x];
}
}
reverse(ans.begin(), ans.end());
return ans;
}
// LCA
// ダブリングと根からの距離で頑張る
vector<vector<int>> parent;
map<int,int> dist;
int query(int x, int y){
// xとyのLCAまでの距離を求めて、
// x->LCA->y->xという閉路の長さを返す
if(dist[x] < dist[y]){
return query(y,x);
}
int in = x;
int out = y;
// cerr << "before: x: " << x << " y: " << y << endl;
if(dist[x] != dist[y]){
int up = dist[x] - dist[y];
int log_up = log2(up);
// xのup個上に
for(ll k = log_up; k >= 0; k--){
if((up>>k)&1){
x = parent[k][x];
}
}
// cerr << "after: x: " << x << " y: " << y << endl;
}
int lca;
if(x == y){
lca = x;
} else {
int height = parent.size();
for(int i = height -1; i >= 0; i--){
if(parent[i][x] != parent[i][y]){
x = parent[i][x];
y = parent[i][y];
}
}
// cerr << "LCA: " << parent[0][x] << endl;
lca = parent[0][x];
}
return lca;
}
int main(){
int N;
cin >> N;
vector<vector<int>> v(N);
int root;
for(int i = 0; i < N; i++){
int tmp;
cin >> tmp;
if(tmp == -1){
root = i;
} else {
tmp--;
v.at(i).push_back(tmp);
v.at(tmp).push_back(i);
}
}
// 0からの距離
dist[root] = 0;
queue<int> q;
q.push(root);
int log_N = floor(log2(N));
// cerr << N << " " << log_K << endl;
parent.assign(log_N+1, vector<int>(N));
parent[0][root] = -1;
while(!q.empty()){
int now = q.front();
q.pop();
for(int next: v.at(now)){
if(dist.count(next) == 0){
parent[0][next] = now;
dist[next] = dist[now] + 1;
q.push(next);
}
}
}
// ダブリング
for(int k = 0; k < log_N; k++){
for(int i = 0; i < N; i++){
if(parent[k][i] == -1){
parent[k+1][i] = -1;
} else {
parent[k+1][i] = parent[k][parent[k][i]];
}
}
}
int Q;
cin >> Q;
for(int i= 0; i < Q; i++){
int tmp1,tmp2;
cin >> tmp1 >> tmp2;
tmp1--;
tmp2--;
int lca = query(tmp1,tmp2);
string ans;
if(tmp2 == lca){
ans = "Yes";
} else {
ans = "No";
}
cout << ans << endl;
}
}
// 2次元累積和
int main() {
// 入力: H × W のグリッド
int H, W; cin >> H >> W;
vector<vector<int> > a(H, vector<int>(W));
for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> a[i][j];
// 二次元累積和
vector<vector<int> > s(H+1, vector<int>(W+1, 0));
for (int i = 0; i < H; ++i)
for (int j = 0; j < W; ++j)
s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + a[i][j];
// クエリ [x1, x2) × [y1, y2) の長方形区域の和
int Q; cin >> Q;
for (int q = 0; q < Q; ++q) {
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
cout << s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] << endl;
}
}
// クラスカル法
typedef pair<int,int> pii;
long long MOD = 1000000000 + 7;
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
int main(){
cout << setprecision(10);
int N,M; cin >> N >> M;
vector<pair<int, pair<int,int>>> v(M);
for(int i = 0; i < M; i++){
int x,y,z; cin >> x >> y >> z;
v[i] = make_pair(z, make_pair(x,y));
}
sort(v.begin(), v.end());
UnionFind tree(N);
vector<pair<int,int>> ans;
ll min_val = 0;
for(int i = 0; i < M; i++){
ll weight = (ll)v[i].first;
int s = v[i].second.first;
int t = v[i].second.second;
if(tree.root(s) == tree.root(t)){
continue;
} else {
min_val += weight;
tree.unionSet(s,t);
}
}
cout << min_val << endl;
}
//
version: '3.3'
services:
atcoder:
build: .
volumes:
- type: bind
source: .
target: /atcoder
tty: true
FROM python:3.8
RUN apt-get update \
&& apt-get -y install --no-install-recommends apt-utils dialog 2>&1 \
&& apt-get -y install git iproute2 procps lsb-release gdb\
&& apt-get install -y sudo wget curl vim
RUN cd /tmp \
&& git clone https://github.com/atcoder/ac-library.git
RUN pip3.8 install atcoder-tools
RUN mkdir -p /root/.atcodertools/template
RUN mkdir -p /root/atcoder-workspace
RUN echo 'asub="atcoder-tools submit -f -u"'
RUN echo 'alias atest="g++ --std=c++17 -I /tmp/ac-library main.cpp ; atcoder-tools test"' >> /root/.bashrc
RUN echo 'alias agen="atcoder-tools gen --without-login --template /root/.atcodertools/template/template.cpp"' >> /root/.bashrc
RUN echo 'alias agenlogin="atcoder-tools gen --template /root/.atcodertools/template/template.cpp"' >> /root/.bashrc
RUN echo 'alias asub="atcoder-tools submit -u"' >> /root/.bashrc
RUN curl -s -S https://gist.githubusercontent.com/gghatano/1aab64239be88181d0fc91069c6fe9b4/raw/332945d88d778ce6caa9cf0e15eb6b355fa2ef17/template.cpp >> /root/.atcodertools/template/template.cpp
RUN curl -s -S https://gist.githubusercontent.com/gghatano/1aab64239be88181d0fc91069c6fe9b4/raw/2a786e175ef71502ee704ccec615187b06c45d43/algorithm.cpp >> /root/atcoder-workspace/algorithm.cpp
CMD ["/bin/bash"]
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace atcoder;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
long long MOD = 10000000000 + 7;
long long INF = numeric_limits<ll>::max() / 4;
int main(){
cout << setprecision(10);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment