2020-05-02

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies

codeforces

概要

$1 \sim N$ の $N$ 種類の味のキャンディがある
バッグに1か2種類を入れる
ただし2種類の場合、味の $\text{gcd}$ が2以上でなければならない
バッグの数を最小化しろ
$N \leq 10^{11}$

解法

2種類のペアをつくる数を最大化すればバッグの数を最小化できる。味1のキャンディと $N/2$ より大きいの素数の味のキャンディをペアの片方にすることは不可能である。これらの味の集合を $D$ とすると、ペアの個数は $\lfloor \frac{N-|D|}{2} \rfloor$ 以下である。

この上限を必ず達成できることを示す。 $f(x)=(x$ の素因数のうち最大のもの $)$ とする。 $D$ に属さない味のうち、 $f(x)$ が同じ味のものをまとめた集合を考える。要素数が偶数の集合についてはこれらの集合内でペアをつくればよい。要素数が奇数の集合については $2f(x)$ 以外の要素でペアをつくり、余った $2f(x)$ については別の集合同士でペアをつくればよい。したがって、 $D$ に属さない味のキャンディでペアを構成することは常に可能である。

あとは $N/2$ より大きい素数の個数を高速に求められれば良い。Counting Primes の高速な提出を写経するとこれはできる。

想定解に $10^7$ ごとに素数の数を数えておいて埋め込めばよいと書かれていたので計算したらこどふぉのファイル長の制限に引っかかったの何？

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
// N以下の素数の数を数える  
// https://judge.yosupo.jp/submission/7976 の写経でN<=10^11 が25ms  
__attribute__((target("avx"), optimize("O3", "unroll-loops")))  
ll prime_count(const ll N) {  
    if(N <= 1) return 0;  
    if(N == 2) return 1;  
    const int v = sqrtl(N);  
    int s = (v+1)/2;  
    vector<int> smalls(s), roughs(s);   
    for(int i=1; i<s; ++i) smalls[i] = i;  
    for(int i=0; i<s; ++i) roughs[i] = 2*i+1;  
    vector<ll> larges(s);   
    for(int i=0; i<s; ++i) larges[i] = (N/(2*i+1)-1)/2;  
    vector<bool> skip(v+1);  
    const auto divide = [](ll n, ll d) -> int { return double(n) / d; };  
    const auto half = [](int n) -> int { return (n - 1) >> 1; };  
    int pc = 0;  
    for(int p=3; p<=v; p+=2) if(!skip[p]) {  
        int q = p*p;  
        if (ll(q)*q > N) break;  
        skip[p] = true;  
        for(int i=q; i<=v; i+=2*p) skip[i] = true;  
        int ns=0;  
        for(int k=0; k<s; ++k) {  
            int i = roughs[k];  
            if(skip[i]) continue;  
            ll d = ll(i) * p;  
            larges[ns] = larges[k] - (d<=v ? larges[smalls[d>>1]-pc] : smalls[half(divide(N, d))]) + pc;  
            roughs[ns++] = i;  
        }  
        s = ns;  
        for(int i=half(v), j=((v/p)-1)|1; j>=p; j-=2) {  
            int c = smalls[j>>1]-pc;  
            for(int e=(j*p)>>1; i>=e; --i) smalls[i] -= c;  
        }  
        ++pc;  
    }  
    larges[0] += ll(s+2*(pc-1))*(s-1)/2;  
    for(int k=1; k<s; ++k) larges[0] -= larges[k];  
    for(int l=1; l<s; ++l) {  
        int q = roughs[l];  
        ll M = N/q;  
        int e = smalls[half(M / q)]-pc;  
        if(e<l+1) break;  
        ll t = 0;  
        for(int k = l + 1; k <= e; ++k) t += smalls[half(divide(M, roughs[k]))];  
        larges[0] += t-ll(e-l)*(pc+l-1);  
    }  
    return larges[0]+1;  
}  
  
int main() {  
    ll t;  
    cin >> t;  
    REP(i, t) {  
        ll n;  
        cin >> n;  
        ll pair = (n - prime_count(n) + prime_count(n/2) - 1) / 2;  
        cout << n-pair << "\n";  
    }  
  
    return 0;  
}

2020-05-02

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers

codeforces

問題ページ

トンネルが連結なパターンを2通りに分ける

並行な場合
隣接している4パターンのみ考えられる。mapかsetで存在するトンネルを保持しておけばこの判定はできる。
垂直な場合
x軸に垂直なトンネルとy軸に垂直なトンネルが連結となるのはz座標の差が1以下であるときのみである。x軸に垂直でz座標がzのトンネルとx軸に垂直でz座標がz-1,z,zのトンネルを連結にする。連結なトンネルについてすべての集合を持つ必要はないので、トンネルの集合を圧縮する。これをすべてのzについて行う。垂直な方向が違う場合についても対称に同様に計算できる。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
struct UnionFind {  
    vector<ll> par, s;  
    UnionFind(ll n) : par(n), s(n, 1) { iota(ALL(par), 0); }  
    ll find(ll x) {  
        if(par[x] == x) return x;  
        return par[x] = find(par[x]);  
    }  
    void unite(ll x, ll y) {  
        x = find(x), y = find(y);  
        if(x == y) return;  
        if(s[x] < s[y]) par[x] = y, s[y] += s[x];  
        else par[y] = x, s[x] += s[y];  
    }  
    bool same(int x, int y) { return find(x) == find(y); }  
    ll size(int x) { return s[find(x)]; }  
};  
  
