LinuxとMacと俺と

　ARC092/ABC091 D - Two Sequencesを解いていきます。 問題 https://beta.atcoder.jp/contests/arc092/tasks/arc092_b 感想 　本番でC問題も解けず、焦ってこの問題見たら絶望しました。 　何か規則性はないものかと必死で探して見たものの見つからず、解ける気がしませんでした。今後のために解法を書いておく事にしました。 　結果はもちろん0完。。。 解法 　aとbを足した全ての値を全て計算すると、計算量はO(n^2)となり最大で400億になってしまうので間に合わない。 　そこで二進数の各位ごとに計算する。 　　 10進数 2進数 0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 16 10000 　 　この表を見ると2^kの位は０と１が2^k個づつ交互に並んでいることがわかる。 　よって、 　ai + bj の ２^kの位 の値は、ai + bj の値が... 　0 ≤ ai+bj < 2^k の時 0    2^k ≤ ai+bj < 2*2^k の時 1    2*2^k ≤ ai+bj < 3*2^k の時 0    3*2^k ≤ ai+bj < 4*2^k の時 1 　4*2^k ≤ ai+bj < 5*2^k の時 0    5*2^k ≤ ai+bj < 6*2^k の時 1   ...... となる。 　これは、mod(2*2^k)としてしまっても構わないので、 　　　　ai ≡ n (mod 2*2^k) 　　　　bj ≡ m (mod 2*2^k) 　とすると、 0 ≤ n+m < 2^k の時 0 2^k ≤ n+m < 2*2^k の時 1 2*2^k ≤ n+m < 3*2^k の時 0 3*2^k ≤ n...

　最近競プロを始めて、UnionFindを使う問題に出会うことが増えたので実装してみた。 Union-Findとは 　UnionFindは、素集合（互いに素な集合）を求めるアルゴリズムです。 　例えば、グラフのある二つの頂点が連結されているかどうか調べたり、ある頂点にいくつの頂点が繋がっているかなどを調べるためのアルゴリズムです。 コード 　チーター本の実装をアレンジした形になっています。 class UnionFind{ public: vector<int> uni; UnionFind(int s) : uni(s, -1) { } //頂点aが所属するグループを調べる int root(int a) { if (uni[a] < 0) return a; return uni[a] = root(uni[a]); } //頂点aと頂点bを繋ぐ。もともと同じグループの時falseを返す bool connect(int a,int b) { a = root(a); b = root(b); if (a == b) return false; if (uni[a] > uni[b]) { a ^= b; b ^= a; a ^= b; } uni[a] = uni[a] + uni[b]; uni[b] = a; return true; } //頂点a,bが同じグループであるかを調べる bool isConnect(int a,int b) { return root(...

　ARC087 / ABC082を解いたので、初心者なりに考え方などを書いて行きます。 　AtCoderの解説放送を参考にしています。 https://www.youtube.com/watch?v=GDuzZIuWs2Q A - Round Up the Mean 　a+b+1の平均を取れば良い。 #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int a,b; cin >> a >> b; cout << (a+b+1) / 2 << endl; return 0; } B - Two Anagrams 　s,tをソートして、tを逆順にして比較すればおk。 #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); string s,t; cin >> s >> t; sort(s.begin(),s.end()); sort(t.begin(),t.end()); reverse(t.begin(),t.end()); cout << (s < t ? "Yes" : "No") << endl; return 0; } C - Good Sequence 　数字が出てきた回数がその数字よりも少なかったら出てきた回数、多かったら回数-その数字で良い数列にすることができます。 　数字が出てきた回数を数え上げるところで少し悩んだ。 #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios...