2020-05-13

Codeforces Round #641 (Div. 1) A. Orac and LCM

codeforces

gcdを求めたいので素因数ごとに独立に考えて、最後に掛け合わせても問題ない。

例えば数列が $(2^0, 2^1, 2^2, 2^3)$ であったとする。このときのlcmの集合は

$\text{lcm}(2^0, 2^1) = 2^{\max(0, 1)}$
$\text{lcm}(2^0, 2^2) = 2^{\max(0, 2)}$
$\text{lcm}(2^0, 2^3) = 2^{\max(0, 3)}$
$\text{lcm}(2^1, 2^2) = 2^{\max(1, 2)}$
$\text{lcm}(2^2, 2^3) = 2^{\max(2, 3)}$

となる。このときの $\gcd$ は $2^{\max(0, 1)}$ となる。このように指数が小さい方から2番目の値のものが $\gcd$ の指数となる。

あとは素因数ごとに指数が小さい方から2番目のものを列挙していく。指数が0のものもすべて列挙すると $O(n \times ($ 素数の個数 $))$ かかってしまうので、各数の素因数のみを参照するように工夫する。

$\text{num} \lbrack i \rbrack = ($ 素因数 $i$ を約数にもつ数の個数 $)$ 、 $\text{mi} \lbrack i \rbrack = ($ 素因数 $i$ の指数の最小 $)$ 、 $\text{mi2} \lbrack i \rbrack = ($ 素因数 $i$ の指数の小さい方から2番目 $)$ とした配列を持つ。数 $A_i$ の素因数分解を行い、現れた素因数についてこれらの配列の更新を行う。これは $O(\sqrt{A_i})$ でできる。

配列を構成した後、 $\text{num} \lbrack i \rbrack = n$ であれば $i^{\text{mi2} \lbrack i \rbrack }$ を答えに掛け、 $\text{num} \lbrack i \rbrack = n-1$ であれば $i^{\text{mi} \lbrack i \rbrack }$ (最小の指数は0なので)を答えに掛ける。 $\text{num} \lbrack i \rbrack \leq n-2$ のときは2番目から小さい方の指数は0なので何もしなくても問題ない。

▶ソースコード(クリックで展開)

#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;  
  
ll modpow(ll x, ll y) {  
    ll a = 1, p = x;  
    while(y > 0) {  
        if(y%2 == 0) {p = (p*p); y /= 2;}  
        else {a = (a*p); y--;}  
    }  
    return a;  
}  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    if(n == 2) {  
        cout << lcm(a[0], a[1]) << endl;  
        return 0;  
    }  
  
    vector<ll> num(200001), mi(200001, INF), mi2(200001, INF);  
    REP(i, n) {  
        ll t = a[i];  
        for(ll j=2; j*j<=t; j++) {  
            ll cnt = 0;  
            while(t%j == 0) {  
                cnt++;  
                t /= j;  
            }  
            num[j]++;  
            if(mi[j] > cnt) {  
                mi2[j] = mi[j];  
                mi[j] = cnt;  
            } else if(mi2[j] > cnt) {  
                mi2[j] = cnt;  
            }  
        }  
        if(t > 1) {  
            num[t]++;  
            if(mi[t] > 1) {  
                mi2[t] = mi[t];  
                mi[t] = 1;  
            } else if(mi2[t] > 1) {  
                mi2[t] = 1;  
            }  
        }  
    }  
  
    ll ans = 1;  
    FOR(i, 2, 200001) {  
        if(num[i] == n-1) ans *= modpow(i, mi[i]);  
        else if(num[i] == n) ans *= modpow(i, mi2[i]);  
    }  
    cout << ans << endl;  
  
    return 0;  
}

$\text{num} \lbrack i \rbrack = n-1$ のときに $i^{\text{mi2} \lbrack i \rbrack }$ を掛けてシステス落とした…

2020-05-11

ダブリング

この間のABCで話題になってたのでダブリングについてちょっと考えたことのメモ
コードは適当なので雰囲気です

$x:=f(x,y)$ を繰り返す

関数 $f: T \times T \to T$ が存在
$x,y \in T$ について $x := f(x,y)$ を $K$ 回実行
これは $O((f$ の計算量 $) \times \log K)$ で計算可能

繰り返し二乗法などが具体例としてあげられる

template<class T, class F>  
T binpow(T y, ll k, F f, T x) {  
    T ret = x, p = y;  
    while(k > 0) {  
        if(k%2 == 0) {p = f(p, p); k /= 2;}  
        else {ret = f(ret, p); k--;}  
    }  
    return ret;  
};  
  
int main() {  
    // 10^100 mod 1e9+7  
    binpow(10, 100, [](ll a, ll b){ return a*b%1000000007; }, 1);  
}

行列累乗や置換の積を繰り返すような処理も f, x を変更することで対応可能

