ABC177のD問題に挑戦してみた
初めに
今回はABC177のD問題に挑戦してみました。
この問題は、Union-findというデータ構造を使用すると簡単に解ける問題で、
今まで書いた事が無いアルゴリズムだったので、今回はABC177のD問題について書きます。
https://atcoder.jp/contests/abc177
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
https://atcoder.jp/contests/abc177/tasks/abc177_d
人1から人NまでのN人がおり、それぞれの人の友人関係情報が入力されます。
N人をいくつかのグループに分ける際に、すべての人について友人が同じグループにいない状態
にするには最小でいくつのグループに分ければ良いかを求める問題です。
回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; struct UnionFind { vector<int> d; UnionFind(int N){ //初期化 d = vector<int>(N,-1); } int find(int x){ //根に到達したら根の値を返す if(d[x] < 0) return x; //同じ根に属する要素の return d[x] = find(d[x]); } bool unite(int x,int y){ //xとyに結合する根の情報を格納 x = find(x);y = find(y); //根が同じであれば、結合処理は不要 if(x == y) return false; //xの方がyより根が大きければxとyの値を入替 if(d[x] > d[y]) swap(x,y); //連結する根(y)のサイズを新たな根(x)に加算 d[x]+=d[y]; //yの新しい根としてxを設定 d[y]=x; return true; } //同じ根に属しているか判定 bool same(int x,int y){ return find(x) == find(y); } //連結成分のサイズ返す int size(int x){ return -d[find(x)]; } }; int main(){ ll N,M; ll A,B; cin >> N >> M; UnionFind UF(N); for(ll i = 0;i < M;++i){ cin >> A >> B; --A;--B; UF.unite(A,B); } int ans = -1; for(int i = 0;i < N;++i){ ans = max(ans,UF.size(i)); } cout << ans << endl; return 0; }
この問題は、Union-Findというデータ構造を利用すると簡単に解くことが出来ますので、
まずはUnion-Findについて記載した後に問題を解いていこうと思います。
Union-Findは下記のような共通部分を持たない集合を保持することが出来るデータ構造です。
Union-Findは、主に以下の操作を行う事で素集合の保持と
ある要素がどの集合に属するか判定を行う事が出来ます。
Unite:同様な根を持つ2つの集合を結合する操作
Find:要素が属している集合の根を見つける操作
※詳細については下記ブログに情報がまとめられていたので、こちらを参照下さい。
pyteyon.hatenablog.com
Union-Find Tree を理解する!素集合系を扱うデータ構造 | アルゴリズムロジック
Uniteは以下のような操作になります。根となっている配列には集合のサイズを格納しています。
(正負が逆転しているので注意。プログラムと一緒に見てみて下さい。)
Findは以下のような操作になります。
(プログラム上ではreturnする時に集合に属する要素の結合先を根の値に縮約しています。)
※配列の添え字は0基算で記載しています。
上記のようなイメージでUniteとFindの操作は行われます。
Union-Findがわかると問題を解くのは簡単です。N人の人をそれぞれ友達がいないグループに分ける場合、
グループの数を最小とするには、一番大きい集合の要素数と同じ数のグループが必要となります。
(一番大きい集合の要素数より小さいグループ数とすると少なくとも1つは友達関係持つ人がグループになります。)
そのため、プログラム中で求めている各集合のサイズが最大のものを求めて出力することで答えを求める事が出来ます。
最後に
久しぶりにブログ書きましたがやはりまとめると理解が深まりますね。
ただ、Union-Findは他にも書き方があったりとまだ完全に理解して使いこなせる訳ではないので
精進しようと思います。(Union-Findはより理解が深まったら書き直すかもです。)
あと少しで目標の茶色になりそうなので頑張ります!(あと60あげればいける!)
Appendix:Union by rank
Union-Findはいくつかの書き方があるようで、上述したものはUnion by Sizeという書き方です。
もう一つUnion by rankという書き方があるようで以下にその書き方の備忘を記載しています。
※そのうち加筆します。
vector<int> d; vector<int> rank; UnionFind(int N){ //初期化 for(int i = 0;i < N;++i) d[x] = x; rank = vector<int>(N,0); } int find(int x) { if (x == d[x]) return x; return d[x] = find(d[x]); } void unite(int x, int y) { x = find(x); y = find(y); //xのrankの方が大きい場合はyの接続先をxに付け替える if (rank[x] > rank[y]) { d[y] = x; //上記条件を満たさない場合はxの接続先をyに付け替える } else { d[x] = y; // rankが同じ場合はrankの値を1つ増やす if (rank[x] == rank[y]) { rank[y]++; } } }
Union by rankの書き方で結合する場合は以下のようになります。
xとyが同様であった場合のみ、rankの値が1つ増える更新が行われます。 ※x,yの大小関係が成立している場合はrankの更新は発生しない。
ABC169のD問題に挑戦してみた
初めに
今回はABC169のD問題に挑戦してみました。
この問題は、方針は浮かんだのですが実装が出来ませんでしたが、
今まで書いた事が無い手法だったので、今回はABC169のD問題について書きます。
https://atcoder.jp/contests/abc169
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
D - Div Game
ある整数Nが与えられ、下記の操作が最大で何回行えるかを求める問題です。
最終的な回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll N; cin >> N; vector<Pair> fs; for(ll i = 2;i*i <= N;++i ){ ll cnt = 0; //素因数分解 //割り切れなくなるまで割り算を行う while(N%i==0){ //割り算を行える回数をカウント N/=i; ++cnt; } //素因数の数をそれぞれ個数を格納 fs.emplace_back(i,cnt); } // Nの値が1ではなかった場合はその数は素因数となるため格納 if(N!=1) fs.emplace_back(N,1); ll ans = 0; for(Pair p : fs){ ll cnt = p.second; ll x = 1; // while(x <= cnt){ cnt -= x; ++ans; ++x; } } cout << ans << endl; return 0; }
まずは、試しに例題として記載されているN=24のパターンで素因数分解してみると、
素因数は2が3つ、3が1つあることがわかります。
今回の問題では最大何回の操作が行えるかを求める問題であり、以下のように
小さい素因数から指数の小さい順に操作を行う事で操作回数が最大になります。
素因数分解については、2からまでの整数で計算を行う事で求められます。
プログラム上では という条件でループを行っています。(下記参照)
2からまでで良い理由としては、下記のようにNをある数で割りきれた場合、
計算結果から得られた商でも割り切る事が可能であり、以降の値での割り算は
すでに2からの範囲で計算したものと同様であるためです。
※ちゃんとした証明はけんちょんさんのブログ↓を見た方が良いです。 https://qiita.com/drken/items/a14e9af0ca2d857dad23
素因数分解が完了したら、あとは求めた素因数の個数を1,2,3....という形で引いていき、
その回数を集計することで最大回数を求める事が出来ます。
最後に
今回の素数判定の計算量削減のようなテクニックは演習を重ねてどんどん身に着けて
行きたいですね。今までもテクニックとして見たことはあったんですが、
あまり理解していなかったのでブログを書くことで理解が深まって良かったです。
ABC171のD問題に挑戦してみた
初めに
今回はABC171のD問題に挑戦してみました。
この問題は、解説を見ないで回答することができましたが、
解いていく中で気付きがあったのでそれを中心に記載して行きます。
https://atcoder.jp/contests/abc171
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
D - Replacing
N個の整数からなら数列が与えられます。その数列に対して1 → 2といった
数字の置き換え操作をQ回行い、1~Q回目の入れ替えのタイミングでの
数列の和をそれぞれ出力する問題です。
最初の回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll N,Q; cin >> N; vector<ll> A(N); for(ll i = 0;i < N;++i) cin >> A[i]; cin >> Q; ll B,C; vector<ll> S(Q,0); for(ll i = 0;i < Q;++i){ cin >> B >> C; for(ll j = 0;j < N;++j){ if(A[j] == B){ A[j] = C; } S[i] += A[j]; } } for(ll i = 0;i < Q;++i){ cout << S[i] << endl; } return 0; }
最終的な回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll N,Q; ll sum = 0; cin >> N; ll A; vector<ll> cnt(100001,0); for(ll i = 0;i < N;++i){ cin >> A; // 初期入力された数列の和を計算し格納 sum += A; // バケットに入力された整数の個数を格納 ++cnt[A]; } cin >> Q; ll B,C; vector<ll> S(Q,0); for(ll i = 0;i < Q;++i){ cin >> B >> C; // 入れ替え操作が発生した際の差分(C-B)と入れ替わった数字の個数の積をsumに加算 sum += (C - B)*cnt[B]; // 入れ替え操作により入れ替えもとの数字の個数を入れ替え先の数字の個数に加算 cnt[C] += cnt[B]; // 入れ替え元の数字の個数を0に設定 cnt[B] = 0; S[i] = sum; } for(ll i = 0;i < Q;++i) cout << S[i] << endl; return 0; }
まずこの問題は愚直に入れ替え操作を行うととなり、
N,Qの入力の制約が105のため、TLEになります。(最初の回答)
愚直に処理を行ってもTLEが発生することは分かったので、予め初期入力の総和を求め、
その総和に入れ替え時に発生した差分を加算するというアプローチで考えてみます。
差分の計算を行うためには、「B(入れ替え前の数字)」と「C(入れ替え後の数字)」を減算後に、
「入れ替え前の数字の数」と掛け算をすることで差分を求める事ができます。
ここで、各数字の個数を求めるためにバケット法という手法を利用します。
バケット法とは下記のように配列で「cnt[値] = 値の個数」で値の個数を集計する方法で、
数列の並びは重要では無く、個数が重要な場合に利用できる方法です。
バケット法を用いて配列cntに各数字の個数が求められているので、
後は以下の操作を繰り返す事で答えを求める事が出来ます。
①総和と入れ替え時の差分((C-B)*cnt[i])の和を求める
②「入れ替え前の数字」の個数を「入れ替え後の数字」の個数に加算
③「入れ替え前の数字」の個数を0に設定
最後に
今回書いたバケット法は今まで名前はしらなかったのですが
使用したことがある手法でした。やはり名前が付いていた方が
頭の中からパッと引き出せるので良いですね。
こんな感じでACしたけど、気付きがあった問題も書いていきます!
ABC171のE問題に挑戦してみた
初めに
レート400(茶色レート)を超えるためにになるためにAtCoder Problemsを
利用して茶色レート帯の問題を解いていまして、
今までは参加した時にしかブログを書いていなかったのですが、
書いてもまとめた方がお勉強になるので参加していない時も
たまに書こうかと思います。(今週はABCありませんし)
https://kenkoooo.com/atcoder/#/table/
制限時間を決めて解いているんですが、時間内に解き終わらなかったので、
主に解説を見て「なるほどなぁ」となったところについて書いて行きます。
https://atcoder.jp/contests/abc171
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
E - Red Scarf
N匹の猫がおり、それぞれの猫は整数が記載された赤いスカーフを付けています。
までの入力が与えられ、はi番目の猫のスカーフに記載されている整数を除いた
猫のスカーフに記載された整数をXORした結果となります。
この情報を元にそれぞれの猫のスカーフに記載されている整数を求めます。
解説を見てからの回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll N; ll sum = 0; cin >> N; vector<ll> a(N); // 入力とA1~ANの値のXORした結果を格納 for(ll i = 0;i < N;++i){ cin >> a[i]; sum ^= a[i]; } // 元の値を求る for(ll i = 0;i < N;++i) a[i] ^= sum; // 結果を出力 for(ll i = 0;i < N;++i) cout << a[i] << endl; return 0; }
※下記に表示しているイメージは0起算で書いてます。
まずは、テストケースのパターンを元に考えてみましょう。
をi番目の猫のスカーフに記載されている整数とすると、
を以下のような形で表す事が出来ます。
XORの性質について考えて見ると以下のように同じ整数を偶数回XORをすると0となり
奇数回XORをすると1つ分の整数の値となります。
この性質を利用して、の値を下記例のようにXORすると
XORする前の値()をXORした値となります。
上記のことが分かったので、の値をXORしたものと、
個別にをXORするとの値を元の数が求められます。
これをのすべてに行うと元の数をすべて求める事が出来ます。
最後に
XOR自体は知っていたんですが、この発想は浮かびませんでしたね。
過去問やると今まで思いつかなかった発想に出くわすのでタメになりますね
継続して過去問を解いていき本番で活かせるようにしていきます!
ABC177に参加してみた
初めに
ABC177はAB完でした。C問題はほぼほぼ解けていたんですが
問題文を読み間違えている事に最後まで気づかず回答できませんでしたorz
はい、ということで今回はC問題について書いていきます。。。
https://atcoder.jp/contests/abc177
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Sum of product of pairs
N個の整数が与えられるのでを満たす
すべてのについてのの和をで割った数を求める問題です。
解説を見てからの回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll N; ll ans = 0; ll mod = 1e9 + 7; cin >> N; vector<ll> A(N); vector<ll> S(N + 1); for (ll i = 0; i < N;++i) cin >> A[i]; S[0] = 0; for (ll i = 0; i <N;++i){ // 累積和を求める S[i+1] = (S[i] + A[i]); } for (ll i = 0; i < N;++i){ // 区間和を求める ll sum = (S[N] - S[i + 1]) % mod; // AiAjの計算を行い変数ansに加算し、mod計算を行う ans += sum*A[i]; ans %= mod; } cout << ans << endl; return 0; }
この問題は愚直に2重ループで計算を行っていくとNの制約がのため、
制限時間内に計算を行う事が出来ません。
まずは何か法則性が無いか考えてみましょう。の場合を考えて見ます。
が,,の場合の計算は以下のようにまとめる事が可能です。
※0基算で書いてます。
上記よりに以降の値を足した数を掛け算し、それぞれのでの計算結果を
足し合わせることでも答えが得られそうです。
2重ループで足し算をした後に掛け算を行うと制限時間内に間に合わないので
下記のように累積和をまずは求めます。累積和を求めておけばある区間の和も
で求める事が出来ます。
あとは、に区間和を掛けていきその和を求めていきます。
区間和およびと区間和の積を求める際はmod計算も忘れずに行いましょう。
(オーバーフローの可能性があるため。mod計算は計算途中に行っても計算結果は変わりません。)
最後に計算結果を出力すれば問題を解くことが出来ます。
最後に
うーん今回はもったいなかったですね。ほとんど解けていたようなものだったというのと
割と回答内容に自身があった分、WAが発生した時に余計混乱してしまいました。。。
落ち着いて取り組みましょ!
※累積和の計算段階からmod計算をしていたので、C問題はWAになってしまいました。。。
ABC176に参加してみた
初めに
ABC176はABC完でした。D問題までは到達したのですが、
目をつむって考えていて、気づいたら朝になっていましたorz(寝落ち)
まぁ起きていても解けた問題では無かったのですが(笑)
今回はD問題について書いてきますが、自分の理解を深める事に重点を置いて書いて行きます。
(いつもそうですが今回は特に)
https://atcoder.jp/contests/abc176
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Step
この問題は迷路のスタート地点からゴール地点に到達するまでに
必要な最小のワープ回数を回答するという問題です。
解説を見てからの回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; // 4近傍の座標への移動をするために使用 const ll di[] = {-1, 0, 1, 0}; const ll dj[] = {0, -1, 0, 1}; typedef pair<ll,ll> Pair; int main(){ ll H, W; ll Ch, Cw; ll Dh, Dw; cin >> H >> W; cin >> Ch >> Cw; //扱いやすいように0起算の形にしています。 Ch--;Cw--; cin >> Dh >> Dw; //扱いやすいように0起算の形にしています。 Dh--;Dw--; vector<string> S(H); for (ll i = 0; i < H;++i) cin >> S[i]; // 距離を格納する配列 vector<vector<ll>> dist(H, vector<ll>(W, INF)); // ある地点から行けるマスを格納 deque<Pair> q; // 初期値の距離はコスト0で初期化 dist[Ch][Cw] = 0; // 初期値をキューに格納 q.emplace_back(Ch,Cw); // キューが空になるまでループを回す。 while(!q.empty()){ // i,jにキューの先頭の座標を格納 ll i = q.front().first; ll j = q.front().second; // 移動元の座標のコストを格納 ll d = dist[i][j]; // キューから先頭の座標を取り除きます。 q.pop_front(); // コスト0で移動できる場所(上下左右) for (ll ii = 0; ii < 4;++ii){ // 上下左右の四近傍の座標を格納 ll ni = i + di[ii]; ll nj = j + dj[ii]; // 迷路の枠外の座標だった場合はスキップ if(nj < 0 || ni < 0 || ni >= H || nj >= W) continue; // 壁のある座標だったらスキップ if (S[ni][nj] == '#') continue; // 座標の移動コストがd以下だったらスキップ if (dist[ni][nj] <= d) continue; // 座標のコストをdに更新 dist[ni][nj] = d; // キューの先頭に座標を格納 q.emplace_front(ni,nj); } // コスト1で移動できる場所(ワープ魔法を使用した場合の5×5マス) for (ll ei = -2; ei <= 2;++ei) { for (ll ej = -2; ej <= 2;++ej) { // 現在いる座標の5×5マス座標を格納 ll ni = i + ei; ll nj = j + ej; // 迷路の枠外の座標だった場合はスキップ if(nj < 0 || ni < 0 || ni >= H || nj >= W) continue; // 壁のある座標だったらスキップ if (S[ni][nj] == '#') continue; // 座標の移動コストがd+1以下だったらスキップ if (dist[ni][nj] <= d+1) continue; // 座標のコストをd+1に更新 dist[ni][nj] = d+1; // キューの末尾に座標を格納 q.emplace_back(ni,nj); } } } // 初期値から更新されていない場合はゴールに到達出来ないため-1を出力 if(dist[Dh][Dw] == INF) cout << "-1" << endl; // 初期値から更新されている場合はゴール地点の座標のコストを出力 else cout << dist[Dh][Dw] << endl; return 0; }
この問題では01-BFSというアルゴリズムと利用することで、解くことが出来ます。
01-BFSは今回のように2通りの移動方法があるような場合に利用することが可能です。
BFSはキュー(queue)というデータ構造で実装を行うことができますが、
01-BFSはこれを拡張したものでデック(deque)というデータ構造で実装出来ます。
デック(deque)はキュー(queue)とは異なり両端からデータの出し入れを行う事が出来ます。
これを利用してコスト0で移動(魔法無し)できる座標を先頭に、
コスト1で移動(魔法有り)できる座標を末尾に追加することで
コスト0の座標が先頭に、コスト1の座標が末尾に固めっている状態とすることが出来ます。
このデータ構造を使用することで、コスト0で移動した座標を優先して探索が可能となります。
そして、コスト0の移動については現在いる座標を中心とした4近傍(上下左右)の座標、
コスト1の移動については現在いる座標を中心とした5×5マスの座標について距離を更新します。
(配列di,djのような形で定義しておくと、ループを回すことで4近傍の探索が行えます。下記参照)
距離の更新が完了したら、ゴールの初期値が更新されているか確認を行い、
更新がされていた場合はその距離を出力し、更新されていない場合は-1を出力することで
問題を解くことが出来ます。
最後に
知らないアルゴリズムが登場したらあきらめて次回出てきた場合には対応できるように
まとめておくしかないですね。まぁ後は寝落ちしないように頑張ります(笑)
ABC175に参加してみた
初めに
ABC175はAB完でした。C問題はアルゴリズム云々って問題では無く、
問題を考察してシミュレーションするって形の問題だったんですが、回答出来ず、、、
アルゴリズムの学習をするのもそうですが、考察力も鍛えなきゃですね、、、
というわけでC問題について記載していきます。
https://atcoder.jp/contests/abc175
※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。
C - Walking Takahashi
ある座標XからK回移動した座標の絶対値が最小になるように移動する問題です。
移動可能な距離はDで正の方向と負の方向に移動する事が可能です。
(入力Kの最大値は1015なので愚直に計算していくと間に合いません。。。)
解説を見てからの回答
#include<bits/stdc++.h> using namespace std; using ll = long long; const long long INF = 1LL<<60; typedef pair<ll,ll> Pair; int main(){ ll X,K,D; cin >> X >> K >> D; // 絶対値を設定 X = abs(X); // 原点間の行き来が発生しないパターン if(X/D >= K) cout << X - D*K << endl; // 原点間の行き来が発生するパターン else{ K = K - X/D; X = X - D*(X/D); if(K % 2 == 1) X = X - D; cout << abs(X) << endl; } return 0; }
まずは、計算を楽にするためにXに入力された値の絶対値を格納します。
負の値が入力された場合は正の値に変更されますが、移動する際の操作が反転するだけなので
Xの絶対値で計算を行っても結果は変わりません。
最小値を求めるためには、基本的にXから値を引いて行くことで最小値に値が近づいて行きます。
そして、操作を進めて行く原点を超えないパターンと、下記のように原点(0)を境に
行き来するようなパターンの2パターンが発生することが考えられます。
そのため、原点を超えないパターンと原点を行き来するパターンで場合分けを行います。
場合分けはX/Dが移動回数Kを超えているかどうかで行います。
X/Dは「原点を超えずにXからDを引く事が出来る回数」を意味しており、
この値がKより大きかった場合は、K回引く操作を行っても原点を超えることは無いので
XからK回Dを引いた値(X - D*K)を出力します。
X/Dの値がKより小さかった場合は、原点を境に行き来するパターンとなります。
まずは、KからX/Dを引き「残りの操作回数」とXからD*(X/D)の値を引き
「X/D回移動した座標」を求めます。
さらにKが偶数か奇数かで場合分けを行い、偶数の場合は「X/D回移動した座標」に戻るため、
Xの値をそのまま表示し、奇数の場合は「X/D回移動した座標」からDを引いた値を表示します。
このような形で最小値を求める事が可能です。
最後に
うーん、完全に考察不足ですね。場合分けは思いついてたんで、
あとは偶数・奇数を利用すれば解けそうだなぁってとこまでは
当たりはついたんですが、回答には至りませんでしたね。。。
もうちょっと勉強時間ふやそうかなぁ、、、