Atcoder Grand Contest 010 D. Decrementing
Atcoder Grand Contest 010 D. Decrementing
D: Decrementing - AtCoder Grand Contest 010 | AtCoder
感想
奇数の$\ gcd\ $で割ったときに偶奇の個数が変わらないことがポイントだった。
解法
明らかに愚直に考えると厳しいので、とりあえず偶奇によって場合をわけて考えることにする。まず（最初の状態も含めて）ある操作後にすべての数が偶数であるということはありえない。すなわち、一つ以上の奇数が存在する。
まず偶数の個数が奇数個の場合を考えると、いかなる場合においても、偶数の個数が偶数個の状態を相手に渡すことができるので、先手が勝つ。なぜなら、ある偶数を選んで操作によって奇数にすると、それらを$\ gcd\ $で割ったものの偶奇も変わらない（$\ gcd\ $が奇数であるため）ので、結局相手は偶数が偶数個の状態を受け取ることになり、そこからはどう操作しても必ず偶数が奇数個の状態になって返ってくる。これを繰り返すことで、結局先手が勝つことがわかる。
逆に偶数の個数が偶数個の場合は、奇数が2個以上ある場合は、先手がどんな操作をしても上に述べた先手必勝の状態を渡すことになるので、後手必勝である。奇数の個数が一個のときは、偶数に操作をしてしまうと上の偶数が奇数個の状態（先手必勝）を渡してしまうことになるので、奇数に対して操作するしか手はない。これによって、すべてが偶数になるので、2以上の$\ gcd\ $で割られることになり、数列の値はすべて半分以下になる。このあとの操作の進み方は上と全く同様になるので、勝敗が決定するまで計算する。計算の性質上明らかにこれは高々$\ \log (max(A_i))\ $回の計算で終了する。よって計算量は$\ O(n \log(max(A_i)))\ $となる。
実装
#include "bits/stdc++.h" using namespace std; int print(bool first) { puts(first ? "First" : "Second"); return 0; } int main() { int n; scanf("%d", &n); vector<int> a(n); for (int i = 0; i < n; i ++) scanf("%d", &a[i]); int even_cnt = 0; for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0); assert(even_cnt != n); //includes at least one odd number if (even_cnt & 1) return print(true); if (even_cnt != n - 1) return print(false); bool f = true; while (true) { for (int i = 0; i < n; i ++) { if (a[i] & 1) { if (a[i] == 1) { return print((f && (n - 1) % 2 == 1) || (!f && ((n - 1) % 2 == 0))); } a[i] --; break; } } f ^= 1; int gcd = a[0]; for (int i = 1; i < n; i ++) gcd = __gcd(a[i], gcd); for (int i = 0; i < n; i ++) a[i] /= gcd; even_cnt = 0; for (int i = 0; i < n; i ++) even_cnt += (a[i] % 2 == 0); if (even_cnt & 1) return print(f); if (even_cnt != n - 1) return print(!f); } }
Atcoder Grand Contest 006 D. Median Pyramid Hard
Atcoder Grand Contest 006 D. Median Pyramid Hard
D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder
感想
いいところまでは考えられたような気がしたけど結局解説を読んで。
てきとうに書いて投げたら通った。
最近は二分探索をあまりバグらせない気がする。
解法
頂上が$\ x\ $以上であるかどうかで二分探索する。すべての数を、$\ x\ $以上であるかどうかによって1と0のみで分類でき、各マスは下の3マスの多数決になることから、パターンを見出す。
実装
#include "bits/stdc++.h" using namespace std; int main() { int n; scanf("%d", &n); int N = 2 * n - 1; vector<int> a(N); for (int i = 0; i < N; i ++) scanf("%d", &a[i]); int lb = 1, ub = N; while (ub - lb > 1) { int mid = (lb + ub) / 2; vector<int> b(N); for (int i = 0; i < N; i ++) b[i] = a[i] >= mid; int m = N / 2; if (b[m] == b[m + 1] || b[m] == b[m - 1]) { (b[m] ? lb : ub) = mid; } else { int left = m, right = m; while (left > 0 && (b[left] ^ b[left - 1]) == 1) left --; while (right < N && (b[right] ^ b[right + 1]) == 1) right ++; if (m - left < right - m) (b[left] ? lb : ub) = mid; else (b[right] ? lb : ub) = mid; } } printf("%d\n", lb); return 0; }
Atcoder Grand Contest 002 D. Stamp Rally
Atcoder Grand Contest 002 D. Stamp Rally
D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder
解法
二分探索をまとめてやる感じのやつ。各$\ mid\ $の値に関するソートをしておくことで左から順に見ていける。$\ O(m {\log}^2 m)\ $。
実装
#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() #define mp make_pair struct UnionFind { int n; vector<int> parent; vector<int> rank; vector<int> num; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } UnionFind(int n_) { n = n_; parent.resize(n); for (int i = 0; i < n; i ++) parent[i] = i; rank.assign(n, 0); num.assign(n, 1); } void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { if (rank[x] < rank[y]) { parent[x] = y; num[y] += num[x]; } else { parent[y] = x; if (rank[x] == rank[y]) rank[x] ++; num[x] += num[y]; } n --; } } bool same(int x, int y) { return find(x) == find(y); } int get() { return n; } int get(int x) { return num[find(x)]; } }; int main() { int n, m; scanf("%d%d", &n, &m); vector<pair<int, int>> es(m); for (int i = 0; i < m; i ++) { int a, b; scanf("%d%d", &a, &b); a --, b --; es[i] = mp(a, b); } int q; scanf("%d", &q); vector<int> x(q), y(q), z(q); vector<int> lb(q), ub(q); for (int i = 0; i < q; i ++) { scanf("%d%d%d", &x[i], &y[i], &z[i]); x[i] --, y[i] --; lb[i] = 0, ub[i] = m; } vector<int> idx; for (int i = 0; i < q; i ++) idx.push_back(i); for (int loop = 0; loop < 20; loop ++) { sort(all(idx), [&](const int &a, const int &b) { return (lb[a] + ub[a]) / 2 < (lb[b] + ub[b]) / 2; }); UnionFind uf(n); int p = 0; for (auto &i : idx) { int mid = (lb[i] + ub[i]) / 2; while (p <= mid) { uf.unite(es[p].first, es[p].second); p ++; } int sum = uf.get(x[i]) + uf.get(y[i]); if (uf.same(x[i], y[i])) sum /= 2; if (sum < z[i]) { lb[i] = mid + 1; } else { ub[i] = mid; } } } for (int i = 0; i < q; i ++) printf("%d\n", lb[i] + 1); return 0; }
Atcoder Grand Contest 007 C. Pushing Balls
Atcoder Grand Contest 007 C. Pushing Balls
C: Pushing Balls - AtCoder Grand Contest 007 | AtCoder
感想
難しいよ
解法
解説動画がわかりやすい。各ボールの距離に関する数列を書いて実験すると、その次のステップ（の期待値）の数列も同様に等差数列になることが証明される。
等差数列になることが証明できれば、あとは今の数列の長さ$\ N_{now}\ $と初項$\ d_{now}\ $と公差$\ x_{now}\ $より次のそれらを計算していけば良い。計算のたびに、その移動の総和の期待値、すなわち(等差数列の総和) / (項数)を足していけば答えになる。
具体的に計算すると、$\ N_{next} = N_{now} - 2,\ d_{next} = \cfrac {(N + 2) d_{now} + 5x_{now}} {N_{now}},\ x_{next} = \cfrac {(N + 4)x_{now}} {N_{now}}\ $となるので、そのように書く。
実装
#include "bits/stdc++.h" using namespace std; double calc(double n, double d, double x) { if (n == 0) return 0; double res = n * (2.0 * d + (n - 1) * x) / (2.0 * n); res += calc(n - 2, ((n + 2) * d + 5 * x) / n, (n + 4) * x / n); return res; } int main() { double n, d, x; scanf("%lf%lf%lf", &n, &d, &x); double ans = calc(2 * n, d, x); printf("%.15lf\n", ans); return 0; }
Atcoder Grand Contest 019 C. Fountain Walk
Atcoder Grand Contest 019 C. Fountain Walk
感想
500点くらいの問題
解法
一般性を失わずに左上にスタート、右下にゴールがあると仮定して、それらを頂点とする長方形を考える。このとき、明らかにこの長方形の外に出て遠回りする方が経路長が短くなるようなことはない。
この長方形の内部で移動することを考えるときに、できるだけ(↓, 噴水, →）という移動をすればよいはずである。ただしこの移動をするために遠回りする必要はなく、まず通過できる噴水の最大値を$\ LIS\ $で求める。さらに図を書いて実験すると、条件を満たすような噴水の置き方の中で、最大個数、すなわち$\ min(gy - sy, gx - sx) + 1\ $個より少ない場合は、通過可能なすべての噴水をこの移動の仕方に使うことができる。$\ min(gy - sy, gx - sx) + 1\ $に等しい場合は、一回だけ噴水を通過して180度回るような移動をしなければいけない（これが最適）。ここを場合分けして素直に計算すればよい。
スタートの位置とゴールの位置は実際には異なるので、うまく処理する。
実装
#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() static const int INF = 1 << 30; static const double PI = acos(-1); int dp[202020]; int main() { int sx, sy, gx, gy; scanf("%d%d%d%d", &sx, &sy, &gx, &gy); int n; scanf("%d", &n); vector<pair<int, int>> p(n), q; for (int i = 0; i < n; i ++) scanf("%d%d", &p[i].first, &p[i].second); for (int i = 0; i < n; i ++) { if (min(sx, gx) <= p[i].first && p[i].first <= max(sx, gx) && min(sy, gy) <= p[i].second && p[i].second <= max(sy, gy)) { q.push_back(p[i]); } } if (sy > gy) for (int i = 0; i < q.size(); i ++) q[i].second *= -1; sort(all(q)); if (sx > gx) reverse(all(q)); for (int i = 0; i < 202020; i ++) dp[i] = INF; for (int i = 0; i < q.size(); i ++) { *lower_bound(dp, dp + 202020, q[i].second) = q[i].second; } int len = lower_bound(dp, dp + 202020, INF) - dp; double ans = (long long) (abs(gy - sy) + abs(gx - sx)) * 100; if (len < min(abs(gy - sy), abs(gx - sx)) + 1) { ans -= (20.0 - 5.0 * PI) * len; } else { ans -= (20.0 - 5.0 * PI) * (len - 1); ans += 10.0 * PI - 20; } printf("%.15lf\n", ans); return 0; }
Atcoder Regular Contest 013 C. 笑いをとれるかな？
Atcoder Regular Contest 013 C. 笑いをとれるかな？
C: 笑いをとれるかな？ - AtCoder Regular Contest 013 | AtCoder
感想
友人が問題文の内容がおもしろいと言っていたのでやったみた。確かにおもしろかった。
解法
各座標軸を基準にみて端点同士の点より内側にある部分は決して食べることができない。よってこれは大きなハバネロが一つ埋め込まれているものとして考えてよく、それぞれの座標のハバネロの位置の最小値と最大値がわかれば、あとはその外側の幅の部分を食べていけることになる。
この幅が高々$\ 6 * N\ $個あって、それらを山とみれば、単純な$\ Nim\ $になっているので、$\ XOR\ $をとると答えがわかる。
実装
#include "bits/stdc++.h" using namespace std; static const int INF = 0x3f3f3f3f; int main() { int n; scanf("%d", &n); int ans = 0; for (int i = 0; i < n; i ++) { int X, Y, Z; int m; scanf("%d%d%d%d", &X, &Y, &Z, &m); int min_x = INF, max_x = 0, min_y = INF, max_y = 0, min_z = INF, max_z = 0; for (int i = 0; i < m; i ++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); min_x = min(min_x, x); max_x = max(max_x, x); min_y = min(min_y, y); max_y = max(max_y, y); min_z = min(min_z, z); max_z = max(max_z, z); } max_x = X - max_x - 1; max_y = Y - max_y - 1; max_z = Z - max_z - 1; int res = 0; res = min_x ^ max_x ^ min_y ^ max_y ^ min_z ^ max_z; ans ^= res; } puts(ans ? "WIN" : "LOSE"); return 0; }
Atcoder Grand Contest 011 E. Increasing Numbers
Atcoder Grand Contest 011 E. Increasing Numbers
E: Increasing Numbers - AtCoder Grand Contest 011 | AtCoder
感想
数論の問題などでたまに見かけるレピュニットの性質をうまく利用した問題で少しおもしろかった。
解法
増加的な数を9個以下のレピュニットの和で表してやると解ける。
レピュニットを$\ R\ $とすると、$\ 9R + 1\ $がきれいになることを利用するのは下の問題でも同じである。
実装1
#include "bits/stdc++.h" using namespace std; //----------------------------------------Library--------------------------------------------- class Bigint { public: static const int BASE = 100000000, LEN = 8; bool negative; std::vector<int> a; Bigint& normalize(); public: Bigint(int x = 0); Bigint(const std::string& s); Bigint& operator = (const Bigint& x); Bigint& operator = (int x); Bigint& operator = (const std::string& s); const bool operator < (const Bigint& x) const; const bool operator > (const Bigint& x) const; const bool operator <= (const Bigint& x) const; const bool operator >= (const Bigint& x) const; const bool operator != (const Bigint& x) const; const bool operator == (const Bigint& x) const; Bigint operator -() const; Bigint& operator += (const Bigint& x); Bigint& operator -= (const Bigint& x); Bigint& operator *= (const Bigint& x); Bigint& operator /= (const Bigint& x); Bigint& operator %= (const Bigint& x); const Bigint operator + (const Bigint& x) const; const Bigint operator - (const Bigint& x) const; const Bigint operator * (const Bigint& x) const; const Bigint operator / (const Bigint& x) const; const Bigint operator % (const Bigint& x) const; friend std::pair<Bigint, Bigint> divmod(const Bigint& lhs, const Bigint& rhs); friend std::istream& operator >> (std::ostream& is, Bigint& x); friend std::ostream& operator << (std::ostream& os, const Bigint& x); friend const Bigint abs(Bigint x); }; Bigint& Bigint::normalize() { int i = a.size()-1; while (i >= 0 && a[i] == 0) i --; a.resize(i + 1); if (a.size() == 0) negative = false; return *this; } Bigint::Bigint(int x) : negative(x < 0) { x = abs(x); for (; x > 0; x /= BASE) a.push_back(x % BASE); } Bigint::Bigint(const std::string& s): negative(false) { int p = 0; if (s[p] == '-') { p ++; negative = true; } else if (s[p] == '+') p ++; for (int i = s.size() - 1, v = BASE; i >= p; i --, v *= 10) { int x = s[i] - '0'; if (x < 0 || 9 < x) { std::cerr << "error: parse error:" << s << std::endl; exit(1); } if (v == BASE) { v = 1; a.push_back(x); } else { a.back() += x * v; } } normalize(); } Bigint& Bigint::operator = (const Bigint& x) { negative = x.negative; a = x.a; return *this; } Bigint& Bigint::operator = (int x) { return *this = Bigint(x); } Bigint& Bigint::operator = (const std::string& s) { return *this = Bigint(s); } const bool Bigint::operator < (const Bigint& x) const { if (negative != x.negative) return negative < x.negative; if (a.size() != x.a.size()) return (a.size() < x.a.size()) ^ negative; for(int i = a.size()-1; i >= 0; i --) if (a[i] != x.a[i]) return (a[i] < x.a[i]) ^ negative; return false; } const bool Bigint::operator > (const Bigint& x) const { return x < (*this); } const bool Bigint::operator <= (const Bigint& x) const { return !(x < (*this)); } const bool Bigint::operator >= (const Bigint& x) const { return !((*this) < x); } const bool Bigint::operator != (const Bigint& x) const { return (*this) < x || x < (*this); } const bool Bigint::operator == (const Bigint& x) const { return !((*this) < x || x < (*this)); } Bigint Bigint::operator -() const { Bigint ret(*this); if (a.size()) ret.negative = !ret.negative; return ret; } Bigint& Bigint::operator += (const Bigint& x) { if (negative != x.negative) return *this -= -x; if (a.size() < x.a.size()) a.resize(x.a.size()); int up = 0; for (int i = 0; i < a.size(); i ++) { a[i] += (i < x.a.size() ? x.a[i] : 0) + up; up = a[i] / BASE; a[i] %= BASE; } if (up) a.push_back(1); return *this; } Bigint& Bigint::operator -= (const Bigint& x) { if (negative != x.negative) return *this += -x; std::vector<int> b(x.a); if ((*this < x) ^ negative) { a.swap(b); negative = !negative; } for (int i = 0, up = 0; i < a.size(); i ++) { a[i] += BASE - (i < b.size() ? b[i] : 0) + up; up = a[i] / BASE - 1; a[i] %= BASE; } return this->normalize(); } Bigint& Bigint::operator *= (const Bigint& x) { negative ^= x.negative; std::vector<int> c(a.size() * x.a.size() + 1); for (int i = 0; i < a.size(); i ++) { long long tmp = 0; for (int j = 0; j < x.a.size(); j ++) { long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp; tmp = v / BASE; c[i + j] = (int)(v % BASE); } if (tmp) c[i + x.a.size()] += (int)tmp; } a.swap(c); return this->normalize(); } Bigint& Bigint::operator /= (const Bigint& x) { return *this = divmod(*this, x).first; } Bigint& Bigint::operator %= (const Bigint& x) { return *this = divmod(*this, x).second; } const Bigint Bigint::operator + (const Bigint& x) const { Bigint res(*this); return res += x; } const Bigint Bigint::operator - (const Bigint& x) const { Bigint res(*this); return res -= x; } const Bigint Bigint::operator * (const Bigint& x) const { Bigint res(*this); return res *= x; } const Bigint Bigint::operator / (const Bigint& x) const { Bigint res(*this); return res /= x; } const Bigint Bigint::operator % (const Bigint& x) const { Bigint res(*this); return res %= x; } std::pair<Bigint, Bigint> divmod(const Bigint& lhs, const Bigint& rhs) { if (!rhs.a.size()) { std::cerr<<"error: division by zero"<<std::endl; exit(1); } Bigint x(abs(rhs)), q, r; for (int i = lhs.a.size() - 1; i >= 0; i --) { r = r * Bigint::BASE + lhs.a[i]; int head = 0, tail = Bigint::BASE; if (r >= x) { while (head + 1 < tail) { int mid = (head + tail) / 2; if (x * Bigint(mid) > r) tail = mid; else head = mid; } r -= x * head; } q.a.push_back(head); } reverse(q.a.begin(), q.a.end()); bool neg = lhs.negative ^ lhs.negative; q.negative = neg; r.negative = neg; return std::make_pair(q.normalize(), r.normalize()); } std::istream& operator >> (std::istream& is, Bigint& x) { std::string tmp; is >> tmp; x = Bigint(tmp); return is; } std::ostream& operator << (std::ostream& os, const Bigint& x) { if (x.negative) os << '-'; if (!x.a.size()) os << 0; else os << x.a.back(); for (int i = x.a.size()-2; i >= 0; i --) { os.width(Bigint::LEN); os.fill('0'); os << x.a[i]; } return os; } const Bigint abs(Bigint x) { x.negative = false; return x; } std::string str(Bigint x) { stringstream st; st << x; return st.str(); } //------------------------------------------------------------------------------------------ bool check(Bigint n, int k) { string s = str((Bigint)9 * n + (Bigint)(9 * k)); int sum = 0; for (int i = 0; i < s.size(); i ++) sum += s[i] - '0'; return sum <= 9 * k; } int main() { Bigint n; cin >> n; int lb = 0, ub = 500000; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (check(n, mid)) ub = mid; else lb = mid; } cout << ub << endl; return 0; }
下の実装はboostの多倍長整数ライブラリによるすっきりした実装。boostはの多倍長演算は遅いっぽく（要検証）、ほとんど$\ TLE\ $してしまった。
実装2
#include "bits/stdc++.h" #include <boost/multiprecision/cpp_int.hpp> #define Bigint boost::multiprecision::cpp_int bool check(Bigint n, int k) { Bigint t = 9 * (n + k); std::string s = t.str(); int sum = 0; for (int i = 0; i < s.size(); i ++) sum += s[i] - '0'; return sum <= 9 * k; } int main() { Bigint n; std::cin >> n; int lb = 0, ub = 500000; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (check(n, mid)) ub = mid; else lb = mid; } std::cout << ub << std::endl; return 0; }
