2022-02-03

【競プロ用】約数列挙、素数判定、素因数分解、素数列挙（エラトステネスのふるい）のC++テンプレート

競プロ

競プロ用に約数、素数関連のよく使う処理をテンプレ化したので、そのメモ ※追加後にいくつかバグが見つかっています。ご利用の際は自己責任でお願いしますm( )m

// 約数列挙
vector<ll> get_divs(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (i * i == n) {
        res.push_back(i);
      } else {
        res.push_back(i);
        res.push_back(n / i);
      }
    }
  }
  return res;
}

// 素数判定
bool is_prime(ll n) {
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

// 素因数分解
map<ll, int> get_primes(ll x) {
  map<ll, int> res;
  for (ll i = 2; i * i <= x; i++) {
    while (x % i == 0) {
      res[i] += 1;
      x /= i;
    }
  }
  // 最後に残った数を追加
  if (x != 1) {
    res[x] += 1;
  }
  return res;
}

// 素数列挙（エラトステネスのふるい）
vector<int> era_primes(ll n) {
  vector<int> res(n + 1, 1);  // 素数なら1, それ以外は0
  res[0] = 0;
  res[1] = 0;

  for (ll i = 2; i * i <= n; i++) {
    ll x = 2 * i;
    // 素数じゃないものに印をつける
    while (x <= n) {
      if (res[x]) {
        res[x] = 0;
      }
      x += i;
    }
  }
  return res;
}

2022-01-23

mod割り算の便利ツール（逆元、べき乗、階乗、二項係数nCr）

競プロ

mod割り算まわりの便利ツールを用意したのでメモこれでmodに怯えずに戦える（かも）

modの演算の詳しい説明はけんちょんさんの以下の記事がとても分かりやすいです

qiita.com

便利ツール

// x!(mod mod)
ll mod_fact(ll x, ll mod) {
  ll ans = 1;
  for (int i = 2; i <= x; i++) {
    ans = (ans % mod) * i;
  }
  return ans % mod;
}

// a^n (mod mod)
ll modpow(ll a, ll n, ll mod) {
  ll ans = 1;
  while (n > 0) {
    if (n & 1) {
      ans = ans * a % mod;
    }
    a = a * a % mod;
    n >>= 1;
  }
  return ans;
}

// a^-1 (mod mod)
ll modinv(ll a, ll mod) { return modpow(a, mod - 2, mod); }

// nCr(mod mod)
ll mod_nCr(ll n, ll r, ll mod) {
  return mod_fact(n, mod) *
         modinv((mod_fact(r, mod) * mod_fact(n - r, mod)) % mod, mod) % mod;
}

2022-01-22

HW盤面のBFSをグラフ構築してから解く

競プロ

グラフの問題を練習してて、よくあるHW盤面の問題をグラフ構築してから実装してみたのでそのメモ

問題

これを解いていく。HW盤面の迷路の最も基本的な形。

atcoder.jp

※以下の2パターンの実装、書いた時期が違うので書き方の癖が違って読みにくいです、、

HW盤面そのまま解く場合

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
using vec = std::vector<T>;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

int main() {
  vec<int> dx = {1, 0, -1, 0};
  vec<int> dy = {0, 1, 0, -1};

  int n, m;
  int sx, sy;
  int gx, gy;
  cin >> n >> m >> sx >> sy >> gx >> gy;
  sx--;
  sy--;
  gx--;
  gy--;

  vector<vector<char>> c(n, vector<char>(m, '.'));
  for (size_t i = 0; i < n; i++) {
    for (size_t j = 0; j < m; j++) {
      cin >> c.at(i).at(j);
    }
  }

  vec<vec<int>> dist(n, vec<int>(m, IINF));  // 最短距離をメモ
  dist.at(sx).at(sy) = 0;                    // スタート地点は距離0
  queue<pair<int, int>> que;                 // bfsのためのキュー

  que.push(make_pair(sx, sy));
  while (que.size()) {
    // 取り出して探索
    auto pos = que.front();
    que.pop();

    // 近傍で探索していない箇所の距離を確定
    for (int i = 0; i < 4; i++) {
      // 次の位置
      int nx = pos.first + dx.at(i);
      int ny = pos.second + dy.at(i);

      // 範囲外の場合
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
        continue;
      }
      // 通行不可の場合
      if (c.at(nx).at(ny) == '#') {
        continue;
      }
      // 未探索なら現在地から+1で距離確定して, キューに追加
      if (dist.at(nx).at(ny) == IINF) {
        dist.at(nx).at(ny) = dist.at(pos.first).at(pos.second) + 1;
        que.push(make_pair(nx, ny));
      }
    }
  }

  cout << dist.at(gx).at(gy) << endl;
}