int main() {  
    // 行列累乗  
    {  
        const ll n = 3; // 行列の次数  
        using mind = modint<1000000007>;  // modintの実装は省略します  
        auto mul = [&](vector<vector<mint>> a, vector<vector<mint>> b) {  
            vector<vector<mint>> c(n, vector<mint>(n));  
            REP(i, n) REP(j, n) REP(k, n) c[i][j] += a[i][k] * b[k][j];  
            return c;  
        };  
        vector<vector<mint>> a = {  
            {1, 2, 3},  
            {4, 5, 6},  
            {7, 8, 9}  
        }, d = {   // 単位行列  
            {1, 0, 0},  
            {0, 1, 0},  
            {0, 0, 1}  
        };  
        // a^10  
        binpow(a, 10, mul, d);  
    }  
  
    // 置換の積  
    {  
        const ll n = 3; // 置換の要素数  
        auto mul = [](vector<ll> a, vector<ll> b) {  
            vector<ll> ret(a.size());  
            REP(i, a.size()) ret[i] = b[a[i]];  
            return ret;  
        };  
        // (0, 2, 1) を 10回適用  
        binpow({0, 2, 1}, 10, mul, {0, 1, 2});  
    }  
}

このあいだのABCのD - Teleporterを置換の積と思うと、これで解ける
Submission #13117116 - AtCoder Beginner Contest 167

例題1
例題2

$x:=f(x)$ を繰り返す

$x \in T$ に関数 $f:T \to T$ を $K$ 回適用したときの値を計算する

$N=|T|$ と表す
$f(x)\ (x \in T)$ を $O(g)$ で計算可能なとき、前計算が $O(gN + N \log N)$ で可能
各クエリ $O(\log K)$ で計算可能

前計算

前計算では $\text{next} \lbrack k \rbrack \lbrack i \rbrack = (i$ 番目の要素の $2^k$ 個次の要素 $)$ を計算する
まず、 $\text{next} \lbrack 0 \rbrack \lbrack i \rbrack = g(x_i)$ で初期化する。 $k \gt =1$ に関しては $\text{next} \lbrack k \rbrack \lbrack i \rbrack = \text{next} \lbrack k-1 \rbrack \lbrack \text{next} \lbrack k-1 \rbrack \lbrack i \rbrack \rbrack$ と計算可能

クエリ

$x \in T$ に関数 $f:T \to T$ を $K$ 回適用したい
もし K&1<<i であったら $x = \text{next} \lbrack i \rbrack \lbrack x \rbrack$ として更新する

実装例

template<ll LOG=60>  
struct doubling {  
    // nxt[i][j] = (j番目の要素に関数fを2^i回適用した要素は何番目の要素か)  
    vector<vector<ll>> nxt;   
    doubling(vector<ll> nxt0) : nxt(LOG, vector<ll>(nxt0.size())) {  
        REP(i, nxt0.size()) nxt[0][i] = nxt0[i];  
        FOR(k, 1, LOG) REP(j, nxt0.size()) nxt[k][j] = nxt[k-1][nxt[k-1][j]];  
    }  
    // x番目の要素に関数fをk回適用した要素は何番目の要素か？  
    ll query(ll x, ll k) {  
        for(ll i=LOG-1; i>=0; --i) if(k&1LL<<i) x = nxt[i][x];  
        return x;  
    }  
};

この間のABCのD - Teleporterの場合、 $f(x) = a \lbrack x \rbrack$ とすればよい
Submission #13117497 - AtCoder Beginner Contest 167

合計・最小などの求解

前計算のタイミングで $2^k$ 回適用したところまでの合計、最小を求めておけばよい

試しに合計で考える
$\text{sum} \lbrack i \rbrack \lbrack j \rbrack = (j$ に $\lbrack 0, 2^i)$ 回適用した値の合計 $)$
$\text{sum} \lbrack i \rbrack \lbrack j \rbrack$ → $(j$ に $\lbrack 0,2^i)$ 回 $)$ → $(j$ に $\lbrack 0,2^{i-1})$ 回適用 $) + (\text{next} \lbrack i-1 \rbrack \lbrack j \rbrack$ に $\lbrack 0, 2^{i-1})$ 回適用 $)$
より小さい $i$ の情報を用いて計算できるので、 $i$ が小さい方から計算していける

二分探索

単調性があるなら二分探索できる

$x_i \leq x_{i+1}, x \leq f(x)$ みたいな単調性があるとする
$x$ から $y$ 以上に移動するのに必要な関数適用の回数の最小
$\text{next} \lbrack k \rbrack \lbrack a \rbrack \leq b$ が成り立つなら $ret += 2^k, a := \text{next} \lbrack k \rbrack \lbrack a \rbrack$ を $k$ が大きい方から実行すればよい

(実装例) Submission #13117640 - AtCoder Regular Contest 060

ダブリングで木のLCAを求めるのも同じ感じ

雑感
なんか一般化できないかなあと思って考えてたけど $f(x), f(x,y)$ のやつ同じように扱うの難しそう
$f(x,y)$ の方だと $n$ が大きくてもいける
$f(x)$ の方だとクエリに高速に答えられる

2020-05-10

第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

AtCoder

問題ページ

経路を一つ固定したとき、寝過ごしたときに最悪となるパターンについて考える。辺 $(u,v)$ で寝過ごした場合、かかる時間は (始点からuまでの時間) + (uから終点までの時間) + (終点からtまでの時間) となる。経路上の各辺で寝過ごした場合の時間のmaxが最悪となるパターンである。この時間が最小となるような経路を求める問題である。

終点からdijkstra

