ferinの競プロ帳

競プロについてのメモ

チーム練習 (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;  
}