グラフ構築してから解く場合

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
#define all(obj) (obj).begin(), (obj).end()
using Graph = vector<vector<int>>;

// 変数宣言------------------
int n, m;
Graph g((int)1e5 + 9);
int dist[(int)1e5 + 9];
int h, w;
int sx, sy, gx, gy;

// メイン------------------
int main() {
  cin >> h >> w;
  cin >> sy >> sx >> gy >> gx;
  sy--, sx--, gy--, gx--;

  // 距離の初期化
  for (int i = 0; i < (int)1e5 + 9; i++) {
    dist[i] = IINF;
  }

  // 入力
  char maze[h][w];
  char c;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> c;
      maze[i][j] = c;
    }
  }

  // グラフ構築
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (maze[i][j] == '#') {
        continue;
      }

      // 現在の頂点
      int now = i * w + j;

      // 右の頂点に辺を張る
      if (j + 1 < w && maze[i][j + 1] != '#') {
        g[now].push_back(now + 1);
        g[now + 1].push_back(now);
      }

      // 下の頂点に辺を張る
      if (i + 1 < h && maze[i + 1][j] != '#') {
        g[now].push_back(now + w);
        g[now + w].push_back(now);
      }
    }
  }

  int start = sy * w + sx;
  int goal = gy * w + gx;


  queue<int> que;
  que.push(start);
  dist[start] = 0;

  // bfs
  while (!que.empty()) {
    int now = que.front();
    que.pop();

    for (int i = 0; i < g[now].size(); i++) {
      int next = g[now][i];
      if (dist[next] == IINF) {
        que.push(next);
      }
      dist[next] = min(dist[next], dist[now] + 1);
    }
  }

  cout << dist[goal];

  // 動作確認用
  // for (int i = 0; i < h; i++) {
  //   for (int j = 0; j < w; j++) {
  //     if (dist[i * w + j] == IINF) {
  //       cout << setw(2) << '*' << " ";
  //     } else {
  //       cout << setw(2) << dist[i * w + j] << " ";
  //     }
  //   }
  //   cout << endl;
  // }
}

2022-01-09

競プロ（AtCoder）の目標をレーティングではなく勉強時間にした理由

競プロ雑メモ

2022年の目標のひとつとして、「半年で競プロを700時間勉強する」というのを決めた。なぜ、そんな目標にしたのかを忘れないうちにメモ

なぜ競プロ？

一応仕事はwebエンジニアなので、以下の条件を満たすものを目標にしたいと思っていた。

webエンジニアの仕事に役立つ
即効性のあるものより、将来的に長く役立つ
キャリアアップにつながる可能性がある

このあたりのバランスを考えて競プロで得られるアルゴリズムとデータ構造の知識が該当すると考えた。あと、単純に楽しいので継続できそうだったからというのも大きい。

なぜレーティングではなくて勉強時間？

競プロと言っているが、私の場合はAtCoderのみやっていて現在は茶色（レーティング500くらい）。
そうなると目標を立てる場合は大概、「緑になる！（レーティング800を超える）」「緑安定（レーティング1000くらいで、パフォーマンス加減が1000程度）」みたいになると思う。最初はそれも考えたけど、そうすると自分の特性的に以下が微妙だなと思った

あとどれくらい頑張れば目標達成なのか分からない
目標達成に対して、自分のがんばり以外の変数がある（他の参加者のレベル、自分の習得スピード）

まあ2番目に関しては「緑くらいなら、そんなの気にするまでもないでしょ？」という意見もあると思うが、気になっちゃう怠惰な性分なので、、
あと過去に年始に成果目標立てっぱなしで、結局うやむやにしてしまったことがN回くらいある（Nは十分大きいとする）ので、それをどうにかしたいという気持ちも強かった。

なので、「100%自分で達成がコントロールできる＆途中経過が見えやすい目標」でなおかつ、それを達成すれば自動的に成果も出そうなものにすればいいのでは？と思って、勉強時間を選んだ。

