Study

ユークリッドの互除法やエラストテネスの篩, 繰り返し二乗法の計算を勉強した. 線分上の格子点の個数 最大公約数-1がこの問題の解となる. ユークリッドの互除法を元にgcdを実装. #include <iostream> #include <vector> using namespace std; int x_1, x_2, y_1, y_2; int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } int main(int argc, char const *argv[]) { cin >> x_1 >> y_1 >> x_2 >> y_2; int x_diff = abs(x_1 - x_2); int y_diff = abs(y_1 - y_2); cout << gcd(x_diff, y_diff) - 1 << endl; return 0; } ```cpp ### 双六 ユークリッドの互除法を拡張する. `ax+by=1`を満たす整数`x, y`を探すには以下のようなスクリプトを書く. ```cpp int extgcd(int a, int b, int& x, int& y) { int d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } ```cpp ### 素数判定 素数かどうかは`2 ~ √n`までを調べればよい. ```cpp // 素数判定 bool is_prime(int n) { for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // 約数の列挙 vector<int> divisor(int n) { vector<int> res; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { res.push_back(i); if (i != n / i) { res.push_back(n / i); } } } return res; } // 素因数分解 map<int, int> prime_factor(int n) { map<int, int> res; for (int i = 2; i * i <= n; i++) { while (n % i == 0) { ++res[i]; n /= i; } } if (n != 1) { res[n] = 1; } return res; } ```cpp ### 素数の個数 エラストテネスの篩と呼ばれるアルゴリズムを使って数える. 最小の素数の倍数をどんどん省いていく. ```cpp int sieve(int n) { int p = 0; for (int i = 0; i <= n; i++) { is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false; } } } return p; } ```cpp ### 区間内の素数の個数 篩を2つ用いることで, 特定の区間の素数の個数を調べることができる. 区間`[a, b)`を調べる場合は, `[2, √b)`と`[a, b)`の篩を別々に作っておく. ```cpp const int MAX_N = 100000000; const int MAX_SORT_B = 100000000; typedef long long ll; bool is_prime[MAX_N]; bool is_prime_small[MAX_SORT_B]; int a, b; void segment_sieve(ll a, ll b) { for (int i = 0; (ll)i * i < b; i++) { is_prime_small[i] = true; } for (int i = 0; i < b - a; i++) { is_prime[i] = true; } for (int i = 2; (ll)i * i < b; i++) { if (is_prime_small[i]) { for (int j = 2 * i; (ll)j * j < b; j += i) { is_prime_small[j] = false; } for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) { is_prime[j - a] = false; } } } } ```cpp ### Carmichael_Numbers 繰り返し二乗法を用いてべき乗を計算する. 基本的な考え方としては`x^22 = x^16 * x^4 * x^2`のようにx^2^i を順次求めながら計算する. ```cpp ll mod_pow(ll x, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) { res = res * x % mod; } x = x * x % mod; n >>= 1; } return res; } ```cpp ## 感想 最後のビット計算をうまく使う実装は自分でできる気がしない…