void solve() {  
    ll n;  
    cin >> n;  
    vector<ll> x(n), y(n), z(n);  
    map<tuple<ll,ll,ll>, ll> mp;  
    REP(i, n) {  
        cin >> x[i] >> y[i] >> z[i];  
        mp[{x[i], y[i], z[i]}] = i;  
    }  
  
    // 並行で連結な分をつなぐ  
    UnionFind uf(n);  
    REP(i, n) {  
        if(x[i]==-1) {  
            if(mp.find({-1, y[i]-1, z[i]}) != mp.end()) uf.unite(i, mp[{-1, y[i]-1, z[i]}]);  
            if(mp.find({-1, y[i]+1, z[i]}) != mp.end()) uf.unite(i, mp[{-1, y[i]+1, z[i]}]);  
            if(mp.find({-1, y[i], z[i]-1}) != mp.end()) uf.unite(i, mp[{-1, y[i], z[i]-1}]);  
            if(mp.find({-1, y[i], z[i]+1}) != mp.end()) uf.unite(i, mp[{-1, y[i], z[i]+1}]);  
        } else if(y[i]==-1) {  
            if(mp.find({x[i]-1, -1, z[i]}) != mp.end()) uf.unite(i, mp[{x[i]-1, -1, z[i]}]);  
            if(mp.find({x[i]+1, -1, z[i]}) != mp.end()) uf.unite(i, mp[{x[i]+1, -1, z[i]}]);  
            if(mp.find({x[i], -1, z[i]-1}) != mp.end()) uf.unite(i, mp[{x[i], -1, z[i]-1}]);  
            if(mp.find({x[i], -1, z[i]+1}) != mp.end()) uf.unite(i, mp[{x[i], -1, z[i]+1}]);  
        } else {  
            if(mp.find({x[i]-1, y[i], -1}) != mp.end()) uf.unite(i, mp[{x[i]-1, y[i], -1}]);  
            if(mp.find({x[i]+1, y[i], -1}) != mp.end()) uf.unite(i, mp[{x[i]+1, y[i], -1}]);  
            if(mp.find({x[i], y[i]-1, -1}) != mp.end()) uf.unite(i, mp[{x[i], y[i]-1, -1}]);  
            if(mp.find({x[i], y[i]+1, -1}) != mp.end()) uf.unite(i, mp[{x[i], y[i]+1, -1}]);  
        }  
    }  
  
    // 垂直で連結な分をつなぐ  
    {  
        vector<ll> vx, vy, vz;  
        REP(i, n) {  
            if(x[i]==-1) vx.push_back(i);  
            else if(y[i]==-1) vy.push_back(i);  
            else vz.push_back(i);  
        }  
  
        map<ll,vector<ll>> xz, yz, xy, zy, yx, zx;  
        for(auto i: vx) xz[z[i]].push_back(i);  
        for(auto i: vy) yz[z[i]].push_back(i);  
        for(auto i: vx) xy[y[i]].push_back(i);  
        for(auto i: vz) zy[y[i]].push_back(i);  
        for(auto i: vy) yx[x[i]].push_back(i);   
        for(auto i: vz) zx[x[i]].push_back(i);  
  
        auto unite = [&](vector<ll> &a, vector<ll> &b) {  
            if(a.size() && b.size()) {  
                for(auto i: b) uf.unite(a[0], i);  
                for(auto i: a) uf.unite(i, b[0]);  
                a = {uf.find(a[0])};  
                b = {uf.find(b[0])};  
            }  
        };  
  
        // (-1, ya, za) (xb, -1, zb)  
        for(auto i: vx) {  
            if(yz.find(z[i]-1) != yz.end()) unite(xz[z[i]], yz[z[i]-1]);  
            if(yz.find(z[i]) != yz.end()) unite(xz[z[i]], yz[z[i]]);  
            if(yz.find(z[i]+1) != yz.end()) unite(xz[z[i]], yz[z[i]+1]);  
        }  
        // (-1, ya, za) (xb, yb, -1)  
        for(auto i: vx) {  
            if(zy.find(y[i]-1) != zy.end()) unite(xy[y[i]], zy[y[i]-1]);  
            if(zy.find(y[i]) != zy.end()) unite(xy[y[i]], zy[y[i]]);  
            if(zy.find(y[i]+1) != zy.end()) unite(xy[y[i]], zy[y[i]+1]);  
        }  
        // (xa, -1, za) (xb, yb, -1)  
        for(auto i: vy) {  
            if(zx.find(x[i]-1) != zx.end()) unite(yx[x[i]], zx[x[i]-1]);  
            if(zx.find(x[i]) != zx.end()) unite(yx[x[i]], zx[x[i]]);  
            if(zx.find(x[i]+1) != zx.end()) unite(yx[x[i]], zx[x[i]+1]);  
        }  
    }  
  
    map<PII,ll> xy, xz, yz;  
    REP(i, n) {  
        if(x[i]==-1) yz[{y[i], z[i]}] = i;  
        else if(y[i]==-1) xz[{x[i], z[i]}] = i;  
        else xy[{x[i], y[i]}] = i;  
    }  
  
    ll q;  
    cin >> q;  
    REP(i, q) {  
        ll sx, sy, sz, gx, gy, gz;  
        cin >> sx >> sy >> sz >> gx >> gy >> gz;  
  
        ll vs = -1;  
        if(yz.find({sy, sz}) != yz.end()) vs = yz[{sy, sz}];  
        if(xy.find({sx, sy}) != xy.end()) vs = xy[{sx, sy}];  
        if(xz.find({sx, sz}) != xz.end()) vs = xz[{sx, sz}];  
  
        ll vg = -1;  
        if(yz.find({gy, gz}) != yz.end()) vg = yz[{gy, gz}];  
        if(xy.find({gx, gy}) != xy.end()) vg = xy[{gx, gy}];  
        if(xz.find({gx, gz}) != xz.end()) vg = xz[{gx, gz}];  
  
        if(vs!=-1 && vg!=-1 && uf.same(vs, vg)) cout << "YES\n";  
        else cout << "NO\n";  
    }  
}  
  