AC数とかにすればいいのでは？

AC数も考えたけど、やめた。
まず、AC数を目標にすると数を増やすために簡単な難易度の問題ばかり解いたり、解説すぐに見てACして復習せずに次の問題に行ってしまったりする可能性があると思った。
あと、物事の習得にはいくつか段階があると考えており、競プロで言うと

解説を見て理解できる（座学）
解説を見なくても実装方針を思いつける（座学＋実践）
実装方針通りに実装できる（実践）

という感じ。したがって、学習ステップの最初ほど座学が多めになるため、仮にAC数を目標にすると、

AC数が伸びなくて目標に対して遅れて焦るorやる気を無くす
AC数を伸ばすために座学を疎かにする

ということが起こるかもと思った。なので、AC数ではなくて勉強時間を目標においた。

700時間の根拠は？

結論から言うと割と適当に決めた。
そもそも「何時間勉強すればレーティングOOに行けるのか？」というのは算出できないと思ったので、「可処分時間をガッツリ使って、行けるところまで行ってみる！」という作戦にした。というわけで、可処分時間を計算すると

平日：780h（= 3h * 5日 * 52週）
休日：520h（= 5h * 2日 * 52週）
合計：1400h

という感じになった。フルタイムジョブ & 通勤片道45分 & 0歳児が家にいるという状況で、自分の中で限界ギリギリの設定かな？と思う。上記より半年分で700時間に決定した。

なんで半年にしたの？

前述したように、「どれくらい勉強すれば成果が出るのか？」というのは算出が非常に難しい。ただ、それは経験があまりないからであって、過去のデータがあれば予想がつく。
そのため、いったん半年がんばってみてデータを蓄積して、後半の目標は振り返り後に再設定しようと思った。
あと、自分が必要とするスキルの中では、競プロは即効性が低いためその他の内容も後半に取り組みたいと思ったから。

どうやって進捗管理してくの？

スプレッドシートに書いていく。スマホからも書けるのでこれが一番しっくり来そう。
実際のスプレッドシートはこんな感じ。

f:id:nakashiii:20220109082208p:plain

工夫したポイントとしては、目標の勉強時間を日割り計算して「今どれくらい遅れているか？」が見えるようにしてある。画像の赤字が今遅れている時間数になる（だいぶ遅れてて焦ってる、、、）

実際に進捗が見えると「やばい！遅れてる！やらなきゃ！！！」みたいな意識がはたらくので今のところは割といい感じに取り組めてるかな？と思う

まとめ

今年こそは年始の目標達成するぞ！！！達成したらうまい肉食べようっと。

2021-12-23

勉強も歯磨きみたいにできればいいのかも

雑メモ

勉強を習慣化するのって大切だと思いつつもついついサボってしまう。ふと「歯磨きってめんどくさいけど、ほとんどサボらないな」って思って、これを勉強とかに応用できないかな？と思ったのでメモ

歯磨きは基本的にめんどくさい。個人的には結構嫌い。本当はしたくない。
でも毎日してるのはなぜか？考えられるのは以下あたり
- 磨かないと臭くなって自分が気持ち悪いから
- 磨かないと臭くなって他人に臭いと思われるから
- 習慣化してて、特に何も考えずにただやっている
- 「やることが普通」の環境に身を置いているから
個人的には「他人に臭いと思われたくない」というのと「継続が当たり前の環境にいる」からが大きいと感じる
口臭が他人から分からない性質のものだったら、多分歯磨きしない
あと、歯磨きの文化がない国（本当にあるのかは分からない）だったら、これまた歯磨きしないと思う
これを抽象化すると、物事を継続的にやるためには
- やらないと他人から嫌われる可能性がある（社会的価値が下がる？）
- 「やることが普通」の環境に身を置く
というのがよさそう。
例えば、勉強の場合だとこんな感じ？
- 勉強しないとどれだけ社会的価値が下がるか定期的に思い出す
- 勉強が習慣化しているコミュニティに所属する（例えば偏差値の高い大学や、専門性が高くて自律した人が多い職場など）

2021-12-23

蟻本 p104 Layout（牛ゲーとベルマンフォード法）

競プロ

問題（ざっくり）

