各連結成分が何らかの値を持っているときのUnion Findの書き方
概要
最近F - Construct HighwayやA - Reachable Townsが立て続けに解けなくて悲しかったので、お互いに共通する「UnionFindの各連結成分が変数を持っていて、mergeするときにその変数を使ってなんかする」みたいな問題をすっとかけるようにしたいなと思い、考え方を記すことにした。 他にも使う問題があったら足していきたい/教えてほしい。
考え方
各連結成分が持つ変数のことをで表すことにする。両方の問題で言えることだが、
はどのような値なのか？
- どの
- どうやってマージするのか？
を考える必要が出てくる。以下それぞれの問題に対して順番に考えていく。
1. はどのような値なのか？
ここがうまいこと設定できればこの解き方で解ける可能性が高そう。
F - Construct Highwayについてはその連結成分のうち、次数が足りない頂点群をとすればよい。（例えば、
ならその連結成分についてはまだ頂点1は2回、頂点3は1回、頂点4は1回別の連結成分とつなぐ必要があることを表す）
A - Reachable Townsについては、各連結成分が持つ点のy座標の最小値をとすればよい。
2. どのを持つ連結成分とマージするのか？
すべての連結成分をなめてその都度を見ていると
かかり、TLEになってしまう。そこで、各
がうまく管理されるようにしといてやる必要がある。
を管理するために、各連結成分について代表点
を
と結びつけておく。
二つの問題に共通していることだが、必要なのはというペアが適切にソートされていて、削除や追加、検索にそんなに時間を要さないこと。ということは、setを使えばうまくいきそうだということがわかる。従って、F - Construct Highwayについては、
というペアを
の長さの降順にソートされるようにsetに入れておけばよさそうだし、A - Reachable Townsについては
というペアをそのままsetに入れておけばよさそう(デフォでsetはless<int>()でsortするので)。
そうしたら、あとはsetの先頭と比較していけばよい。F - Construct Highwayなら先頭の二つをmergeしていけばいい。A - Reachable Townsならが見ている点のy座標より小さいものについてずっとmergeを繰り返していく。
3. どうやってマージするのか？
ここまでくればもう後は自然に書けそう。ここの処理は当然問題によるが、一応書いておく。
F - Construct Highwayについて、と
がmergeされるときは、setから二つをpopしてきて、
と
の末尾頂点をpop_backする。そのあと二つを融合させた
がsizeが1以上なら
をsetに再挿入。（なんか
のサイズがでかいときにTLEしそうな感じもある？その場合setからコピー&popするんじゃなくてうまいこと参照とか使う必要があるかも、後でmergeしてから二つ目の要素をeraseする方法も試して、時間を比べてみる）
A - Reachable Townsについて、と現在見ている頂点
（ただし
は
のy座標）がmergeされるときは、setから
をpopしてきて
と
をmergeする。これを
となる
について繰り返したのち、それらの中で最も小さいy座標を
としたときに
をsetに再挿入すればよい。
verify
C++11以降の負の整数に対する割り算の切り上げ、切り捨て問題を解決する
C++における割り算問題はなかなか難しく、どのように実装するか悩ましい。時々競プロで出題されるが、負の整数に対して切り上げ、切り捨てを含む割り算の記事がないような気がしたので、せっかくなのでここにまとめておく。
結論
のとき、
(切り捨て),
(切り上げ)はそれぞれ
auto div_floor = [](ll x, ll y){ if(y < 0) x = -x, y = -y; if(x >= 0) return x / y; return (x-y+1)/y; }; auto div_ceil = [](ll x, ll y){ if(y < 0) x = -x, y = -y; if(x >= 0) return (x+y-1)/y; return x/y; };
考えかた
まず、非負整数に対して、
の切り上げ、切り捨ては次のように簡単に実装できる：
int div_ceil(int a, int b) { // 切り上げ return (a+b-1)/b; } int div_floor(int a, int b) { // 切り捨て return a/b; }
C++11以降では、負の数に対する割り算の挙動が次のように定められている( 整数に対する除算と剰余算の丸め結果を規定 - cpprefjp C++日本語リファレンス )：
整数型を項とする/演算子の結果は代数的な商から小数部を切り捨てたものとなる。注釈：これは「ゼロ方向への切り捨て(truncation towards zero)」とも呼ばれる。
例を出すと次のようになる。
+7 / +2 == +3 -7 / +2 == -3 +7 / -2 == -3 -7 / -2 == +3
もうこの時点で四つ場合分け出てきて面倒くさいので、以下除数を正で固定しておく。もし除数が負なら、被除数と除数の符号を反転すればよい。こうするとだいぶ考えやすくなる。つまり、
+7 / +2 == +3 // 数学的には切り捨て -7 / +2 == -3 // 数学的には切り上げ
にだけ焦点を当てればよい。これを見るとわかるが、数学的に言えば、C++11以降の実装では除算は正の被除数に対しては切り捨てであるが、負の被除数に対しては切り上げである。結構盲点ではある。ここまでで言えば、場合分けは次のようになる()：
floor(a/b) = a/b // a>=0のとき floor(a/b) = ??? // a<0 のとき ceil(a/b) = ??? // a>=0のとき ceil(a/b) = a/b // a<0 のとき
残った二つのうちfloor(a/b)から考える。例えばb=5のときを考えると-15, -14, -13, -12, -11が-3となってほしい被除数だが、実際のC++(11+)では-19, -18, -17, -16, -15が-3となる被除数である。この差を埋めるには5-1=b-1を引けばよい。一般化するほどじゃない（しめんどい）のでこれで良しとすると、
floor(a/b) = (a-b+1)/b
でok。 ceil(a/b)もほぼ同じ。b=5なら6,7,8,9,10が2となってほしい被除数だが、実際には10,11,12,13,14が2となる被除数。この差を埋めるには5-1=b-1を足せばよい。よって
ceil(a/b) = (a+b-1)/b
とすればよく、これは初めに見せたものと同じものである。
Disjoint Set(Union Find木)を一から書けるようにする
将来のコーディング試験に備えて。そのうちfenwick treeとかほかのも書くかもしれない。(typedef long long ll;とかrepマクロの定義は省略する)
あくまで自分のための備忘録なので、初めて組む人はこっち見た方がいいと思う Union-Find Tree を理解する！素集合系を扱うデータ構造 | アルゴリズムロジック
コーディングの順番としては、 ノードの定義→findRoot→isSame→unite(→Setsize) とするのが自然な気がする。
まずは普通にノードを定義する。集合の大きさがよく問われる気がするので、sizeによる併合を考えておく。
private: vector<ll> sizes, parents; public: disjoint_set(ll N) { sizes.resize(N); parents.resize(N); rep(i, N) { sizes[i] = 1; parents[i] = i; } }
sizesとか直で見れないようにしておく。後でわかるが、sizes[i]はノードiを含む集合の大きさになるとは限らないからだ（sizes[iの親ノード]が集合の大きさになる）。
次に集合の代表ノード(根)を見つける。
ll findRoot(ll x) {
if(parents[x] != x) parents[x] = findRoot(parents[x]); // 経路圧縮
return parents[x];
}
経路圧縮してO(log(N))にする。 そして、uniteとisSameを実装する。isSameからuniteが自然かな。uniteは「長いものに巻かれろ」という覚え方で、小さい方から大きい方に接続する。
bool isSame(ll x, ll y) { return findRoot(x) == findRoot(y); } bool unite(ll x, ll y) { if (isSame(x, y)) return false; x = findRoot(x); y = findRoot(y); if (sizes[x] > sizes[y]) { // サイズが小さい方を大きい方につける parents[y] = x; sizes[x] += sizes[y]; } else { parents[x] = y; sizes[y] += sizes[x]; } return true; }
これだとunite時に無駄に二回findRootしていることになるが、まあ定数倍だし、こっちの方がわかりやすいのでこのままにしておこうと思う。小さい木を大きい方につけることで、経路圧縮と合わせて計算量はほとんど定数倍(O(α))に落ちる。 最後にSetsizeを実装して終わり。
ll Setsize(ll x) {
return sizes[findRoot(x)];
}
全体としてはこんな感じ：
struct disjoint_set{ private: vector<ll> sizes, parents; public: disjoint_set(ll N) { sizes.resize(N); parents.resize(N); rep(i, N) { sizes[i] = 1; parents[i] = i; } } ll findRoot(ll x) { if(parents[x] != x) parents[x] = findRoot(parents[x]); // 経路圧縮 return parents[x]; } bool isSame(ll x, ll y) { return findRoot(x) == findRoot(y); } bool unite(ll x, ll y) { if (isSame(x, y)) return false; x = findRoot(x); y = findRoot(y); if (sizes[x] > sizes[y]) { // サイズが小さい方を大きい方につける parents[y] = x; sizes[x] += sizes[y]; } else { parents[x] = y; sizes[y] += sizes[x]; } return true; } ll Setsize(ll x) { return sizes[findRoot(x)]; } };
verifiedする：
よさそう。
AtCoder 精進記録 2021-05-01~2021-05-07
AtCoderの気になった問題やコードの間違いなどをどこかに書きつけたいと思っていて、Google SpreadsheetやGoogle Documentを使ってみたが、どうもなんか違うなーという気がしたのでこっちに一言だけコメントを付けてまとめてみることにした。markdown形式でまとめてつかっていけるのはなかなかの強みだと思う。
2021-05-01
zone2021 C
max(min)の形は二分探索、というのが定石らしい。さらに各能力値をある値以上か未満かというのをbool型に落とし込んで二分探索していくというのも(もっと高度な)定石らしい。難しいので今はとりあえずパスしとく。
zone2021 D
何故か解けなかった、、、かなり悔しい。答えを聞いたらなんてことはなかった。'R'が来たらフラグを反転させてフラグによってdequeの前に足したり後ろに足したりする。ここまでは割と簡単にできた(string型を使ったが)。しかし、その次に(すでにtに文字列を入れていたので、)dequeからstring tに移していきながらt.back()と比較して同じなら消すという発想が思い浮かばなかった、、。
2021-05-03
abc133 B
平方数判定のときは、
for(int i = 1; powdist / i >= i; i++){ if(powdist % i == 0 && powdist / i == i) return true; }
のようにすると効果的なようだ。sqrtからの丸めでやると誤差が無視できないのでWAとなった。(たぶんちゃんとやればACになるのかも？)
abc157 C
ひどい間違え方をした：
if(n == 1) ndigmin = 0, ndigmax = 9; if(n == 2) ndigmin = 10, ndigmax = 99; else ndigmin = 100, ndigmax = 999;
このコードは当然思い通りに動かない。めんどくさがらずに最後までif文を書こう。あとこういう10進数の桁を扱う問題では文字列型に変換するといいっていうの忘れてた。…と思って文字列型でやり直したら平気でこんなコードを書いてしまった。
string num_s = to_string(num);
rep(i, m){
if(num_s.at(s.at(i) - 1) != c.at(i)) possible = false;
}
当然、桁数の比較のところで、c.at(i) + '0'としなければならない。気をつけよう。
2021-05-04
初期化のミスをやらかした。ループを回した結果出てくる値の最小値をさらにその外のループで出す際、内側のループで足し上げるための変数の初期化を忘れてサンプルケースと答えが合わなかった。気を付けよう。
ll entry_to_a = 0LL, b_to_exit = 0LL; ll min_sum_a = LONG_LONG_MAX , min_sum_b = LONG_LONG_MAX; rep(i, n){ rep(j, n){ entry_to_a += abs(a.at(j) - a.at(i)); //初期化忘れてる b_to_exit += abs(b.at(j) - b.at(i)); } min_sum_a = min(entry_to_a, min_sum_a); min_sum_b = min(b_to_exit, min_sum_b); }
これ
for(int i = 1; i <= 20; i++){ if(100 * i <= x && x <= 105 * i) possible = true; else if(x >= 2100) possible = true; }
だけでとけるよな…?こういう算数めいたこともしてACを稼いでいくのも重要だと思った。
2020-05-05
解けたが、一度WAしてしまったし、デバッグしながらギリギリ解いた感じ。余裕が出てきたらもっと見やすいコードを一発でかけるようにしたい。
解き方、というより題意を満たす単調増加数列が何通りあるかについて、概数を出しておく。このままだとなかなか難しいが、次のように不等号を変換して考えると◯(まる)と｜(仕切り)のみで考えられる：
を満たすような数列は何通りか？
当然答えは
通り。今後の概算として使っていくと良いと思われる。それと、再帰関数を考えたりするとき重要になってくるのが引数の扱い。どうしてもグローバル変数を多めに取るほうが楽になってしまう。お行儀は悪いが、そうしたほうが引数を少なくできるのでそのような問題は(競技プログラミングでは)割り切ってグローバル変数を使っていこう。
毎回思うけどこういう問題、添え字が0から始まらないのがすごい歯がゆい……適当に読み替えて入力を適宜-1していくのがよさそうかな？
これもしTLEしそうになったらそのプログラムをn = 1から10まで回して予め結果をプログラムにストアしておいてあとは出力するだけ、みたいなこともできるな……(邪道)そういうテクニックもまあ使えないことはないのかな…？
2020-05-06
現在グラフ理論に関する深さ優先探索を学習している。Boost Graph libraryを使えるようになるとめちゃくちゃ捗りそうな予感がする……が、今のうちからそれに頼りっきりなのもよくなさそうなのでまずは実装できるようにしようと思う。（というかそのうちBoost自体をを使えるようにしていきたい…）
スタックを用いて実装する方法をいつか学びたい(再帰が深くなりすぎるとスタックオーバーフローを起こすらしい)。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=ja
またchar型にcinしてから比較するときに、
c == 0
みたいにするバグを入れてしまった。正しくはもちろん
c == '0'
のようにしなければならない。それと、wとhを逆にしがち。ここらへんは根気強く治していこうと思う。
2020-05-07
C++の構造体ってめちゃくちゃ複雑だな……コンストラクタとか色々あったりしてほとんどクラスみたいだね、いつかはちゃんと言語の仕様も勉強しなきゃな、と思っている。
解答：Submission #22357670 - AtCoder Beginner Contest 126
こんなかんじで書いて提出したけど、これだとsample-2.inに関して"0\n0\n0\n0\n0\n"のように出力されsample-2.outと一致しないが、ACではある。サンプルと一致しないがACというパターンも抑えておこう。
難しい。確認したら青diffだったので、とりあえずは一旦保留する。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891&lang=ja
あとで答えを見て理解したら自分でコードを組んでみよう。それからできれば期間をおいてから復習したい。
wsl環境にmvswapを導入した話
ファイル名の交換コマンド: mvswap - シリコンの谷のゾンビ
ほぼこの方の通りに設定したが、Ubuntu(WSL)ではmktempが使えなかったのと、その他もろもろエラーを吐かれたので以下のようにコードを変更した：
#!/bin/sh TMPNAME=".tmp-hoge-fuga-piyo" if [ $# -eq 2 ] then mv $1 $TMPNAME mv $2 $1 mv $TMPNAME $2 fi
TMPNAMEを定めているところは、まあしょうがないと思おう。多分調べればmktempに相当する機能があるだろうがめんどくさくなった。
それから、このファイルを適当なディレクトリ(今回は/mnt/c/code/)にmvswapで保存し、pathが通っているフォルダ：
$ echo $PATH /home/(ユーザ名)/.local/bin:/home/(ユーザ名)/.nvm/versions/node/v16.0.0/bin:...(その他もろもろ)
のうちの、/home/(ユーザ名)/.local/binに移し、権限を755(rwxr-xr-x)に変更する：
$ cp /mnt/c/code/mvswap /home/(ユーザ名)/.local/bin $ sudo chmod 755 /home/(ユーザ名)/.local/bin/mvswap
あとは元記事同様本当にできているかを確認すればOK。
今後atcoder-cliが落としてきてくれたテストファイルを
/mnt/c/code/atcoder/ABC051-100/abc077/c/test$ mvswap sample-1.in sample-3.in /mnt/c/code/atcoder/ABC051-100/abc077/c/test$ mvswap sample-1.out sample-3.out
のようにすれば、容易に入れ替えることができる。前回qiitaに投稿した
Visual Studio Code with WSLでatcoder-cliを使いつつデバッグもできる環境構築 - Qiita
内ではデバッグ時の標準入力をsample-1.inに指定していたので、WAとなっているsampleファイルをmvswapでsample-1.inと交換すればそのサンプルケースでデバッグすることができるようになる。
bit全探索と演算子優先順位(C++)
いままで全然論理演算子を使っていなかったのでここで不意打ちを食らって全然通らなくて悩んでいたのでまとめてみた。
基本的に、
代入系 ＜ 論理OR, AND ＜ ビットOR, NOT, AND ＜ 関係演算子 ＜ ビットシフト ＜ その他のやつ(四則演算てきな)
と覚えておけばよさそう。特にbit演算を使うような場面では特に太字部分に気を付けるとよいかもしれない。
はbit全探索を使う代表的な例だが、
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) typedef long long ll; int main(){ //1 int n; cin >> n; vector<int> a(n); vector<vector<int>> x(n); vector<vector<int>> y(n); rep(i, n){ cin >> a.at(i); rep(j, a.at(i)){ int x_ij, y_ij; cin >> x_ij >> y_ij; x.at(i).push_back(x_ij - 1); y.at(i).push_back(y_ij); } } //2 int maxhonest = 0; bool possible; rep(bit, 1 << n){ //正直者1, 不親切な人0, n bit possible = true; rep(i, n){ //発言と正直者の一致を正直者のみ見ていく if((1<<i) & bit != 0){ //ここ間違い rep(j, a.at(i)){ if((bool)((1 << x.at(i).at(j)) & bit) != y.at(i).at(j)){ possible = false; break; } } } if(!possible) break; } if(possible) maxhonest = max(maxhonest, (int)__builtin_popcount(bit)); } //3 cout << maxhonest << endl; }
としていて、なかなか間違いに気づかなかった。当然コメントした部分を
if(((1<<i) & bit) != 0){
とするべき。こういう比較演算子とbit演算子は特に気をつける部分かも。基本的に動作してほしい順にすべて括弧をくくっていけば良いと思う。