グラフを使った解法を勉強した. グラフの表現方法として隣接行列と隣接リストの2つがあって, 最短経路問題を特にはベルマンフォード法, ダイクストラ法, ワーシャル-フロイド法があり, 最小全域木問題を特にはプリム法とクラスカル法がある. この一部を使った演習問題を紹介する. 二部グラフ判定 深さ優先探索を用いて, 隣接している頂点をどんどん塗っていく. グラフは隣接リストを使って表現されている. #include <iostream> #include <vector> using namespace std; const int MAX_V = 10000; vector<int> G[MAX_V]; int V, E; int color[MAX_V]; //頂点を1と-1で塗っていく bool dfs(int v, int c) { color[v] = c; for (int i = 0; i < G[v].size(); i++) { // 隣接している頂点が同じ色ならfalse if (color[G[v][i]] == c) { return false; } // 隣接している頂点がまだ塗られていないなら-cで塗る if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) { return false; } } return true; } int main(int argc, char const *argv[]) { cin >> V >> E; for (int i = 0; i < E; i++) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } for (int i = 0; i < V; i++) { if (color[i] == 0) { if (!dfs(i, 1)) { printf("No\n"); return 1; } } } printf("Yes\n"); return 0; } ```cpp ### Roadblocks 道を辺として, 交差点を頂点として2番目に短い経路を求める問題. 基本的にはダイクストラ法を用いるが, ２番目に短い経路も記憶しておくところがみそ. ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_N = 1000; const int INF = 99999999; struct edge { int to, cost; }; typedef pair<int, int> P; // firstは最短距離, secondは頂点の番号 int N, R, E; vector<edge> G[MAX_N]; // グラフの隣接リスト表現 int dist[MAX_N]; int dist2[MAX_N]; void read() { cin >> N >> R >> E; for (int i = 0; i < E; i++) { int s, t, c; cin >> s >> t >> c; edge x, y; x.to = s; y.to = t; x.cost = c; y.cost = c; G[s].push_back(y); G[t].push_back(x); } } void solve() { priority_queue<P, vector<P>, greater<P> > que; fill(dist, dist + N, INF); fill(dist2, dist2 + N, INF); // 発ノード dist[0] = 0; que.push(P(0, 0)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; int d = p.first; if (dist2[v] < d) { // 2番目の最短路より長い continue; } // vと隣接している頂点を更新 for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; int d2 = d + e.cost; if (dist[e.to] > d2) { // 最短より短い場合 swap(dist[e.to], d2); que.push(P(dist[e.to], e.to)); } if (dist2[e.to] > d2 && dist[e.to] < d2) { // ２番目より短い場合 dist2[e.to] = d2; que.push(P(dist2[e.to], e.to)); } } } printf("%d\n", dist2[N - 1]); } int main(int argc, char const *argv[]) { read(); solve(); return 0; } ```cpp ### Conscription 人を頂点として親密度をコスト付きの辺として, 最小全域木をもとめる問題. この時, コストの高い辺を使いたいのでコストの正負を反転させる. また, この問題は男と女が分けられているが, 特殊な構造を使わなかった. 最小全域木を求めるときはクラスカル法を用いた. クラスカル法はUnionFind木の手法を応用している. ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_N = 50000; const int MAX_E = 50000; const int MAX_R = 50000; // union find // -------------------------------------------- int par[MAX_N]; int depth[MAX_N]; void init_union_find(int n) { for (int i = 0; i < n; i++) { par[i] = i; depth[i] = 0; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (depth[x] < depth[y]) { par[x] = y; } else { par[y] = x; if (depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y) { return find(x) == find(y); } struct edge { int u, v, cost; }; bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; } edge es[MAX_E]; int V, E; int kruskal() { sort(es, es + E, comp); init_union_find(V); int res = 0; for (int i = 0; i < E; i++) { edge e = es[i]; if (!same(e.u, e.v)) { unite(e.u, e.v); res += e.cost; } } return res; } int N, M, R; int x[MAX_R], y[MAX_R], d[MAX_R]; void read() { cin >> N >> M >> R; for (int i = 0; i < R; i++) { cin >> x[i] >> y[i] >> d[i]; } } void solve() { V = N + M; E = R; for (int i = 0; i < E; i++) { es[i] = (edge){x[i], N + y[i], -d[i]}; } printf("%d\n", 10000 * (V) + kruskal()); } int main(int argc, char const* argv[]) { read(); solve(); return 0; } ```cpp ### Layout 牛を頂点と考え, 牛の番号, 仲の良さ, 仲の悪さをコストつきの辺として最短経路を求める問題. 発想としては, 全てを制約条件に落としこんだ結果, 両辺に変数が1つずつしか現れていないことに着目する. 今回は負の辺があるのでベルマンフォード法を用いる. 負閉路が存在するかどうかは, 牛の数だけupdateを行ったあとにも更新があるかどうかで判断する. ```sql #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_ML = 10000; const int MAX_MD = 10000; const int MAX_N = 1000; const int INF = 99999999; int N, ML, MD; int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML]; int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD]; int d[MAX_N]; bool updated; void read() { cin >> N >> ML >> MD; for (int i = 0; i < ML; i++) { cin >> AL[i] >> BL[i] >> DL[i]; } for (int i = 0; i < MD; i++) { cin >> AD[i] >> BD[i] >> DD[i]; } } void update(int& x, int y) { if (x > y) { x = y; updated = true; } } void bellmanford() { for (int k = 0; k <= N; k++) { updated = false; // i+1からiへコスト0 for (int i = 0; i + 1 < N; i++) { if (d[i + 1] < INF) { update(d[i], d[i + 1]); } } // ALからBLへコストDL for (int i = 0; i < ML; i++) { if (d[AL[i] - 1] < INF) { update(d[BL[i] - 1], d[AL[i] - 1] + DL[i]); } } // BDからADへコスト-DD for (int i = 0; i < MD; i++) { if (d[BD[i] - 1] < INF) { update(d[AD[i] - 1], d[BD[i] - 1] - DD[i]); } } } } void solve() { // 負閉路チェック fill(d, d + N, 0); bellmanford(); if (updated) { printf("%d\n", -1); return; } fill(d, d + N, INF); d[0] = 0; bellmanford(); int res = d[N - 1]; if (res == INF) { res = -2; } printf("%d\n", res); } int main(int argc, char const* argv[]) { read(); solve(); return 0; } ```cpp ## 感想 最後の牛の並びを最短経路問題に変換する方法はむずすぎる….