1〜Nまで番号のついた牛がいる
牛は番号順に並んでいる
仲良しの牛a, bは距離d1以内に並べる
中が悪い牛c, dは距離d2以上離して並べる
1番目の牛とN番目の牛の距離の最大値を求めよ。
そのような並び方が存在しない場合は-1, いくらでも離せる場合は-2を出力

原文はこちら 3169 -- Layout

まずはベルマンフォード法を確認する

ベルマンフォード法を使って解くので、まずはこれを理解する。
ベルマンフォード法に関しての解説はこちらの記事が分かりやすかった。 2, 3回ほど以下の記事を行ったり来たりしながら、ゆっくり読むとだいたい理解できた。

AOJの問題が練習にちょうどいいので、まずはこれをベルマンフォード法で解く

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp

※以下のコードはコーナーケースでバグっている可能性がありますのでコピペ利用は自己責任でお願いします

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

int main() {
  int nv, ne, start;  // 頂点数, 辺数, スタート位置
  cin >> nv >> ne >> start;

  vector<Edge> es;  // 辺の集合
  int d[nv];        // 最短距離

  // 最短距離を初期化
  for (int i = 0; i < nv; i++) {
    d[i] = IINF;
  }
  d[start] = 0;

  // 辺を入力
  for (int i = 0; i < ne; i++) {
    int x, y, cost;
    cin >> x >> y >> cost;
    es.push_back(Edge(x, y, cost));
  }

  // ベルマンフォード
  for (int i = 0; i < nv; i++) {
    // 最短経路更新
    bool updated = false;
    for (Edge e : es) {
      if (d[e.from] != IINF && d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        updated = true;
      }
    }
    // 更新がなければ抜ける
    if (!updated) {
      break;
    }
    // 負閉路検出
    if (i == nv - 1) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }

  for (int i = 0; i < nv; i++) {
    if (d[i] == IINF) {
      cout << "INF" << endl;
    } else {
      cout << d[i] << endl;
    }
  }
}

牛ゲーの考え方

ei1333.github.io 以下はこちらのページから引用した解説。これが一番分かりやすかった。（とは言っても、理解するのにけっこう苦労した。）

単一始点最短路は特殊な線形計画問題の双対である(いわゆる牛ゲー)。

頂点 s から頂点 v までの最短経路を f ( v ) とする。グラフに負閉路がなければ f(s) = 0 である。また頂点 u から v へ向かう重み w の辺が存在するとき f ( u ) + w ≥ f ( v ) が成立する。言い換えれば, 頂点 v には最大でも f ( u ) + w のコストで到達可能を意味している。

最短路問題を解くことで各 v について f ( v ) がとりうる最大の値を求めることができる。つまり f ( v ) の最大値を求める問題が最短路問題に対応する。

すべての制約が変数+定数≧変数の形で表される線形計画問題は, 対応するグラフ上での最短路問題を解くことで求めることが出来る。 f ( u ) + w ≥ f ( v ) が成立するとき, 頂点 u から頂点 v へ向かう重み w の辺を張れば良い。

以下の部分が牛ゲーのミソだと思ってる

つまり f(v) の最大値を求める問題が最短路問題に対応する。

実際に問題を解く時は、以下の部分を問題文から読み解くのが大切。

すべての制約が変数+定数≧変数の形で表される線形計画問題は, 対応するグラフ上での最短路問題を解くことで求めることが出来る。

牛ゲーの実装

というわけで、以下が実装。

制約を定式化する
定式化した制約を辺として受け取る
ベルマンフォード法適用

という感じで解ける

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

// ベルマンフォード法
// 負閉路ありならfalse, それ以外はtrueを返す
bool bf(int n, int start, vector<Edge> es, int d[]) {
  // 最短距離を初期化
  for (int i = 0; i < n; i++) {
    d[i] = IINF;
  }
  d[start] = 0;

  // ベルマンフォード
  for (int i = 0; i < n; i++) {
  // 最短経路算出
    bool updated = false;
    for (auto e : es) {
      if (d[e.from] != IINF && d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        updated = true;
      }
    }
    // 更新されていないなら終了
    if (!updated) {
      break;
    }
    // 負閉路検出
    if (i == n - 1) {
      return false;
    }
  }

  return true;
}