int main() {  
    ll test;  
    cin >> test;  
    REP(i, test) solve();  
  
    return 0;  
}

2020-05-02

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest F問題 The Halfwitters

codeforces

問題ページ

概要

$n$ 要素の順列が与えられる
以下の操作を繰り返して順列を昇順に並べる

隣接要素のswap： $a$ 分かかる
順列のreverse： $b$ 分かかる
ランダムシャッフル： $c$ 分かかる

初期状態が $d$ 個与えられるのでそれぞれについて、最適に操作したときにかかる時間の期待値を求めろ
出力は分数で行うこと

$n \leq 16$ 、 $a,b,c \leq 1000$ 、 $d \leq 10000$
複数テストケースで $\sum{d} \leq 10^5$

解法

隣接swapとreverseのみを使って順列を昇順に並べるときにかかる時間は転倒数を用いて計算することができる。 $\text{dp}_{\text{inv}} = ($ 転倒数が $\text{inv}$ のときにかかる時間 $)$ とすると、 $\text{dp}_{\text{inv}} = \min(a \times \text{inv}, (n(n-1)/2-a) \times \text{inv} + b)$ となる。

ランダムな順列を整列するのにかかる時間の期待値を $X$ とすると、転倒数が $\text{inv}$ のときの答えは $\text{ans}_{\text{inv}} = \min(\text{dp}_{\text{inv}}, X+c)$ となる。あとは $X$ を求められればよい。 $\text{cnt}_{i} = ($ 転倒数が $i$ となる順列の個数 $)$ とすると、 $X = \sum_{\text{inv}} \text{cnt}_{\text{inv}} * \text{ans}_{\text{inv}}$ となる。 $\text{ans}_{\text{inv}}$ のうち、 $X+c$ になるものと $\text{dp}_{\text{inv}}$ になるものがそれぞれ何かがわかれば $X$ が求められる。

$\text{dp}$ をソートしておくと、ある $j$ について $\text{ans}_{i} = \text{dp}_{i}\ (i \leq j)$ 、 $\text{ans}_{i} = X+c\ (i \geq j+1)$ となる。 $\displaystyle S = \sum_{l=0}^j \text{cnt}_l \cdot \text{dp}_l$ で $\displaystyle M = \sum_{l=j+1}^k \text{cnt}_l$ とする。ただし、 $\text{cnt}$ は $\text{dp}$ のソートに合わせて並べ替えておくものとする。このとき $X \cdot n! = S + M \cdot (X+c)$ であるから、 $X$ を計算することができる。

$j$ を一旦決め打って $X$ を計算し、 $j$ に関する制約を満たすのであれば、そのときの $X$ が正しい値である。

$\text{cnt}$ に関してはDPで計算することができる。 $A \lbrack i \rbrack \lbrack j \rbrack =($ 長さ $i$ で転倒数 $j$ の順列の個数 $)$ とすると、遷移は $A \lbrack i \rbrack \lbrack j \rbrack += A \lbrack i-1 \rbrack \lbrack j-k \rbrack \ (0 \leq k \lt i)$ となる。

計算量について

