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

問題ページ

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

終点からdijkstra

頂点からまでで最悪な位置で寝た場合の最短時間 とする。辺 について 辺重み 辺重み 路線の終点までの時間 路線の終点からTまでの時間 となる。 からスタートしてdijkstra法のように最小のものから順に確定させていけばよい。

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

辺 で に移動するとき、 から までは最短の移動時間とするのが最善である。よって、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;  
}  

自分の誤答

頂点からまで移動する場合に最悪な位置で寝たパターン, からの移動時間 というペアを持つことにする。辺 について 寝過ごした場合の分 辺重み のペア と更新する。

dijkstra法のように行っても、これでは最適解を求めることはできない。辺 を移動する場合、 が最小のものが最適とは限らない。…らしいんだけどどういうケースなのか思いつかなかったのでランダム生成した。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法を行うときはちゃんと条件を確認する必要がある

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

ARC052 D - 9

問題ページ

と表す。 は下から 桁目の値であり、 である。 となるような を求めたい。

の組は 通り存在するため、普通に全列挙するとTLEしてしまう。そこで半分全列挙を行う。 と についてそれぞれ和を列挙する。足したときに で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;  
  
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;  
}  

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

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

問題ページ

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

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

番目の箱が潰されるときのデータ構造の変化について考える。 番目の箱より小さい最大の箱を 、 番目の箱より大きい最小の箱を と表すことにする。、 をRBSTから消去し、 を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;  
}  

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

問題ページ

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

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

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

線分を偏角の区間に置き換えるところについて、誤差の処理だったりが結構大変
偏角 かつ 始点の偏角終点の偏角 かつ 終点の偏角始点の偏角 となるようにしておく。こうしても一般性を失わないし、頭が壊れにくくなる。始点の偏角 から 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;  
}  

チーム練習 (05/07)

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

マス を操作するなら を1、操作しないなら0にする
各マスを 'B','W' のどちらにするかで式が立てられる
mod 2 で に隣接する の和が0か1になるような式

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

F

多角形の面積を求める

G

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

H

漸化式について となるような が存在する
start, periodについて前計算をして埋め込みを行うことで で計算可能

前計算を行う際に 個のメモリをもつのは厳しいが、フロイドの循環検出法などを使うと space でいける

ソースコード

#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

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

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

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

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

同じwet zoneに隣接している && 連結 であるようなfirm groundの集合を考える
異なる集合同士については独立に解くことが可能
集合ごとにgrundy数を求めたい
集合の要素数は高々 なので で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;  
}  

AtCoder Regular Contest 037 D - Chaotic Polygons

問題ページ

レベルが のときの答え、レベルが のときに2点を結ぶ方法、レベルが のときに同じ点を2回通るパターンを各レベルについて計算していく。それぞれ と表す。

各三角形内で完結するパターン + 三角形をまたぐパターン
三角形を2つ使うパターン + 三角形を3つ使うパターン

#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;  
  