$\text{dist} \lbrack v \rbrack = ($ 頂点 $v$ から $t$ までで最悪な位置で寝た場合の最短時間 $)$ とする。辺 $(u,v)$ について $\text{dist} \lbrack u \rbrack = \max($ 辺重み $+ \text{dist} \lbrack v \rbrack ,$ 辺重み $+$ 路線の終点までの時間 $+$ 路線の終点からTまでの時間 $)$ となる。 $\text{dist} \lbrack t \rbrack =0$ からスタートしてdijkstra法のように最小のものから順に確定させていけばよい。

これが通常の最短距離を求めるdijkstra法と同様に最適解が求められることを確認する。最短経路問題では辺 $(u,v)$ を使用する場合、始点から $u$ までは最短距離で移動するのが最善である(負辺がないなら)。したがって、最短距離が確定した頂点から隣接した頂点に移動するパターンについて更新すればよい。

辺 $(u,v)$ で $v \to u$ に移動するとき、 $t$ から $v$ までは最短の移動時間とするのが最善である。よって、dijkstra法の要領で最短が確定した頂点から順に確定させていくことで最適解を得ることができる。

▶ソースコード(クリックで展開)

#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, m, s, t;  
    cin >> n >> m >> s >> t;  
    struct edge { ll to, cost, ep, cost_ep; };  
    vector<vector<edge>> g(n), rg(n);  
    REP(i, m) {  
        ll l;  
        cin >> l;  
        vector<ll> v(l), w(l-1);  
        REP(i, l) cin >> v[i];       
        REP(i, l-1) cin >> w[i];  
        vector<ll> rui(w);  
        FOR(i, 1, l-1) rui[i] += rui[i-1];  
        FOR(i, 1, l) {  
            // w[i-1…l-2]  
            ll s0 = (l-2<0?0:rui[l-2]) - (i-2<0?0:rui[i-2]);  
            // w[0…i-1]  
            ll s1 = (i-1<0?0:rui[i-1]);  
  
            g[v[i-1]].push_back({v[i], w[i-1], v[l-1], s0});  
            rg[v[i-1]].push_back({v[i], w[i-1], v[0], s1});  
            g[v[i]].push_back({v[i-1], w[i-1], v[0], s1});  
            rg[v[i]].push_back({v[i-1], w[i-1], v[l-1], s0});  
        }  
    }  
  
    vector<ll> dist_t(n, INF);  
    {  
        priority_queue<PII, vector<PII>, greater<PII>> que;  
        que.push({0, t});  
        dist_t[t] = 0;  
        while(que.size()) {  
            ll cost, vtx;  
            tie(cost, vtx) = que.top(); que.pop();  
            if(dist_t[vtx] < cost) continue;  
            for(auto e: g[vtx]) {  
                if(dist_t[e.to] > dist_t[vtx] + e.cost) {  
                    dist_t[e.to] = dist_t[vtx] + e.cost;  
                    que.push({dist_t[e.to], e.to});  
                }  
            }  
        }  
    }  
  
    vector<ll> dist(n, INF);  
    dist[t] = 0;  
    priority_queue<PII, vector<PII>, greater<PII>> que;  
    que.push({0, t});  
    while(que.size()) {  
        ll cost, vtx;  
        tie(cost, vtx) = que.top(); que.pop();  
        if(dist[vtx] < cost) continue;  
        for(auto e: rg[vtx]) {  
            ll nd = max(e.cost + dist[vtx], e.cost_ep + dist_t[e.ep]);  
            if(dist[e.to] > nd) {  
                dist[e.to] = nd;  
                que.push({nd, e.to});  
            }  
        }  
    }  
    cout << dist[s] << endl;  
  
    return 0;  
}

自分の誤答

$\text{dist} \lbrack v \rbrack = ($ 頂点 $s$ から $v$ まで移動する場合に最悪な位置で寝たパターン, $s$ から $v$ の移動時間 $)$ というペアを持つことにする。辺 $(u,v)$ について $\text{chmin}(\text{dist} \lbrack v \rbrack , (\max(\text{dist} \lbrack u \rbrack .\text{first}, \text{dist} \lbrack u \rbrack .\text{second} +$ 寝過ごした場合の分 $), \text{dist} \lbrack u \rbrack .\text{second} +$ 辺重み $)$ のペア $)$ と更新する。

dijkstra法のように行っても、これでは最適解を求めることはできない。辺 $u,v$ を移動する場合、 $\text{dist} \lbrack u \rbrack$ が最小のものが最適とは限らない。…らしいんだけどどういうケースなのか思いつかなかったのでランダム生成した。20頂点10路線で始点が0で終点が19のケースになっている。

▶ランダム生成で試してたら落ちたやつ

20 10 0 19  
9  
3 7 17 15 5 6 19 11 10   
51 94 44 58 9 8 78 11   
9  
6 13 10 5 7 19 11 17 14   
70 73 39 99 28 62 75 84   
18  
19 11 18 1 15 0 7 3 16 12 17 6 2 13 5 14 4 8   
37 44 96 27 98 97 52 57 78 81 10 57 26 23 43 73 57   
8  
4 6 9 1 13 0 7 12   
36 1 89 4 94 38 51   
6  
10 11 3 6 8 9   
7 9 70 35 46   
4  
11 6 1 0   
11 92 14   
8  
16 13 19 15 11 14 4 5   
77 95 39 83 79 71 56   
13  
10 8 11 7 14 6 9 0 17 1 2 4 5   
41 7 20 72 67 36 29 51 22 14 60 49   
17  
1 8 11 13 17 0 15 7 2 9 16 10 12 6 5 3 19   
72 61 86 44 72 35 54 10 35 52 88 23 97 54 23 60   
3  
18 2 1   
94 84