平成最後の日も蟻本の勉強をしてみた. 二分木, 二分探索木, Union-Find木を使った問題を3問解いた. priority_queueを用いる問題 1 expedition ガソリンを補給する回数を最小限に抑える問題. 探索としては, 今あるガソリンで次のガソリンスタンドに辿り着けなかったら, 過去に通過した供給量が一番大きいガソリンスタンドで補給したことにする. ここで, ガソリンスタンドをpriority_queueに入れて, 供給量が大きいもの順に並べていた. #include #include using namespace std; const int MAX_N = 10000; int N, L, P; int A[MAX_N + 1], B[MAX_N + 1]; void read() { cin >> N >> L >> P; for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < N; i++) { cin >> B[i]; } } void solve() { A[N] = L; B[N] = 0; priority_queue que; int ans = 0, pos = 0, tank = P; for (int i = 0; i <= N; i++) { int d = A[i] - pos; // ガソリンを補給 while (tank - d < 0) { if (que.empty()) { puts("-1"); return; } tank += que.top(); que.pop(); ans++; } tank -= d; pos = A[i]; que.push(B[i]); } printf("%d\n", ans); } int main(int argc, char const *argv[]) { read(); solve(); return 0; } ```cpp ### 2 fence repair なるべく長い板を切らせないように目的の板の集合を手に入れる問題. ナイーブに実装すると`O(N^2)`時間になってしまうが, `priority_queue`を用いれば`O(NlogN)`時間になる. ```cpp const int MAX_N = 10000; int n, l[MAX_N]; void solve() { cin >> n; for (int i = 0; i < n; ++i) { cin >> l[i]; } LL ans = 0; priority_queue, greater > que; for (int i = 0; i < n; i++) { que.push(l[i]); } while (que.size() > 1) { int l1, l2; l1 = que.top(); que.pop(); l2 = que.top(); que.pop(); ans += l1 + l2; que.push(l1 + l2); } printf("%lld\n", ans); } int main() { solve(); return 0; } ```cpp #### `priority_queue`の小さい順 ```cpp priority_queue<int, vector<int>, greater<int> > que; ```cpp このように宣言する. ### 3 食物連鎖 複数の情報から矛盾している情報の数を求める. 食物連鎖の関係に矛盾がないことを調べるのにUnion-Find木を用いる. 情報を見ると, 同じ種類に属するか捕食被食の関係にあるという情報だけで種類を特定できない. そこで, 3通りのUnion-Find木を作って1つの木が同時に実現するということにする. 以下がUnion-Find木の実装である. ```cpp // union find // -------------------------------------------- int par[MAX_N]; int depth[MAX_N]; // 初期化 void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; depth[i] = 0; } } // 木の根を返す int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } // 木を併合する void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (depth[x] < depth[y]) { par[x] = y; } else { par[y] = x; if (depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int N, K; int T[MAX_K], X[MAX_K], Y[MAX_K]; void solve() { cin >> N >> K; for (int i = 0; i < K; i++) { cin >> T[i] >> X[i] >> Y[i]; } init(N * 3); int ans = 0; for (int i = 0; i < K; i++) { int t = T[i]; int x = X[i] - 1, y = Y[i] - 1; // 0...N-1 // 正しくない番号 if (x < 0 || x >= N || y < 0 || y >= N) { ans++; continue; } if (t == 1) { // xとyは同じ種類という情報 if (same(x, y + N) || same(x, y + N * 2)) { ans++; } else { unite(x, y); unite(x + N, y + N); unite(x + N * 2, y + N * 2); } } else { if (same(x, y) || same(x, y + N * 2)) { ans++; } else { unite(x, y + N); unite(x + N, y + N * 2); unite(x + N * 2, y); } } } printf("number of wrong info is %d\n", ans); } int main() { solve(); return 0; } ```cpp ## 感想 Union-Find木を知らなかったので, 食物連鎖の実装が綺麗でわかりやすかった. これも標準のライブラリがあればいいのに…