まず最初に $\text{cnt}$ をDPで計算しておく。これは $O(n^4)$ でできる。

各テストケースについて $\text{dp}$ を計算する。転倒数は高々 $n(n-1)/2$ なので $O(n^2)$ でできる。固定した各 $j$ について $X$ の計算は $O(1)$ でできるので $X$ は $O(n^2)$ でできる。よってテストケース数を $T$ とすると、この部分の計算量は $O(Tn^2)$ である。

与えられた順列について $O(n^2)$ で転倒数を求めることで答えを計算できる。この部分の計算量は $O((\sum d)\cdot n^2)$ である。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
// 分数ライブラリ  
// 常に約分されているとする  
// 負のときは常にaを負にする  
struct fraction {  
    ll a, b;  
    fraction(ll x=0, ll y=1) : a(x), b(y) {  
        ll g = __gcd(a, b);  
        a /= g, b /= g;  
        if(b < 0) a *= -1, b *= -1;  
    }  
    // comparator  
    bool operator<(fraction r) const { return a*r.b < b*r.a; }  
    bool operator>(fraction r) const { return a*r.b > b*r.a; }  
    bool operator<=(fraction r) const { return a*r.b <= b*r.a; }  
    bool operator>=(fraction r) const { return a*r.b >= b*r.a; }  
    bool operator==(fraction r) const { return a*r.b == b*r.a; }  
    bool operator!=(fraction r) const { return a*r.b != b*r.a; }  
    // Basic Operations  
    fraction operator+(fraction r) const { return fraction(*this) += r; }  
    fraction operator-(fraction r) const { return fraction(*this) -= r; }  
    fraction operator*(fraction r) const { return fraction(*this) *= r; }  
    fraction operator/(fraction r) const { return fraction(*this) /= r; }  
    fraction &operator+=(fraction r) {  
        ll g = __gcd(abs(a*r.b+b*r.a), b*r.b);  
        ll na = (a*r.b+b*r.a)/g, nb = (b*r.b)/g;  
        a = na, b = nb;  
        return *this;  
    }  
    fraction &operator-=(fraction r) {  
        ll g = __gcd(abs(a*r.b-b*r.a), b*r.b);  
        ll na = (a*r.b-b*r.a)/g, nb = (b*r.b)/g;  
        a = na, b = nb;  
        return *this;  
    }  
    fraction &operator*=(fraction r) {  
        ll g1 = __gcd(a, r.a), g2 = __gcd(b, r.b);  
        a = a/g1*r.a, b = b/g2*r.b;  
        return *this;  
    }  
    fraction &operator/=(fraction r) {  
        ll g1 = __gcd(a, r.b), g2 = __gcd(b, r.a);  
        a = a/g1*r.b, b = b/g2*r.a;  
        if(b < 0) a *= -1, b *= -1;  
        return *this;  
    }  
    friend fraction abs(fraction a) {  
        a.a = abs(a.a);  
        return a;  
    }  
    // output  
    friend ostream &operator<<(ostream& os, fraction a) {  
        return os << a.a << "/" << a.b;  
    }  
};  
  
int main() {  
    // cnt[i][j] = (長さiで転倒数がjの順列の個数)  
    vector<vector<ll>> cnt(17);  
    FOR(i, 1, 17) {  
        cnt[i].resize(i*(i-1)/2+1);  
        if(i==1) {  
            cnt[i][0] = 1;  
            continue;  
        }  
  
        REP(j, i*(i-1)/2+1) REP(k, i) {  
            if(0<=j-k && j-k<=(i-1)*(i-2)/2) {  
                cnt[i][j] += cnt[i-1][j-k];  
            }  
        }  
    }  
  
    vector<ll> fact(17);  
    fact[0] = 1;  
    FOR(i, 1, 17) fact[i] = fact[i-1] * i;  
  
    auto solve = [&] {  
        ll n, a, b, c, d;  
        cin >> n >> a >> b >> c >> d;  
  
        // dp[i] = (転倒数がiの順列を隣接swap,reverseで並べる時間)  
        vector<ll> dp(n*(n-1)/2+1);  
        REP(i, n*(n-1)/2+1) dp[i] = min(a*i, a*(n*(n-1)/2-i) + b);  
  
        // x = (randomな順列から整列するのにかかる時間の期待値)  
        auto calc = [&] {  
            vector<PII> sdp(n*(n-1)/2+1);  
            REP(i, n*(n-1)/2+1) sdp[i] = PII(dp[i], i);  
            sort(ALL(sdp));  
            vector<ll> scnt(n*(n-1)/2+1);  
            REP(i, n*(n-1)/2+1) scnt[i] = cnt[n][sdp[i].second];  
  
            ll s = 0, m = 0;  
            REP(i, n*(n-1)/2+1) m += scnt[i];  
            fraction tx(s+m*c, fact[n]-m);  
            if(sdp[0].first*tx.b >= tx.a+c*tx.b) return tx;  
            REP(i, n*(n-1)/2+1) {  
                s += scnt[i] * sdp[i].first;  
                m -= scnt[i];  
  
                fraction tx(s+m*c, fact[n]-m);  
                bool cond1 = sdp[i].first*tx.b <= tx.a+c*tx.b;  
                bool cond2 = i+1>n*(n-1)/2 || sdp[i+1].first*tx.b >= tx.a+c*tx.b;   
                if(cond1 && cond2) return tx;  
            }  
            assert(false);  
        };  
        fraction x = calc();  
  
        // ans[i] = (転倒数がiのときの答え)  
        vector<fraction> ans(n*(n-1)/2+1);  
        REP(i, n*(n-1)/2+1) {  
            if(dp[i]*x.b < x.a + c*x.b) ans[i] = fraction(dp[i], 1);  
            else ans[i] = x + fraction(c, 1);  
        }  
  
        REP(i, d) {  
            vector<ll> p(n);  
            REP(j, n) cin >> p[j], p[j]--;  
  
            ll inv = 0;  
            REP(j, n) REP(k, j) if(p[k] > p[j]) inv++;  
            cout << ans[inv] << "\n";  
        }  
    };  
  
    ll test;  
    cin >> test;  
    REP(i, test) solve();  
  
    return 0;  
}