このケースで正しいのは0→7→11→19という経路で0→7で眠る場合の138となる
誤答の方は0→7→3→19という経路の149を出力する
0→7→11 とくる場合のdist[11]は(138,58)であるが、0→1→6→11 とくる場合のdist[11]は(136,117)でこちらの方が小さいため、0→7→11の方の経路は使用されない
ペアの辞書順で最小のものが常に正しいわけではないのでこのアルゴリズムはおかしい

dijkstra法を行うときはちゃんと条件を確認する必要がある

最短が確定した頂点から移動するような経路が必ず最適になるように実行
ちゃんと全順序になっていること

2020-05-10

ARC052 D - 9

AtCoder

問題ページ

$\displaystyle N=\sum_{i=0}^{10} 10^i \times a_i$ と表す。 $a_i$ は下から $i$ 桁目の値であり、 $0 \leq a_i \leq 9$ である。 $\displaystyle \sum_{i=0}^{10} (10^i-1) \times a_i \equiv 0\ (\text{mod}\ K)$ となるような $a_i\ (0 \leq i \leq 10)$ を求めたい。

$a_i$ の組は $10^{10}$ 通り存在するため、普通に全列挙するとTLEしてしまう。そこで半分全列挙を行う。 $0 \leq i \leq 4$ と $5 \leq i \leq 10$ についてそれぞれ和を列挙する。足したときに $\text{mod } K$ で0になるようなものが何個あるのか求めればよい。

上限 $M$ の設定から $a_i$ を列挙するのが多少面倒になっているが、上位部分が $M$ と一致するか？の場合分けをすればよい。

▶ソースコード(クリックで展開)

#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 k, m;  
    cin >> k >> m;  
  
    auto calc = [&](ll n, bool islower) -> ll {  
        ll t = n, ret = 0, pw = (islower ? 1 : 100000%k);  
        REP(i, 5) {  
            ret += (t%10)*(pw-1)%k;  
            (pw *= 10) %= k;  
            t /= 10;  
        }  
        return (ret%k+k)%k;  
    };  
  
    ll ans = 0;  
    {  
        map<ll,ll> cnt;  
        REP(i, 100000) cnt[calc(i, true)]++;  
        REP(i, m/100000) {  
            ll val = calc(i, false);  
            ans += cnt[(k-val)%k];  
        }  
    }  
    {  
        map<ll,ll> cnt;  
        REP(i, m%100000+1) cnt[calc(i, true)]++;  
        ans += cnt[(k-calc(m/100000, false))%k];  
    }  
    cout << ans-1 << endl;  
  
    return 0;  
}

半分全列挙見えなかった…
数字和と元の数字の一致、 $B$ 進数のときに $\text{mod}\ B-1$ するくらいしか性質を知らない(なんかあるのかな？)ので、これでだめなら全探索ベースで考えるとかした方がいいのかも…？

2020-05-09

Donutsプロコンチャレンジ2015 D - ドーナツの箱詰め

AtCoder

問題ページ

まず $Q=0$ のときの解き方を考える。 $c_i$ についてソートしておく。この数列の差分について小さい方から $n-k$ 個の和が答えになる。差分が大きいところから $k-1$ 個と一番小さい箱にドーナツを入れることでこれは達成できる。

数列の小さい方から $x$ 個の和を求めるのにはセグ木、平衡二分探索木などのデータ構造を用いればよい。今回はRBSTを使う。

$d$ 番目の箱が潰されるときのデータ構造の変化について考える。 $d$ 番目の箱より小さい最大の箱を $\text{prev}(d)$ 、 $d$ 番目の箱より大きい最小の箱を $\text{next}(d)$ と表すことにする。 $a \lbrack d \rbrack -\text{prev}(d)$ 、 $\text{next}(d)-a \lbrack d \rbrack$ をRBSTから消去し、 $\text{next}(d)-\text{prev}(d)$ をRBSTに追加すればよい。prev, next については std::set で実現可能なのでこの問題は解けた。

▶ソースコード(クリックで展開)

#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;  
  
template<class M>  
struct RBST {  
    using T = typename M::T;  
    using E = typename M::E;  
  
    struct node {  
        node *l, *r, *p;  
        T val;  
        E lazy;  
        bool rev;  
        int sz;  
  
        node(T v, E p) : l(nullptr),r(nullptr),val(v),lazy(p),rev(false),sz(1) {}  
    };  
  
    int size(node* a) { return !a ? 0 : a->sz; }  
    T val(node* a) { return !a ? M::dt() : (eval(a), a->val); }  
    node* fix(node* a) {  
        a->sz = size(a->l) + 1 + size(a->r);  
        a->val = M::f(val(a->l), a->val, val(a->r));  
        return a;  
    }  
    void eval(node* a) {  
        if(a->lazy != M::de()) {  
            a->val = M::g(a->val, a->lazy, size(a));  
            if(a->l) a->l->lazy = M::h(a->l->lazy, a->lazy);  
            if(a->r) a->r->lazy = M::h(a->r->lazy, a->lazy);  
            a->lazy = M::de();  
        }  
        if(a->rev) {  
            swap(a->l, a->r);  
            if(a->l) a->l->rev ^= 1;  
            if(a->r) a->r->rev ^= 1;  
            a->rev = false;  
        }  
    }  
  