アルゴリズム活用力は, 主にコーディングの試験の際に見られるところであり, webアプリやモバイルアプリを作るのにはあまり必要ないかもしれない. しかし, 将来転職する際にAtcoderである程度の成績を納めていたら強いのではという理由と, 単に楽しいからという理由で蟻本の中級くらいやりたいなと思っている. ってか, 今日のAtcoder全然解けへんくて萎えた… 今回は, 2_3 値を覚えて再利用"動的計画法"を勉強した. 01ナップサック問題 dpを使った動的計画法の初歩が書かれていた. 全探索を行うとO(2^n)かかってしまうところが, メモ化によりO(nW)の計算量で済む. この問題のコツは, 品物と重さを引数として価値の総和を出した時に計算結果を残しておくという発想から. const int MAX_N = 100; int n, W; int w[MAX_N], v[MAX_N]; // dp[i+1][j]: i番目までの品物から重さの総和がj以下となるように選んだ時の, // 価値の総和の最大値 int dp[MAX_N + 1][MAX_N + 1]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } cin >> W; for (int i = 0; i < n; i++) { for (int j = 0; j <= W; j++) { if (j < w[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]); } } } printf("max sum value is %d\n", dp[n][W]); return 0; } ```cpp #### 参考: メモ化テーブルを初期化する方法 ```cpp memset(dp, -1, sizeof(dp)); ```cpp ってな感じで, 0と-1ならば初期化できる. 1はできない. ### 最長共通部分列問題 この問題のコツは, 2つも文字列を引数とした計算結果をメモ化するところである. 最初のうちはDPテーブルをかくと漸化式が浮かびやすいかなと思う. ```cpp const int MAX_N = 1000; int n, m; char s[MAX_N], t[MAX_N]; int dp[MAX_N][MAX_N]; int main() { cin >> n >> m >> s >> t; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i] == t[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } } cout << "max value is " << dp[n][m] << endl; return 0; } ```cpp ### 個数制限なしのナップサック問題 個数制限がなくなったことで, 愚直に計算するとforループがもう一つ増えてしまう. そこで無駄に計算を行なっている箇所を探して, 漸化式を簡単にする. コツとしては, DPテーブルをみて漸化式の動きをみて, 簡単になる箇所がないかを探すのみだと思う. #### 参考: 偶奇を考えた配列の再利用 ```cpp for (int i = 0; i < n; i++) { for (int j = 0; j <= W; j++) { if (j < w[i]) { dp[(i + 1) & 1][j] = dp[i & 1][j]; } else { dp[(i + 1) & 1][j] = max(dp[i & 1][j], dp[(i + 1) & 1][j - w[i]] + v[i]); } } } ```cpp `(i + 1) & 1`の使い方がめちゃうまい気がする… こうして, 2行分のデータを確保できる. ### 01ナップサック問題その2 重さの制約条件が緩くなって, Wが10^9まで飛んでしまった時は, Wでforループを回したくなくなる. そんなときは, メモ化けする対象を入れ替えることでうまくいく. メモ化の値に大きくなるものを入れるのがコツな気がする. ```cpp const int MAX_N = 100; const int MAX_V = 100; const int INF = 99999999; int n, W; int w[MAX_N], v[MAX_N]; // dp[i+1][j]: i番目までの品物から価値の総和がjとなるよう選んだときの, // 重さの総和の最小値 そのような解が存在しない場合は十分大きな値INF int dp[MAX_N + 1][MAX_N * MAX_V + 1]; int main() { // 入力値の読み込み cin >> n; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } cin >> W; // 解く fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= MAX_N * MAX_V; j++) { if (j < v[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]); } } } int res = 0; for (int i = 0; i <= MAX_N * MAX_V; i++) { if (dp[n][i] <= W) { res = i; } } printf("max sum value is %d\n", res); return 0; } ```cpp ### 個数制限付き部分和 bool値をメモ化けするのは無駄がある. そこで大きな値である残りの`a_i`を入れることで漸化式が改善されて計算量を落とすことができる. ```cpp const int MAX_N = 100; const int MAX_K = 100000; int n; int K; int a[MAX_N]; int m[MAX_N]; // dp[i+1][j]: i番目まででjを作る際に余る最大のi番目の個数(作れない場合は-1) int dp[MAX_K]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> m[i]; } cin >> K; memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= K; j++) { if (dp[j] >= 0) { dp[j] = m[i]; } else if (j < a[i] || dp[j - a[i]] < 0) { dp[j] = -1; } else { dp[j] = dp[j - a[i]] - 1; } } } if (dp[K] > 0) { printf("answer is YES\n"); } else { printf("answer is NO\n"); } return 0; } ```cpp ### 最長増加部分列問題 案外奥が深い問題. 部分文字列の候補があがってくるのでそれをメモ化すると`O(n^2)`で解くことができるが, 候補よりも, 最終要素がなにであるかに着目すると`O(n \log n)`で解くことができる. ここらへんは地頭の良さ. #### 参考: lower_bound ```cpp fill(dp, dp + n, INF); for (int i = 0; i < n; i++) { * lower_bound(dp, dp + n, a[i]) = a[i]; } printf("%ld\n", lower_bound(dp, dp + n, INF) - dp); ```cpp ってな感じで, ソートされた列aから二分探索で`a_i <= k`となりような最小の`a_i`のポインタを求めることができる. ### 分割数 最適化だけでなく場合の数にも応用. ```cpp const int MAX_N = 1000; const int MAX_M = 1000; int n, m; int M; int dp[MAX_M + 1][MAX_N + 1]; int main(int argc, char const *argv[]) { cin >> n >> m; cin >> M; dp[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j <= n; j++) { if (j >= i) { dp[i][j] = dp[i - 1][j] + dp[i][j - i]; } else { dp[i][j] = dp[i - 1][j]; } } } printf("%d\n", dp[m][n] % M); return 0; } ```cpp ### 重複組み合わせ これはめちゃめちゃ難しかった. これも, - 何をメモ化するか - 漸化式が作れるように - 計算量が多くならないように - 1つ前の値を意識する - DPテーブルから漸化式を導き出す みたいなところが大事である. ```cpp const int MAX_N = 1000; int n, m; int a[MAX_N + 1]; int M; int dp[MAX_N + 1][MAX_N + 1]; int main(int argc, char const *argv[]) { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } cin >> M; // 1つも選ばない方法は常に1通り for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (j - 1 - a[i] >= 0) { dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - a[i]] + M) % M; } else { dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % M; } } } printf("%d\n", dp[n][m]); return 0; } ```cpp ## 感想 蟻本なかなか重たい. 結構な練習を積まないと身につかない. やっぱり初級編だけ終わらせようかなと思ってきた…