template<ll MOD>  
struct modint {  
    ll x;  
    modint(): x(0) {}  
    modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}  
    static constexpr ll mod() { return MOD; }  
    // e乗  
    modint pow(ll e) {  
        ll a = 1, p = x;  
        while(e > 0) {  
            if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}  
            else {a = (a*p) % MOD; e--;}  
        }  
        return modint(a);  
    }  
    modint inv() const {  
        ll a=x, b=MOD, u=1, y=1, v=0, z=0;  
        while(a) {  
            ll q = b/a;  
            swap(z -= q*u, u);  
            swap(y -= q*v, v);  
            swap(b -= q*a, a);  
        }  
        return z;  
    }  
    // Comparators  
    bool operator <(modint b) { return x < b.x; }  
    bool operator >(modint b) { return x > b.x; }  
    bool operator<=(modint b) { return x <= b.x; }  
    bool operator>=(modint b) { return x >= b.x; }  
    bool operator!=(modint b) { return x != b.x; }  
    bool operator==(modint b) { return x == b.x; }  
    // Basic Operations  
    modint operator+(modint r) const { return modint(*this) += r; }  
    modint operator-(modint r) const { return modint(*this) -= r; }  
    modint operator*(modint r) const { return modint(*this) *= r; }  
    modint operator/(modint r) const { return modint(*this) /= r; }  
    modint &operator+=(modint r) {  
        if((x += r.x) >= MOD) x -= MOD;  
        return *this;  
    }  
    modint &operator-=(modint r) {  
        if((x -= r.x) < 0) x += MOD;  
        return *this;  
    }  
    modint &operator*=(modint r) {  
    #if !defined(_WIN32) || defined(_WIN64)  
        x = (ll)x * r.x % MOD; return *this;  
    #endif  
        unsigned long long y = (unsigned long long)x * r.x;  
        unsigned xh = (unsigned) (y >> 32), xl = (unsigned) y, d, m;  
        asm(  
            "divl %4; \n\t"  
            : "=a" (d), "=d" (m)  
            : "d" (xh), "a" (xl), "r" (MOD)  
        );  
        x = m;  
        return *this;  
    }  
    modint &operator/=(modint r) { return *this *= r.inv(); }  
    // increment, decrement  
    modint operator++() { x++; return *this; }  
    modint operator++(signed) { modint t = *this; x++; return t; }  
    modint operator--() { x--; return *this; }  
    modint operator--(signed) { modint t = *this; x--; return t; }  
    // 平方剰余のうち一つを返す なければ-1  
    friend modint sqrt(modint a) {  
        if(a == 0) return 0;  
        ll q = MOD-1, s = 0;  
        while((q&1)==0) q>>=1, s++;  
        modint z=2;  
        while(1) {  
            if(z.pow((MOD-1)/2) == MOD-1) break;  
            z++;  
        }  
        modint c = z.pow(q), r = a.pow((q+1)/2), t = a.pow(q);  
        ll m = s;  
        while(t.x>1) {  
            modint tp=t;  
            ll k=-1;  
            FOR(i, 1, m) {  
                tp *= tp;  
                if(tp == 1) { k=i; break; }  
            }  
            if(k==-1) return -1;  
            modint cp=c;  
            REP(i, m-k-1) cp *= cp;  
            c = cp*cp, t = c*t, r = cp*r, m = k;  
        }  
        return r.x;  
    }  
  
    template<class T>  
    friend modint operator*(T l, modint r) { return modint(l) *= r; }  
    template<class T>  
    friend modint operator+(T l, modint r) { return modint(l) += r; }  
    template<class T>  
    friend modint operator-(T l, modint r) { return modint(l) -= r; }  
    template<class T>  
    friend modint operator/(T l, modint r) { return modint(l) /= r; }  
    template<class T>  
    friend bool operator==(T l, modint r) { return modint(l) == r; }  
    template<class T>  
    friend bool operator!=(T l, modint r) { return modint(l) != r; }  
    // Input/Output  
    friend ostream &operator<<(ostream& os, modint a) { return os << a.x; }  
    friend istream &operator>>(istream& is, modint &a) {   
        is >> a.x;  
        a.x = ((a.x%MOD)+MOD)%MOD;  
        return is;  
    }  
    friend string to_frac(modint v) {  
        static map<ll, PII> mp;  
        if(mp.empty()) {  
            mp[0] = mp[MOD] = {0, 1};  
            FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {  
                mp[(modint(i) / j).x] = {i, j};  
            }  
        }  
        auto itr = mp.lower_bound(v.x);  
        if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr;  
        string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first));  
        if(itr->second.second > 1) {  
            ret += '/';  
            ret += to_string(itr->second.second);  
        }  
        return ret;  
    }  
};  
using mint = modint<1000000007>;  
  
int main() {  
    ll l;  
    cin >> l;  
  
    struct state { mint r1, r2, r3; };  
    auto dfs = [&](auto &&self, ll v) -> state {  
        if(v == 0) {  
            state ret({1, 2, 1});  
            // dump(v, ret);  
            return ret;  
        }  
        state st = self(self, v-1);  
        state ret({  
            3 * st.r1 + st.r2*st.r2*st.r2,  
            st.r2*st.r2 + st.r2*st.r2*st.r2 - st.r3*st.r2*st.r3,  
            st.r2*st.r3*st.r2 - st.r3*st.r3*st.r3  
        });  
        // dump(v, ret);  
        return ret;  
    };   
  
    cout << dfs(dfs, l).r1 << endl;  
  
    return 0;  
}  

チーム練習 (04/29)

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest をやった。本番51位相当、参加者のレベル帯めっちゃ高くないか

(開始) 手分けして読む。L,Bが解かれているので考える。
(0:22) Lは貪欲でいいことがわかるのでolpheが書きはじめる。
(0:25) Lが通る。
(0:39) Bは高速ゼータ変換でいいことにdivくんが気づいて書く。
(0:59) Iが貪欲にできる限り大きいものから取っていいことにolpheが気づいて書き始める。
(1:37) Gについて色々考えた結果、マッチング全探索して2点間を直接線分で結ぶと一つは解が存在するに反例が見つからなかったので書くことになった。
(1:55) Gを出すとn<=6なのにMLE(？？？) 未定義を踏んでないか確認したけどなさそう。なんかやばそうなバグらせかたをしていそうなので実装をolpheにかわる。二人がHの考察を詰めてて、実装できる段階になった。
(2:29) Gが通る。divくんがHの実装をはじめる。Eを考えるけどつらそうなのでFを考える。隣接swapとreverseだけで揃える場合は転倒数で計算できそうなので、シャッフルをする場合の期待値を求めたい。頑張ればできそうな気もするけど遷移がよくわからない。
(3:09) Hが通る。Jを考える。
(3:37) Jは状態をうまくもってUFでつないで管理するとできるっぽいのでolpheが実装を始める。EJあたりを考えたけど通らなくて終了。

解説を読むとEが誤読だったことが判明 マジでごめん
Jは連結にするべきパターンが少し抜けてたらしい
cin高速化を複数回実行していたのを1回になるようにしたらGのMLEが取れた。標準入出力のあとにcin高速化のいつもの関数を呼ぶのは処理系定義らしく、気をつけた方がよさそう。
Gはもうちょっと早く実装に入ってもよかったかなあ

A 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies - ferinの競プロ帳
E 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination - ferinの競プロ帳
F 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest F問題 The Halfwitters - ferinの競プロ帳
J 2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers - ferinの競プロ帳

C 解説のの条件を消せると書いてある部分がよくわからない