    inline int xor128() {  
        static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;  
        int t;  
        t = x ^ (x << 11); x = y; y = z; z = w;  
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));  
    }  
  
    node* merge(node *a, node *b) {  
        if(!a) return b;  
        if(!b) return a;  
        eval(a); eval(b);  
        if(xor128() % (size(a) + size(b)) < size(a)) {  
            a->r = merge(a->r, b);  
            if(a->r) a->r->p = a;  
            return fix(a);  
        } else {  
            b->l = merge(a, b->l);  
            if(b->l) b->l->p = b;  
            return fix(b);  
        }  
    }  
    // [0,k) [k,n)  
    pair<node*, node*> split(node *a, int k) {  
        if(!a) return pair<node*, node*>(nullptr, nullptr);  
        eval(a);  
        node *sl, *sr;  
        if(k <= size(a->l)) {  
            tie(sl, sr) = split(a->l, k);  
            if(a->l) a->l->p = nullptr;  
            a->l = sr;  
            if(a->l) a->l->p = a;  
            return pair<node*, node*>(sl, fix(a));  
        }  
        tie(sl, sr) = split(a->r, k - size(a->l) - 1);  
        if(a->r) a->r->p = nullptr;  
        a->r = sl;  
        if(a->r) a->r->p = a;  
        return pair<node*, node*>(fix(a), sr);  
    }  
    // 要素の挿入/削除  
    void insert(node*& a, int k, const T& x) {  
        node *sl, *sr;  
        tie(sl, sr) = split(a, k);  
        a = merge(sl, merge(new node(x, M::de()), sr));  
    }  
    T erase(node*& a, int k) {  
        node *sl, *sr, *tl, *tr;  
        tie(sl, sr) = split(a, k + 1);  
        tie(tl, tr) = split(sl, k);  
        a = merge(tl, sr);  
        return val(tr);  
    }  
    // 区間クエリ  
    T query(node*& a, int l, int r) {  
        node *sl, *sr, *tl, *tr;  
        tie(sl, sr) = split(a, r);  
        tie(tl, tr) = split(sl, l);  
        T res = !tr ? M::dt() : tr->val;  
        a = merge(merge(tl, tr), sr);  
        return res;  
    }  
    // x以上の最小の位置  
    int lower_bound(node *t, const T &x) {  
        if(!t) return 0;  
        if(x <= val(t)) return lower_bound(t->l, x);  
        return lower_bound(t->r, x) + size(t->l) + 1;  
    }  
    // xより大きい最小の位置  
    int upper_bound(node *t, const T &x) {  
        if(!t) return 0;  
        if(x < val(t)) return upper_bound(t->l, x);  
        return upper_bound(t->r, x) + size(t->l) + 1;  
    }  
    // xの個数  
    int count(node *t, const T &x) {  
        return upper_bound(t, x) - lower_bound(t, x);  
    }  
    // 要素xを追加する  
    void insert_key(node *&t, const T &x) {  
        insert(t, lower_bound(t, x), x);  
    }  
    // 要素xを消す  
    void erase_key(node *&t, const T &x) {  
        // if(!count(t, x)) return;  
        erase(t, lower_bound(t, x));  
    }  
    // デバッグ用  
    void debug(node* t) {  
        if(t == nullptr) return;  
        cerr << "{";  
        debug(t->l);  
        cerr << " " << t->val << " ";  
        debug(t->r);  
        cerr << "}";  
    }  
};  
  
struct update_sum {  
    using T = PII;  // (頂点の値, 部分木の総和)  
    using E = ll;  
    static T dt() { return PII(0, 0); }  
    static constexpr E de() { return 0; }  
    static T f(const T &l, const T &self, const T &r) {  
        return PII(self.first, l.second + self.first + r.second);  
    }  
    static T g(const T &a, const E &b, const int &sz) {  
        return b == de() ? a : PII(b, b);  
    }  
    static E h(const E &a, const E &b) {  
        return b == de() ? a : b;  
    }  
};  
  
int main(void) {  
    ll n, k;  
    cin >> n >> k;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
  
    set<PII> st;  
    REP(i, n) st.insert({a[i], i});  
  
    // 小さい方からx個の合計を求めたい  
    vector<ll> sa(a);  
    sort(ALL(sa));  
    RBST<update_sum> tree;  
    RBST<update_sum>::node *root = nullptr;  
    FOR(i, 1, n) {  
        ll diff = sa[i]-sa[i-1];  
        tree.insert_key(root, PII(diff, diff));  
    }  
  
    cout << tree.query(root, 0, n-k).second << endl;  
    ll q;  
    cin >> q;  
    REP(i, q) {  
        ll d;  
        cin >> d;  
        d--;  
  
        auto itr = st.find(PII(a[d], d));  
        PII pre, now, nxt;  
        if(itr != st.begin()) pre = *prev(itr);  
        now = *itr;  
        if(next(itr) != st.end()) nxt = *next(itr);  
  
        // treeからa[d]-pre(a[d]) と next(a[d])-a[d]を消す  
        if(itr != st.begin()) tree.erase_key(root, PII(now.first-pre.first, 0));  
        if(next(itr) != st.end()) tree.erase_key(root, PII(nxt.first-now.first, 0));  
        // treeにnext(a[d])-pre(a[d])を追加する  
        if(itr != st.begin() && next(itr) != st.end()) {  
            tree.insert_key(root, PII(nxt.first-pre.first, nxt.first-pre.first));  
        }  
        // stからPII(a[d], d)を消す  
        st.erase(PII(a[d], d));  
          
        cout << tree.query(root, 0, n-k-1-i).second << endl;  
    }  
  
    return 0;  
}