2020-05-02

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination

codeforces

問題ページ

概要

$n$ 個の円(中心が $(c_x,c_y)$ で半径 $r$ ) が存在
$q$ 個のクエリが与えられる
2点 $(p_x,p_y),(q_x,q_y)$ を以下の条件を満たしつつ行き来できるか？

円の内部を通らない
$y_{\min}\leq y \leq y_{\max}$ となる範囲のみ

$n,q \leq 10^6$
円は重ならない

解法

$p_x \leq q_x$ と仮定しても一般性を失わない。クエリが'NO'となる条件は「 $p_x \leq c_x \leq q_x$ かつ $y_{\min} \leq c_y-r \leq c_y+r \leq y_{\max}$ となる円が存在する」ことである。

この判定は平面走査でできる。 $y=\text{const}$ のときに $\text{seg} \lbrack i \rbrack = (x=i$ を含む円の上端 $)$ となるようにセグ木を保持して管理する。 $\text{const}$ を小さい方から動かしていく。このときセグ木を更新するタイミングは以下の3パターンである。

円の下端
$\text{seg} \lbrack c_x \rbrack = c_y+r$ と更新
円の上端
$\text{seg} \lbrack c_x \rbrack = -\infty$ と更新
$y_{\min}$ に達したタイミング
区間 $\lbrack p_x, q_x \rbrack$ の $\max \geq y_{\max}$ であれば'NO'

したがって $O( (q+n)\log(q+n) )$ で解けた。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
// 根が1  
template<typename Monoid>  
struct segtree {  
    using T = typename Monoid::T;  
    int n;  
    vector<T> dat;  
  
    segtree(int n_) {  
        n = 1;  
        while(n < n_) n <<= 1;  
        dat.assign(n*2, Monoid::id());  
    }  
    void build(vector<T> v) {  
        REP(i, v.size()) dat[i+n] = v[i];  
        for(int i=n-1; i>0; --i) dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
    }  
  
    T query(int a, int b) {  
        if(a >= b) return Monoid::id();  
        T l = Monoid::id(), r = Monoid::id();  
        for(a+=n, b+=n; a<b; a>>=1, b>>=1) {  
            if(a&1) l = Monoid::op(l, dat[a++]);  
            if(b&1) r = Monoid::op(dat[--b], r);  
        }  
        return Monoid::op(l, r);  
    }  
    void update(int i, T v) {  
        i += n;  
        dat[i] = v;  
        while(i >>= 1) {  
            dat[i] = Monoid::op(dat[i*2], dat[i*2+1]);  
        }  
    }  
  
    friend ostream &operator <<(ostream& out,const segtree<Monoid>& seg){  
        out << "---------------------" << endl;  
        int cnt = 1;  
        for(int i=1; i<=seg.n; i*=2) {  
            REP(j, i) {  
                out << seg.dat[cnt] << " ";  
                cnt++;  
            }  
            out << endl;  
        }  
        out << "---------------------" << endl;  
        return out;  
    }  
};  
  
template<typename Tp>  
struct max_monoid {  
    using T = Tp;  
    static constexpr Tp id() { return -INF; }  
    static Tp op(const Tp &a, const Tp &b) { return max(a, b); }  
};  
  
