前回はバイト先で無限に書類をシュレッダーにぶちこむというクソ仕事のせいで参加できませんでした。ABC177はちゃんと参加できたのと、新しい知識がいくつも出てきたので復習していきます。
また、ABC178が日曜日にありますが、私は石川で友人と呑んだくれる予定なので参加できません。
目次
1.A問題
キーワード:やるだけ,算数
算数ができれば解ける問題です。みはじって懐かしいですよね。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| double d, t, s; | |
| cin >> d >> t >> s; | |
| if (d / s <= t) | |
| cout << "Yes" << endl; | |
| else | |
| cout << "No" << endl; | |
| return 0; | |
| } |
by 2.B問題
キーワード:文字列,部分文字列,最小値
ある文字列内に指定の文字列を作る場合、最低何箇所書き換えればいいかという問題。私は最初「なにこれ・・・？」となってC問題を先にやってましたが、あとで考えたらやるだけの問題でした。そもそも問題のタイトルがsubstr使えみたいな感じですし。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int main() { | |
| string s, t; | |
| cin >> s >> t; | |
| int s_l = s.size(), t_l = t.size(); | |
| int ans = t_l; | |
| rep(i, s_l - t_l + 1) { | |
| string tmp = s.substr(i, t_l); | |
| int count = 0; | |
| rep(j, t_l) { | |
| if (tmp[j] == t[j]) count++; | |
| } | |
| ans = min(ans, t_l - count); | |
| } | |
| cout << ans << endl; | |
| return 0; | |
| } |
3.C問題
問題:C – Sum of product of pairs
キーワード:ライブラリ利用,数学
競プロフレンズさんの解説の図がわかりやすいと思います。
フェネック「C問題は ((ΣAi)^2 – Σ(Ai^2))/2 が答えだねー。この問題みたいに、「i<jの全ての組(i,j)について……」って問題で、「全ての組(i,j)について計算してからi=jの分を引いて2で割る」っていうのよく使うテクニックだから覚えておくといいよー」 pic.twitter.com/1stRIjuqj4
— 競技プログラミングをするフレンズ (@kyopro_friends) August 29, 2020
mod計算ですが、自力でmod計算しているとWAになったので、AtCoderの公式ライブラリを用いました。
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| // auto mod int | |
| // https://youtu.be/L8grWxBlIZ4?t=9858 | |
| // https://youtu.be/ERZuLAxZffQ?t=4807 : optimize | |
| // https://youtu.be/8uowVvQ_-Mo?t=1329 : division | |
| const int mod = 1000000007; | |
| struct mint { | |
| ll x; // typedef long long ll; | |
| mint(ll x = 0) : x((x % mod + mod) % mod) {} | |
| mint operator-() const { return mint(-x); } | |
| mint& operator+=(const mint a) { | |
| if ((x += a.x) >= mod) x -= mod; | |
| return *this; | |
| } | |
| mint& operator-=(const mint a) { | |
| if ((x += mod - a.x) >= mod) x -= mod; | |
| return *this; | |
| } | |
| mint& operator*=(const mint a) { | |
| (x *= a.x) %= mod; | |
| return *this; | |
| } | |
| mint operator+(const mint a) const { return mint(*this) += a; } | |
| mint operator-(const mint a) const { return mint(*this) -= a; } | |
| mint operator*(const mint a) const { return mint(*this) *= a; } | |
| mint pow(ll t) const { | |
| if (!t) return 1; | |
| mint a = pow(t >> 1); | |
| a *= a; | |
| if (t & 1) a *= *this; | |
| return a; | |
| } | |
| // for prime mod | |
| mint inv() const { return pow(mod - 2); } | |
| mint& operator/=(const mint a) { return *this *= a.inv(); } | |
| mint operator/(const mint a) const { return mint(*this) /= a; } | |
| }; | |
| istream& operator>>(istream& is, mint& a) { return is >> a.x; } | |
| ostream& operator<<(ostream& os, const mint& a) { return os << a.x; } | |
| int main() { | |
| ll n; | |
| cin >> n; | |
| vector<mint> a(n); | |
| rep(i, n) cin >> a[i]; | |
| mint sum = 0, ans = 0; | |
| rep(i, n) sum += a[i]; | |
| // cout << "sum=" << sum << endl; | |
| ans = sum * sum; | |
| // cout << "ans1=" << ans << endl; | |
| rep(i, n) ans -= a[i] * a[i]; | |
| // cout << "ans2=" << ans << endl; | |
| cout << ans / 2 << endl; | |
| return 0; | |
| } |
コードにはありませんが、1億9を表すとき、いつも100000009と書いていたのですが、1e8+9で書けることを知りました。
4.D問題
問題:D – Friends
キーワード:Union-Find,ライブラリ利用
友達同士を同じグループに分けないようにしようという問題。友達関係をグラフでやるとめんどくさいので集合でやって、最も大きい集合のサイズが答えになるというのはわかったのですが、実装の仕方が全くわからずに断念。
集合を作って、さらに集合を結合させたり、どの集合に属しているかを実現するには、Union-FIndというデータ構造があるようです。
Unionが集合をくっつける、Findがどの集合に属しているかを探すことらしく、この2つのクエリを高速に処理できるデータ構造のことのようです。このとき、集合を木構造で保持します。
ここに2つの工夫を行います。それが集合のくっつけ方と経路集約です。
4-1.集合のくっつけ方
まず前提として、各頂点は根にくっつけることとしています。そして、くっつけるときは小さい方の集合を大きい方の集合にくっつけるようにします。こうすることで、木の深さがそれほど深くならずに済みます。こうすると、計算量はO(log(N))になります。これについての証明はABC157の解説放送でやっています。(cf.ABC157解説放送)
4-2.経路集約
根に向かって探索をしますが、深い木だと計算量が多くなるので、同じ根に繋がるならば、その根にくっつけるようにします。
この場合、ならし計算量はO(log(N))となります。
4-3.両方の工夫をする
ならし計算量はO(α(N))になるようです。アッカーマン関数というらしい。
4-4.コード
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| struct UnionFind { | |
| vector<int> d; //リンクの情報。同時にサイズも持つ。 | |
| UnionFind(int n = 0) : d(n, -1) {} //最初はサイズは-1に設定 | |
| int find(int x) { // findの実装 | |
| if (d[x] < 0) return x; //サイズが負なら親なのでその親のIDを返す | |
| return d[x] = find(d[x]); //子なら根に向かって探索をする。 | |
| // d[x]=とすることで経路縮約を実現。 | |
| } | |
| bool unite(int x, int y) { | |
| x = find(x); | |
| y = find(y); // 2つの頂点を持ってくる | |
| if (x == y) | |
| return false; //連結成分が一致するとやることがない。falseにするとくっつけられるかどうか確認できて楽。 | |
| if (d[x] > d[y]) | |
| swap(x, y); // xの方を大きいとするが、サイズは負なので不等号に注意。 | |
| d[x] += d[y]; //くっつけたのでサイズを合算する | |
| 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() { | |
| int n, m; | |
| cin >> n >> m; | |
| UnionFind uf(n); | |
| rep(i, m) { | |
| int a, b; | |
| cin >> a >> b; | |
| --a, --b; | |
| uf.unite(a, b); | |
| } | |
| int ans = 0; | |
| rep(i, n) ans = max(ans, uf.size(i)); | |
| cout << ans << endl; | |
| return 0; | |
| } |
これは解説放送聞きながらコメントを入れて写経したものです。Union-FIndのコード自体はAtCoderのライブラリにあります。snippetに登録しておきましょう。
4-5.構造体
競プロをやっていると、C問題や簡単なD問題では構造体を使うことがまったくなく、未だによくわかっていません。
構造体とは、いろいろな種類の互いに関連するデータを纏めて、一つの塊にしたものらしいです。この構造体の中には上のコードでも書いたように関数も入れられます。メンバ関数と言うらしいですが。
classとの違いは、デフォルトのアクセシビリティがpublicかprivateからしいです。
5.おわりに
今回はB問題はやるだけの問題なのに通すのが遅れてパフォーマンスを下げてしまいましたが、なんやかんやでレートはプラスになって、highest更新できました。しかし、緑までまだまだ遠いので、アルゴリズムとデータ構造を勉強して行きたいと思います。