2020-05-09

天下一プログラマーコンテスト2014予選A D - EMLauncher

AtCoder

問題ページ

原点からの半直線を引くので関係があるのは始点と終点の偏角である。各線分を[始点の偏角、終点の偏角]の区間に置き換えると、「ある区間の集合が与えられる。任意の区間についていずれかの要素を含むような偏角の集合のうち、最小の要素のものを答えろ。」という問題に置き換えられる。

偏角は循環しているが、一旦単純化して循環していない単なる区間の列について考える。終点でソートしておく。このとき、一番最初の区間については終点を集合に追加するべきである。また、始点が一番最初の区間の終点より前にある区間についても条件を満たす。条件をまだ満たしていない区間のうち、一番最初の区間について同様の処理を行う。

このような循環する座標系においては始点を固定することで列に置き換えるのが常套手段で、この問題では始点となる区間を $O(N)$ 個試すことで循環している条件に対応することができる。

線分を偏角の区間に置き換えるところについて、誤差の処理だったりが結構大変
$($ 偏角 $) \gt 0$ かつ $($ 始点の偏角 $) \lt ($ 終点の偏角 $)$ かつ $($ 終点の偏角 $) - ($ 始点の偏角 $) \lt \pi$ となるようにしておく。こうしても一般性を失わないし、頭が壊れにくくなる。 $($ 始点の偏角 $)$ から eps を引き、 $($ 終点の偏角 $)$ に eps を足しておくといいっぽい。

#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;  
  
using R = long double;  
const R EPS = 1e-8;  
const R PI = atan(1)*4;  
  
inline int sgn(const R &r) { return (r>EPS) - (r<-EPS); }  
inline int sgn(const R &r1, const R &r2) { return sgn(r1-r2); }  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> sx(n), sy(n), gx(n), gy(n);  
    REP(i, n) cin >> sx[i] >> sy[i] >> gx[i] >> gy[i];  
  
    vector<pair<R,R>> v0(n);  
    REP(i, n) {  
        R sarg = atan2l(sy[i], sx[i]);  
        R garg = atan2l(gy[i], gx[i]);  
        if(sarg > garg) swap(sarg, garg);  
        if(garg-sarg > PI) swap(sarg, garg);  
        sarg -= EPS;  
        garg += EPS;  
        if(sarg < 0) sarg += 2*PI;  
        while(garg < sarg) garg += 2*PI;  
        v0[i] = {sarg, garg};  
    }  
    sort(ALL(v0));  
  
    ll ans = n;  
    REP(i, n) {  
        // 区間iの終点に対応する半直線を引く  
        // この半直線に交差しない区間を列挙する  
        R t = v0[i].second;  
        vector<pair<R,R>> v;  
        REP(j, n) {  
            bool cross1 = sgn(v0[j].first, t) <= 0 && sgn(t, v0[j].second) <= 0;  
            bool cross2 = sgn(v0[j].first, t+2*PI) <= 0 && sgn(t+2*PI, v0[j].second) <= 0;  
            if(cross1 || cross2) continue;   
            if(sgn(t, v0[j].first) < 0) v.emplace_back(v0[j].first, v0[j].second);  
            if(sgn(v0[j].second, t) < 0) v.emplace_back(v0[j].first+2*PI, v0[j].second+2*PI);  
        }  
  
        // 終点でソートして貪欲にとっていく  
        sort(ALL(v), [](PII l, PII r){  
            return PII(l.second, l.first) < PII(r.second, r.first);  
        });  
        ll ret = 1, x = 0;  
        for(; x<(ll)v.size();) {  
            ll hold = x;  
            for(; x<(ll)v.size() && sgn(v[x].first, v[hold].second) <= 0; ++x);  
            ret++;  
        }  
        chmin(ans, ret);  
    }  
    cout << ans << endl;  
  
    return 0;  
}

2020-05-08

チーム練習 (05/07)

codeforces

Dashboard - 2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20) - Codeforces
8完ペナ1044で本番9位相当

A

dp[頂点][距離] = コストでDP
dijkstraしなくていいのでlog落とせる

B,C

気づいたら通されてたので知らない

D

struct state {  
    ll val;  
    state* left, right;  
};  
deque<state> dq;

みたいなのをもってがんばる。そのままやるとTLEするのでハッシュ化する。

E

マス $(y,x)$ を操作するなら $A_{y,x}$ を1、操作しないなら0にする
各マスを 'B','W' のどちらにするかで式が立てられる
mod 2 で $(y,x)$ に隣接する $A_{ny,nx}$ の和が0か1になるような式