int main() {  
    ll n, q;  
    cin >> n >> q;  
    vector<PII> ord(q+2*n);  
    vector<ll> cx(n), cy(n), r(n);  
    REP(i, n) {  
        cin >> cx[i] >> cy[i] >> r[i];  
        ord[2*i] = {i, 0};  
        ord[2*i+1] = {i, 2};  
    }  
    vector<ll> px(q), py(q), qx(q), qy(q), ymin(q), ymax(q);  
    REP(i, q) {  
        cin >> px[i] >> py[i] >> qx[i] >> qy[i] >> ymin[i] >> ymax[i];  
        if(px[i] > qx[i]) swap(px[i], qx[i]), swap(py[i], qy[i]);  
        ord[2*n + i] = {i, 1};  
    }  
    sort(ALL(ord), [&](PII a, PII b){  
        ll vl, vr;  
        if(a.second == 1) vl = ymin[a.first];  
        else if(a.second == 0) vl = cy[a.first] - r[a.first];  
        else if(a.second == 2) vl = cy[a.first] + r[a.first];  
        if(b.second == 1) vr = ymin[b.first];  
        else if(b.second == 0) vr = cy[b.first] - r[b.first];  
        else if(b.second == 2) vr = cy[b.first] + r[b.first];  
        return PII(vl, a.second) < PII(vr, b.second);  
    });  
  
    vector<ll> vs(2*q+n);  
    REP(i, q) vs[2*i] = px[i], vs[2*i+1] = qx[i];  
    REP(i, n) vs[2*q+i] = cx[i];  
    sort(ALL(vs));  
    vs.erase(unique(ALL(vs)), vs.end());  
    REP(i, q) {  
        px[i] = lower_bound(ALL(vs), px[i]) - vs.begin();  
        qx[i] = lower_bound(ALL(vs), qx[i]) - vs.begin();   
    }  
    REP(i, n) cx[i] = lower_bound(ALL(vs), cx[i]) - vs.begin();  
  
    vector<bool> ans(q, true);  
    segtree<max_monoid<ll>> seg(vs.size());  
    seg.build(vector<ll>(vs.size(), -INF));  
    for(auto [i, type]: ord) {  
        if(type == 1) {  
            if(ymax[i] <= seg.query(px[i], qx[i]+1)) ans[i] = false;  
        } else if(type == 0) {  
            seg.update(cx[i], cy[i]+r[i]);  
        } else if(type == 2) {  
            seg.update(cx[i], -INF);  
        }  
    }  
  
    REP(i, q) cout << (ans[i] ? "YES" : "NO") << "\n";  
  
    return 0;  
}

2020-04-27

天下一プログラマーコンテスト2014予選B C - 天下一王国の歴史

AtCoder

問題ページ

まず答えの一番上の行を適当に定める。このとき入力の1~n-1行目までが正しく生成されるように、答えの2~n行目までを定めると一意に定まる。入力のn行目についても正しく生成されるような、一番上の行を探したい。 $O(2^n)$ 通りを全列挙することは不可能なので、一番上の行を変化させたときに、生成されるn行目がどのように変化するか考える。

$n=10$ のときに $(0,3)$ を変化させた場合に、答えのどこが変化するのかを以下に示す。規則的な変化になっている。

diff:  
    0123456789  
i=0 ...x......  
i=1 ..x.x.....  
i=2 .x.x.x....  
i=3 x.x.x.x...  
i=4 .x.x.x.x..  
i=5 ..x.x.x.x.  
i=6 ...x.x.x.x  
i=7 ....x.x.x.  
i=8 .....x.x..  
i=9 ......x...

ここで一番下の行に注目すると、隣接する変化しているマスの個数は必ず偶数個である。一番上の行をどのように変化させたとしても同様のことが示せ、 $n$ 行目は変化しないことがわかる。入力で与えられる文字列は必ず生成できる制約なので、一番上の行をどのように固定したとしても条件を満たす答えを得ることができる。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<string> v(n);  
    REP(i, n) cin >> v[i];  
  
    ll dx[] = {-1, 0, 1}, dy[] = {0, -1, 0};  
    auto f = [&](string s) {  
        vector<string> ret(n, string(n, '.'));  
        ret[0] = s;  
        FOR(i, 1, n) REP(j, n) {  
            ll cnt = 0;  
            REP(k, 3) {  
                ll ni = i-1+dy[k], nj = j+dx[k];  
                if(0<=ni && ni<n && 0<=nj && nj<n) {  
                    cnt += ret[ni][nj]=='#';  
                }  
            }  
            if(v[i-1][j]=='#') {  
                if(cnt%2==0) ret[i][j] = '#';  
            } else {  
                if(cnt%2) ret[i][j] = '#';  
            }  
        }  
        return ret;  
    };  
  
    auto ret = f(string(n, '.'));  
    REP(i, n) cout << ret[i] << "\n";  
  
    return 0;  
}

結構すき

2020-04-27

AtCoder Beginner Contest 164 F - I hate Matrix Construction

AtCoder

問題ページ

ビットごとに独立

ビットごとの論理和・論理積について考えているため、ビットごとに独立に考えることができる。したがって要素が0か1の $N \times N$ の行列を構築できるか？の問題に帰着できた。

容易に決定できる要素

まず、0か1か確定させられる要素を決めてしまおう。