int main() {
  int n, ml, md;
  cin >> n >> ml >> md;

  vector<Edge> es;  // 辺の集合
  int d[n];         // 最短距離

  // d[i+1] + 0 >= d[i] の制約を満たす辺を追加
  for (int i = 0; i < n - 1; i++) {
    es.push_back(Edge(i + 1, i, 0));
  }

  // d[al] + dl >= d[bl] の制約を満たす辺を追加
  for (int i = 0; i < ml; i++) {
    int al, bl, dl;
    cin >> al >> bl >> dl;
    al--, bl--;
    es.push_back(Edge(al, bl, dl));
  }

  // d[bd] + (-dd) >= d[ad] の制約を満たす辺を追加
  for (int i = 0; i < md; i++) {
    int ad, bd, dd;
    cin >> ad >> bd >> dd;
    ad--, bd--;
    es.push_back(Edge(bd, ad, -dd));
  }

  if (bf(n, 0, es, d)) {
    if (d[n - 1] == IINF) {
      cout << -2 << endl;
    } else {
      cout << d[n - 1] << endl;
    }
  } else {
    cout << -1 << endl;
  }
}

2021-12-21

蟻本 p103 Conscription（最小全域木プリム法とクラスカル法）

競プロ

蟻本でプリム法とクラスカル法を勉強したのでメモ。クラスカル法の方がかなりスッキリ書ける。

（注）2ケースくらいでしかテストしていないので、バグらせていたらごめんなさい

問題（ざっくり）

N人の女とM人の男を全員徴兵する際の最小コストを求めよ。

徴兵コストは一人あたり10000
女と男には親密度が設定されており、徴兵する際、徴兵済みの人と親密度がある場合はコストをその分差し引く
同じ男女が複数通りの親密度を持つ場合もある

原文はこちら 3723 -- Conscription

解法

連結成分ごとに最小重み森を計算して、最大の徴兵コストから差し引く。

最大重み森とは、最小全域木の逆で、無向グラフからコストが最大になるように頂点を選んだ全域木を指す。要は最小全域木の逆の意味。
今回は差し引くコストを最大にしたいので、最大重み森を求める。

また、頂点N+Mは連結でない頂点もあるので、プリム法を使う場合は連結成分ごとに計算しなければいけないことに注意。Union Findを使って連結判定しながら最大重み森を求める。

プリム法

プリム法でやると閉路判定のためにUnion Findを使う必要がある。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
struct Edge {
  int to, cost;
  Edge(int t, int c) : to(t), cost(c) {}
};
using Graph = vector<vector<Edge>>;

// プリム法
// prim(無向グラフ, 利用したかどうか, 木のサイズ, 開始位置)
int prim(Graph &g, int used[], int tree_size, int start) {
  // コスト順に取り出したいので, Edgeではなくpairで優先キューに入れる
  priority_queue<pint, vector<pint>, greater<pint>> que;

  que.push(make_pair(0, start));  // 任意の点からスタートする（距離, 頂点）
  int ans = 0;                    // 最小全域木の合計コスト

  while (tree_size > 0) {
    pint cur = que.top();  // 現在の木に隣接する頂点で, 一番コストが小さいもの
    que.pop();
    int v = cur.second;
    int cost = cur.first;

    // 使用済みならスキップ
    if (used[v]) {
      continue;
    }

    // コストをプラスして, 使用済みにする
    ans += cost;
    used[v] = 1;  // 使用済みにする
    tree_size--;  // 使用済み頂点数を更新

    // 未探索の頂点をすべて優先キューに入れる
    for (auto next : g[v]) {
      if (!used[next.to]) {
        que.push(make_pair(next.cost, next.to));
      }
    }
  }

  return ans;
}

// union find
class UnionFind {
 public:
  // 親の番号を格納する。親だった場合は-1
  vector<int> Parent;
  UnionFind(int N) { Parent = vector<int>(N, -1); }