普通にgauss jordanするとTLEだが、行列が疎とか形が特殊とかでできるらしい
解けません

F

多角形の面積を求める

G

相対順序が入れ替わらないペアが存在
仲がよくないペア $(a,b)$ について、 $i$ 個目の $a$ より前に $b$ が何個あるか？を前計算
置ける中で小さいものから貪欲に置いていく

H

漸化式について $f_{i+p} = f_{i}\ (i \geq s)$ となるような $s,p$ が存在する
start, periodについて前計算をして埋め込みを行うことで $O(1)$ で計算可能

前計算を行う際に $2^{64}$ 個のメモリをもつのは厳しいが、フロイドの循環検出法などを使うと space $O(1)$ でいける

ソースコード

#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;  
  
const ll start = 350125310, period = 182129209, len = 500000;  
// 長すぎるので省略 pre_calcで計算したものを埋め込み  
ll v0[], v1[], x0[], x1[];  
  
// 初項s0でs_n=next(s_{n-1})となる数列  
// s_i = s_{i+period} (i>=start) となるようなstart, periodを探索  
// time: O(start+period) space: O(1)  
template<class F>  
PII floyd_cycle_find(const ll s0, F next) {  
    ll t = 0, h = 1, st = s0, sh = next(s0);  
    for(; st!=sh; t++, st=next(st), h+=2, sh=next(next(sh)));  
    ll start = 0;  
    sh = s0;   
    REP(i, h-t) sh = next(sh);  
    for(st=s0; st!=sh; ++start, st=next(st), sh=next(sh));  
    ll period = 1;  
    for(sh=next(st); st!=sh; ++period, sh=next(sh));  
      
    return make_pair(start, period);  
}  
  
/* 線形合同法などに使われるらしい  
const ll s0 = 1611516670;  
auto next = [](ll s) {   
    constexpr ll m = 1LL<<40;  
    return (s + (s>>20) + 12345) & (m-1);   
};  
auto [start, period] = floyd_cycle_find(s0, next);   
*/  
  
void pre_calc() {  
    const ll s0 = 1611516670;  
    auto next = [](ll s) {   
        constexpr ll m = 1LL<<40;  
        return (s + (s>>20) + 12345) & (m-1);   
    };  
    auto [start, period] = floyd_cycle_find(s0, next);  
  
    ll s = s0;  
    // O(len) ごとにまとめておくと、各クエリ O(len) かかるけど埋め込む長さを減らせる   
    constexpr ll len = 500000;    
    const ll start1 = (start+len-1)/len, period1 = (period+len-1)/len;  
    vector<ll> v0(start1), v1(period1), x0(start1), x1(period1);  
    REP(i, start) {  
        if(i%len == 0) x0[i/len] = s;  
        (v0[i/len] += (s%2==0));  
        s = next(s);    
    }  
    FOR(i, 1, start1) (v0[i] += v0[i-1]);  
    REP(i, period) {  
        if(i%len == 0) x1[i/len] = s;  
        (v1[i/len] += (s%2==0));  
        s = next(s);  
    }  
    FOR(i, 1, period1) (v1[i] += v1[i-1]);  
  
    cout << "ll v0[] = {";  
    REP(i, start1) cout << v0[i] << (i==start1-1 ? "};\nll x0[] = {" : ",");  
    REP(i, start1) cout << x0[i] << (i==start1-1 ? "};\nll v1[] = {" : ",");  
    REP(i, period1) cout << v1[i] << (i==period1-1 ? "};\nll x1[] = {" : ",");  
    REP(i, period1) cout << x1[i] << (i==period1-1 ? "};\n" : ",");  
}  
  
int main(void) {  
    // pre_calc();  
  
    ll n;  
    cin >> n;  
    n--;  
  
    if(n < 0) {  
        cout << 0 << endl;  
        return 0;  
    }  
  
    auto next = [](ll s) {   
        constexpr ll m = 1LL<<40;  
        return (s + (s>>20) + 12345) & (m-1);   
    };  
  
    ll ans = 0;  
    if(n < start) {  
        if(n/len >= 1) ans += v0[n/len-1];  
        ll s = x0[n/len];  
        REP(i, n%len+1) {  
            (ans += (s%2==0));  
            s = next(s);  
        }  
    } else {  
        // [0, start-1]  
        ans += v0[(start+len-1)/len - 1];  
        n -= start;  
        // [start, start+period*k-1]  
        (ans += n / period * v1[(period+len-1)/len - 1]);  
        n %= period;  
        // [start, start+n]  
        if(n/len >= 1) (ans += v1[n/len-1]);  
        ll s = x1[n/len];  
        REP(i, n%len+1) {  
            (ans += (s%2==0));  
            s = next(s);  
        }  
    }  
  
    cout << ans << endl;  
  
    return 0;  
}

I

気づいたら通ってた

J

最小の数字のみからできる二分木をつくり、残りの数字をその二分木の子孫で表現すると再帰的につくっていける
k頂点の二分木の数はカタラン数でわかる

K

Tに隣接 && Tに行く方法が1通りの頂点の列挙
辺の向きを逆にしたグラフでTから何通りかを求めたい
SCCしてDAGにしてDPする

L

$N \times N$ の2次元グリッド
firm ground, wet zone, protected zone の3タイプのマス
連結なwet zoneからなる集合をwet areaと呼ぶ
任意のwet areaについて以下の性質がある