論理積が1の行/列：全て1
論理和が0の行/列：全て0
$s_y=t_x$ であるような $(y,x)$ ： $s_y$

残りの要素

残りの決まっていない要素は「論理積が0」と「論理和が1」の制約からなる要素だけである。

試しにこれらの要素を全て0としてみる。このとき「論理積が0」という制約に反することはない。「論理和が1」が満たされない場合の対処を考える。そのような行(列)が存在する場合、「論理積が0」である列(行)のいずれかの要素を1にする必要がある。「論理積が0」である列(行)の要素を1にしたときに、その列(行)の要素が全て1にならないのであれば、1にしても問題がない。この条件を満たす列(行)を探し、1に変更する処理を「論理和が1」が満たされない全ての行(列)に対して行う。

行列の存在性

この処理を行った結果の行列が制約を満たさないならば、答えは-1である。結果が条件を満たさない場合、矛盾するパターンは2通り存在する。いずれの場合でも行列が存在することはありえない。

「容易に決定できる要素」の分で矛盾
「論理積が1」から1にしたいが「論理和が0」から0にする必要があるので不可能である。

	or 0	or 0
and 1	無理	無理

「残りの要素」の分で矛盾
0→1に変更する要素が足りないので「論理和が1」の制約を修正することは不可能である。

実装に関して

$a_{i,j} \lt 2^{64}$ より要素はunsigned long long intで管理する必要がある。また1<<iではなく1ULL<<iとしなければいけない。

#include <bits/stdc++.h>  
using namespace std;  
using ll = unsigned long long int;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1ULL<<60;  
  
int main() {  
    ll n;  
    cin >> n;  
    // 0 → and, 1 → or  
    vector<ll> s(n), t(n), u(n), v(n);  
    REP(i, n) cin >> s[i];  
    REP(i, n) cin >> t[i];  
    REP(i, n) cin >> u[i];  
    REP(i, n) cin >> v[i];  
  
    vector<vector<ll>> ans(n, vector<ll>(n));  
    REP(i, 64) {  
        // u2[j] = u[j]のiビット目  
        vector<ll> u2(n), v2(n);  
        REP(j, n) u2[j] = !!(u[j]&1ULL<<i), v2[j] = !!(v[j]&1ULL<<i);  
          
        // 確定させられる要素の分を決定  
        vector<vector<ll>> used(n, vector<ll>(n));  
        REP(j, n) if(s[j]==0 && u2[j]==1) REP(k, n) used[j][k] = 1;  
        REP(j, n) if(t[j]==0 && v2[j]==1) REP(k, n) used[k][j] = 1;  
        REP(j, n) REP(k, n) if(u2[j] == v2[k]) used[j][k] = u2[j];  
  
        // 論理和が1の行の制約を満たせるように  
        {  
            vector<ll> zeros(n);  
            REP(j, n) REP(k, n) zeros[k] += (used[j][k]==0);  
            REP(j, n) if(s[j]==1 && u2[j]==1) {  
                bool exist = false;  
                REP(k, n) if(used[j][k]==1) exist = true;  
                if(exist) continue;  
                // 制約違反の行がある  
                //「論理積が0」で1に変更しても0が残っている列を探す  
                REP(k, n) if(t[k]==0 && v2[k]==0 && zeros[k]>=2) {  
                    zeros[k]--;  
                    used[j][k] = 1;  
                    break;  
                }  
            }  
        }  
        // 論理和が1の列の制約を満たすように  
        {  
            vector<ll> zeros(n);  
            REP(j, n) REP(k, n) zeros[j] += (used[j][k]==0);  
            REP(j, n) if(t[j]==1 && v2[j]==1) {  
                bool exist = false;  
                REP(k, n) if(used[k][j]==1) exist = true;  
                if(exist) continue;  
                REP(k, n) if(s[k]==0 && u2[k]==0 && zeros[k]>=2) {  
                    zeros[k]--;  
                    used[k][j] = 1;  
                    break;  
                }  
            }  
        }  
          
        REP(j, n) REP(k, n) ans[j][k] |= used[j][k]<<i;  
    }  
  
    // 実際に構成した行列が制約を満たすか確認  
    auto check = [&] {  
        REP(i, n) {   
            ll and1 = ans[i][0], or1 = 0, and2 = ans[0][i], or2 = 0;  
            REP(j, n) {  
                and1 &= ans[i][j];  
                or1  |= ans[i][j];  
                and2 &= ans[j][i];  
                or2  |= ans[j][i];  
            }  
            if(s[i]==0 && u[i]!=and1) return false;  
            if(s[i]==1 && u[i]!=or1) return false;  
            if(t[i]==0 && v[i]!=and2) return false;  
            if(t[i]==1 && v[i]!=or2) return false;  
        }  
        return true;  
    };  
    if(!check()) {  
        cout << -1 << endl;  
        return 0;  
    }  
  
    REP(i, n) REP(j, n) cout << ans[i][j] << (j==n-1?'\n':' ');  
  
    return 0;  
}