  // Aがどのグループに属しているか調べる
  int root(int A) {
    if (Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }

  // 自分のいるグループの頂点数を調べる
  int size(int A) {
    return -Parent[root(A)];  //親をとってきたい
  }

  // AとBをくっ付ける
  bool unite(int A, int B) {
    // AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
    A = root(A);
    B = root(B);
    if (A == B) {
      //すでにくっついてるからくっ付けない
      return false;
    }
    // 大きい方(A)に小さいほう(B)をくっ付ける
    // 大小が逆だったらひっくり返す
    if (size(A) < size(B)) {
      swap(A, B);
    }
    // Aのサイズを更新する
    Parent[A] += Parent[B];
    // Bの親をAに変更する
    Parent[B] = A;
    return true;
  }
};

int main() {
  int n, m, r;
  cin >> n >> m >> r;
  int k = n + m;

  Graph g(k);
  UnionFind uni(k);

  // 入力
  for (int i = 0; i < r; i++) {
    int x, y, d;
    cin >> x >> y >> d;
    g[x].push_back(Edge(y + n, -d));  // -d:最大重み森のため、コスト符号を反転
    g[y + n].push_back(Edge(x, -d));
    uni.unite(x, y + n);
  }

  int reduced_cost = 0;  //関係を使って削減できるコスト

  // 連結成分ごとにプリム法でコストを求める
  int used[k]{};
  for (int i = 0; i < k; i++) {
    if (!used[i]) {
      int tree_size = uni.size(i);
      reduced_cost += prim(g, used, tree_size, i);
    }
  }

  cout << (10000 * k) + reduced_cost << endl;
}

クラスカル法

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};
struct EdgeLess {  // 大小比較用の関数オブジェクトを定義することもできる
  bool operator()(const Edge& a, const Edge& b) const noexcept {
    // キーとして比較したい要素を列挙する
    return std::tie(a.cost) < std::tie(b.cost);
  }
};
using Graph = vector<vector<Edge>>;

class UnionFind {
 public:
  // 親の番号を格納する。親だった場合は-1
  vector<int> Parent;
  UnionFind(int N) { Parent = vector<int>(N, -1); }

  // Aがどのグループに属しているか調べる
  int root(int A) {
    if (Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }

  // 自分のいるグループの頂点数を調べる
  int size(int A) {
    return -Parent[root(A)];  //親をとってきたい
  }

  // AとBをくっ付ける
  bool unite(int A, int B) {
    // AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
    A = root(A);
    B = root(B);
    if (A == B) {
      //すでにくっついてるからくっ付けない
      return false;
    }
    // 大きい方(A)に小さいほう(B)をくっ付ける
    // 大小が逆だったらひっくり返す
    if (size(A) < size(B)) {
      swap(A, B);
    }
    // Aのサイズを更新する
    Parent[A] += Parent[B];
    // Bの親をAに変更する
    Parent[B] = A;
    return true;
  }
};

// クラスカル法
// （辺の集合, 頂点の数）
int krs(vector<Edge>& es, int n) {
  UnionFind uni(n);
  int ans = 0;

  sort(es.begin(), es.end(), EdgeLess{});  // コストが小さい順にソート

  for (auto e : es) {
    // 閉路になる場合はスキップ
    if (uni.root(e.from) == uni.root(e.to)) {
      continue;
    }
    ans += e.cost;
    uni.unite(e.from, e.to);
  }

  return ans;
}

int main() {
  int n, m, r;
  cin >> n >> m >> r;
  int k = n + m;

  vector<Edge> es(r, Edge(0, 0, 0));

  // 入力
  for (int i = 0; i < r; i++) {
    int x, y, d;
    cin >> x >> y >> d;
    es[i] = Edge(x, y + n, -d);
  }

  cout << (10000 * k) + krs(es, k) << endl;
}

nakashiiiの自由帳

自由に書きます

【競プロ用】約数列挙、素数判定、素因数分解、素数列挙（エラトステネスのふるい）のC++テンプレート

mod割り算の便利ツール（逆元、べき乗、階乗、二項係数nCr）

便利ツール

HW盤面のBFSをグラフ構築してから解く

問題

HW盤面そのまま解く場合

グラフ構築してから解く場合

競プロ（AtCoder）の目標をレーティングではなく勉強時間にした理由

なぜ競プロ？

なぜレーティングではなくて勉強時間？

AC数とかにすればいいのでは？

700時間の根拠は？

なんで半年にしたの？

どうやって進捗管理してくの？

まとめ

勉強も歯磨きみたいにできればいいのかも

蟻本 p104 Layout（牛ゲーとベルマンフォード法）

問題（ざっくり）

まずはベルマンフォード法を確認する

牛ゲーの考え方

牛ゲーの実装

蟻本 p103 Conscription（最小全域木プリム法とクラスカル法）

問題（ざっくり）

解法

プリム法

クラスカル法