グリッド上の左(右)から一番目のマスにwet zoneが存在
要素数 $2N$ 以下
異なるwet areaのマスは距離3以上離れている

2人でゲームをする
以下の制約にしたがってマスにカメラを置く
置けなくなったら負け

firm groundであること
wet zoneに隣接
protected zoneでないこと
同じマスにはカメラは1個まで
同じwet areaに属するカメラは隣接してはいけない

$N \leq 10$

同じwet zoneに隣接している && 連結であるようなfirm groundの集合を考える
異なる集合同士については独立に解くことが可能
集合ごとにgrundy数を求めたい
集合の要素数は高々 $2N$ なので $O(2^{2N})$ でdfsしてgrundy数を求めればよい

ソースコード

#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;  
   
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)]; }  
};  
   
int main(void) {  
    ll n;  
    cin >> n;  
    vector<string> s(n);  
    REP(i, n) cin >> s[i];  
   
    ll dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};  
    vector<vector<ll>> t(n, vector<ll>(n, -1));  
    {  
        auto dfs = [&](auto &&self, ll y, ll x, ll type) -> void {  
            t[y][x] = type;  
            REP(i, 4) {  
                ll ny = y + dy[i], nx = x + dx[i];  
                if(nx<0 || nx>=n || ny<0 || ny>=n) continue;  
                if(s[ny][nx]=='*' && t[ny][nx]==-1) self(self, ny, nx, type);  
            }  
        };  
        ll type = 0;  
        REP(i, n) REP(j, n) {  
            if(t[i][j] == -1 && s[i][j]=='*') {  
                dfs(dfs, i, j, type);  
                type++;  
            }  
        }  
    }  
   
    vector<pair<PII,ll>> p;  
    REP(i, n) REP(j, n) {  
        if(s[i][j] != '.') continue;  
        REP(k, 4) {  
            ll ny = i + dy[k], nx = j + dx[k];  
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;  
            if(s[ny][nx] == '*') {  
                p.push_back({{i, j}, t[ny][nx]});  
                break;  
            }  
        }  
    }  
   
    UnionFind uf(p.size());  
    FOR(i, 1, p.size()) {  
        if(p[i-1].second == p[i].second && p[i-1].first.first==p[i].first.first && abs(p[i-1].first.second-p[i].first.second)<=1) {  
            uf.unite(i-1, i);  
        }  
    }  
    vector<ll> ord(p.size());  
    iota(ALL(ord), 0);  
    sort(ALL(ord), [&](ll l, ll r){  
        return PII(p[l].first.second, p[l].first.first) < PII(p[r].first.second, p[r].first.first);  
    });  
    FOR(i0, 1, ord.size()) {  
        ll i = ord[i0], pre = ord[i0-1];  
        if(p[pre].second==p[i].second && p[pre].first.second==p[i].first.second && abs(p[pre].first.first-p[i].first.first)<=1) {  
            uf.unite(pre, i);  
        }  
    }  
   
    vector<vector<PII>> v(p.size());  
    REP(i, p.size()) v[uf.find(i)].push_back(p[i].first);  
   
    auto solve = [&](vector<PII> a) {  
        const ll m = a.size();  
        vector<ll> memo((1LL<<m), -1);  
        vector<vector<ll>> b(m);  
        auto dfs = [&](auto &&self, ll mask) -> ll {  
            if(memo[mask]!=-1) return memo[mask];  
            vector<bool> grundy(m+1);  
            REP(i, m) {  
                bool flag = true;  
                for(auto j: b[i]) if(mask&1LL<<j) { flag = false; break; }  
                if(flag) {  
                    ll ret = self(self, mask | 1LL<<i);  
                    grundy[ret] = true;  
                }  
            }  
            REP(i, m+1) if(!grundy[i]) {  
                return memo[mask] = i;  
            }  
            assert(false);  
        };  
        REP(i, m) {  
            b[i].push_back(i);  
            REP(j, m) {  
                if(i==j) continue;  
                if(a[i].first==a[j].first && abs(a[i].second-a[j].second)<=1) b[i].push_back(j);  
                if(a[i].second==a[j].second && abs(a[i].first-a[j].first)<=1) b[i].push_back(j);  
            }  
        }  
        ll ret = dfs(dfs, 0);  
        return ret;  
    };  
   
    ll g = 0;  
    for(auto i: v) if(i.size()) {  
        ll ret = solve(i);  
        g ^= ret;  
        dump(i, ret);  
    }  
   
    if(g == 0) cout << "Second";  
    else cout << "First";  
    cout << " player will win\n";  
   
    return 0;  
}

ferinの競プロ帳

競プロについてのメモ

Codeforces Round #641 (Div. 1) A. Orac and LCM

ダブリング

$x:=f(x,y)$ を繰り返す

$x:=f(x)$ を繰り返す

前計算

クエリ

合計・最小などの求解

二分探索

第2回ドワンゴからの挑戦状予選 C - メンテナンス明け

終点からdijkstra

自分の誤答

ARC052 D - 9

Donutsプロコンチャレンジ2015 D - ドーナツの箱詰め

天下一プログラマーコンテスト2014予選A D - EMLauncher

チーム練習 (05/07)

A

B,C

D

E

F

G

H

I

J

K

L