2020-04-26

Code Formula 2014 本選 E - ab文字列

AtCoder

問題ページ

文字列の長さは $n$ についてフィボナッチ数列になっている。したがって $n$ については一意に定まる。また、フィボナッチ数列で20000以下となるのは22番目までなので、 $n \leq 22$ である。文字列は高々 $2^{20}$ 個程度しか存在しないので、 $F_{n,k}\ (0 \leq k \lt 2^{n-2} \leq 2^{20})$ を全列挙し、 $S$ と一致するか判定すればよい。

普通に文字列の一致判定に $O(|S|)$ かけているとTLEするのでハッシュを用いて高速化する。ローリングハッシュの要領でハッシュ関数を定めると、文字列 $sl, sr$ を連結した文字列の $sl+sr$ のハッシュは高速に求められる。 $f(n,k)$ の値をメモ化再帰で計算していくことで $O(n2^n)$ で $F_{n,k}$ のハッシュを求められる。

MLには注意

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
struct dice {  
    mt19937 mt;  
    dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}  
    ll operator()(ll x) { return this->operator()(0, x - 1); }  
    ll operator()(ll x, ll y) {  
        uniform_int_distribution<ll> dist(x, y);  
        return dist(mt);  
    }  
} rnd;  
  
class rollingHash {  
private:  
    static constexpr ll mod = (1LL<<61) - 1;  
    const ll base;  
    vector<ll> hash, p;  
  
    ll mul(ll a, ll b) {  
        ll au = a>>31, ad = a & ((1LL<<31)-1);  
        ll bu = b>>31, bd = b & ((1LL<<31)-1);  
        ll mid = ad*bu+au*bd, midu = mid>>30, midd = mid & ((1LL<<30)-1);  
        return au*bu*2 + midu + (midd<<31) + ad*bd;  
    }  
    ll calcmod(ll x) {  
        ll ret = (x>>61) + (x & mod);  
        if(ret >= mod) ret -= mod;  
        return ret;  
    }  
  
public:  
    rollingHash(const string &s) : base(rnd(2, 100000)), hash(s.size()+1), p(s.size()+1,1) {  
        REP(i, s.size()) {  
            hash[i+1] = calcmod(mul(hash[i], base)+s[i]);  
            p[i+1] = calcmod(mul(p[i], base));  
        }  
    }  
    // [l,r)  
    ll get(int l,int r) {  
        return calcmod(hash[r] + 3*mod - mul(hash[l], p[r-l]));  
    }  
    ll concat(ll h1, ll h2, ll h2len) {  
        return calcmod(mul(h1, p[h2len]) + h2);  
    }  
};  
  
int main() {  
    string s;  
    cin >> s;  
      
    if(s.size()==1) {  
        if(s=="a") cout << "2 0\n";  
        else cout << "1 0\n";  
        return 0;  
    }  
  
    rollingHash hash(s);  
    ll ha = -1, hb = -1;  
    REP(i, s.size()) {  
        if(s[i]=='a') ha = hash.get(i, i+1);  
        else if(s[i]=='b') hb = hash.get(i, i+1);  
    }  
    ll hs = hash.get(0, s.size());  
  
    // fib[i] = (f_{ij}の長さ)  
    vector<ll> fib({0, 1, 1, 2});  
    {  
        ll a = 1, b = 1, c = 2;  
        while(c < (ll)s.size()) {  
            a = b;  
            b = c;  
            c = a+b;  
            fib.push_back(c);  
        }  
    }  
    ll n = fib.size()-1;  
  
    vector<vector<ll>> memo(n+1);  
    FOR(i, 3, n+1) memo[i].assign(1LL<<(i-2), -1);  
    auto dfs = [&](auto &&self, ll x, ll y) -> ll {  
        if(x==1) return hb;  
        if(x==2) return ha;  
        if(memo[x][y] != -1) return memo[x][y];  
        if(y%2==0) {  
            auto vl = self(self, x-1, y/2);  
            auto vr = self(self, x-2, y/4);  
            return memo[x][y] = hash.concat(vl, vr, fib[x-2]);  
        } else {  
            auto vl = self(self, x-2, y/4);  
            auto vr = self(self, x-1, y/2);  
            return memo[x][y] = hash.concat(vl, vr, fib[x-1]);  
        }  
    };  
  
    REP(i, 1LL<<(n-2)) if(dfs(dfs, n, i) == hs) {  
        cout << n << " " << i << "\n";  
        return 0;  
    }  
  
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies

概要

解法

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest F問題 The Halfwitters

概要

解法

計算量について

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination

概要

解法

天下一プログラマーコンテスト2014予選B C - 天下一王国の歴史

AtCoder Beginner Contest 164 F - I hate Matrix Construction

ビットごとに独立

容易に決定できる要素

残りの要素

行列の存在性

実装に関して

Code Formula 2014 本選 E - ab文字列