2019-05-13

CPSCO 2019

全部解いたので略解と感想メモ

Session1
A: 算数
B: 各文字の出現回数を数える
C: binom(32, 6) の全探索
D: 8*5^n-1
E: 各数は高々1回しか消されないのでsetとかで愚直に書いてもok
F: 最小値の最大化と言われたので二分探索を考える
満足度を決めると各果物を食べられる区間がわかる
区間でN日間を覆えるか？の判定を貪欲にする
G: dpの遷移を見る必要がある場所が少ないのでインラインDPをする
dpの遷移で区間minになるのでセグメント木でdpテーブルを持つとできる
H: 分割統治でl,m,rに制限をつけたやつを解くのを再帰的に繰り返す
mにずっと注目してたけどlに注目すると簡単になる

Session2
A: 算数
B: +したあとに*をする
C: +1/-1に置き換えたあと累積和取って大きい方からK個
D: ゲームなので実験すると両方奇数が条件
E: 木DPしてくださいと問題文が言っている
制約が二乗の木DPですと言っている
dp[部分木i][切った辺がj本] = 必要な操作回数をしようとするとできるのでする
F: 各マスのコインを取る方法はロボットを横に動かすか縦に動かすかの二通り
各マスがどちらに属するか二分割する && 縦/横で取れるマスに依存性がある
グラフをつくって最小カット問題に帰着する(燃やす埋める)
G: クラスカル法の要領で考える
任意のxで使う辺を予め全部つないでおく
コストが小さい辺から見ていき非連結 → その辺をつなぐ and xの辺の本数を少なくする
xの値がw[i]のときの定数の辺の重みと xの辺の本数が求められる

Session3
A: 文字列処理
B: 降順ソートして上からM個取る
C: s,tを2倍してimos
D: s[0]='R' && s[n-1]=='B' && 部分文字列にRB/GGがない → Yes
E: bitごとに独立で考えられる累積xorと0/1の数を持っておけばいい
区間xorの遅延セグ木貼ったらTLEしてつらい
F: P[i] = i は無視してあとで binom(n, a+b) を掛ければいい
あとは箱根駅伝のDP
G: 各アイドルについて賞金を増やしたときに目的関数が減少する量を考える
減少量は単調非減少なのでx_i=0から順番に見ていってもok
各アイドルについて減少量はX/Aを超えるタイミングで3通りしか取らない
3N通りの減少量を求めて大きい方から取る

Session4
A: 算数
B: 全探索
C: r[i]+D以下の人が何人いるか二分探索
D: 退屈さ決め打ち二分探索
E: ox/xoのどちらか
oxが交互の列に分割できる
先頭と末尾が同じ列ならox/xoのどちらかを優先すると取れる数が増える
取れる数が増える方を優先して貪欲に取る
F: 根を決めると残りの頂点をどのように子に分割するかが決められる
再帰的に構築

2019-04-30

Codeforces Round #556 (Div. 2) D. Three Religions

競技プログラミング Codeforces

問題ページ

解法

まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいのでdpをする。 $dp \lbrack i \rbrack\lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack =$ 文字列 $s$ の $i$ 番目までで(文字列1の $x$ 文字 && 文字列2の $y$ 文字 && 文字列3の $z$ 文字)をつくれるか? という愚直なdpがあるがこのままでは状態数が大きすぎてTLEする。dpの値がtrue/falseの2択になっているがここに情報を持たせる。 $dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack =$ 文字列 $s$ の何番目まででつくれるか? としたdpが可能である。dpの遷移は
$dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack = \min ($ 文字列 $s$ の $dp \lbrack x-1 \rbrack \lbrack y \rbrack \lbrack z \rbrack$ より後で文字列1の $x$ 文字目が現れる最初の位置, 文字列 $s$ の $dp \lbrack x \rbrack \lbrack y-1 \rbrack \lbrack z \rbrack$ より後で文字列2の $y$ 文字目が現れる最初の位置, 文字列 $s$ の $dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z-1 \rbrack$ より後で文字列3の $z$ 文字目が現れる最初の位置 $)$
となる。文字列 $s$ で $i$ 文字目以降で文字 $c$ が現れる最初の位置を前計算しておくことでこれらの遷移は $O(1)$ で計算できる。よってクエリが存在しない場合の計算量は $250^{3}$ 程度でできる。
クエリごとに毎回dpをしていたのでは $1000 \times 250^{3}$ かかってしまいTLEする。クエリで変化するのは文字列の末尾1文字だけである点に注目する。クエリによって文字列1の長さが変化したとする。このときdpの値が変動する場所は $dp \lbrack$ 文字列1の長さ $\rbrack \lbrack y \rbrack \lbrack z \rbrack$ だけであり $250^{2}$ 個しか変動しないことがわかる。その他の文字列の長さが変化したとしても同様に $250^{2}$ 個しか変動しないため $1000\times 250^{2}$ 程度の計算量で問題なく解けることがわかる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
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> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

ll dp[255][255][255], pos[100010][30];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    FOR(j, n-1, 100010) REP(i, 26) pos[j][i] = INF;
    for(ll i=n-1; i>=0; --i) {
        REP(j, 26) {
            if(j == s[i]-'a') pos[i][j] = i;
            else if(i<n-1) pos[i][j] = pos[i+1][j];
        }
    }

    REP(i, 255) REP(j, 255) REP(k, 255) dp[i][j][k] = INF;
    dp[0][0][0] = -1;

    vector<string> v(3);
    while(q--) {
        char type;
        cin >> type;
        if(type == '+') {
            ll idx;
            char c;
            cin >> idx >> c;
            idx--;
            v[idx] += c;
            ll a, b;
            if(idx == 0) a = 1, b = 2;
            else if(idx == 1) a = 0, b = 2;
            else if(idx == 2) a = 0, b = 1;
            REP(i, v[a].size()+1) REP(j, v[b].size()+1) {
                ll x=-1, y=-1, z=-1;
                if(idx == 0) x = v[0].size(), y = i, z = j;
                else if(idx == 1) x = i, y = v[1].size(), z = j;
                else if(idx == 2) x = i, y = j, z = v[2].size();

                if(x) {
                    ll tmp = dp[x-1][y][z]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[0][x-1]-'a']);
                }
                if(y) {
                    ll tmp = dp[x][y-1][z]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[1][y-1]-'a']);
                }
                if(z) {
                    ll tmp = dp[x][y][z-1]+1;
                    if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[2][z-1]-'a']);
                }
            }
        } else {
            ll idx;
            cin >> idx;
            idx--;

            if(idx == 0) {
                REP(i, v[1].size()+1) REP(j, v[2].size()+1) {
                    dp[v[0].size()][i][j] = INF;
                }
            } else if(idx == 1) {
                REP(i, v[0].size()+1) REP(j, v[2].size()+1) {
                    dp[i][v[1].size()][j] = INF;
                }
            } else if(idx == 2) {
                REP(i, v[0].size()+1) REP(j, v[1].size()+1) {
                    dp[i][j][v[2].size()] = INF;
                }
            }
            v[idx].pop_back();
        }

        if(dp[v[0].size()][v[1].size()][v[2].size()] < n) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

2019-04-29

GCJ 2019 R1B Fair Fight

競技プログラミング

問題ページ

解法

部分点は $O(N^{3})$ で取りうる区間を全探索すればよい。
満点では $O(N^{2})$ 個の区間を全部見ているのでは間に合わない。 $c \lbrack i \rbrack$ が最大になり、 $\max (d \lbrack i \rbrack)$ についても条件を満たすような区間がそれぞれ何個あるか？を各 $c \lbrack i \rbrack$ に対して求めることで答えを求める。この各区間に課される条件を3つに分割することで数えやすくする。
(1) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) = c \lbrack i \rbrack$ となるような最大の区間の $l,r$
(2) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) \leq c \lbrack i \rbrack + k$ となるような最大の区間 $l,r$
(3) $\max (c \lbrack l \rbrack, \ldots, c \lbrack r \rbrack) \lt c \lbrack i \rbrack - k$ となるような最大の区間 $l,r$

(1)~(3)のそれぞれについて最大の区間に内包される全ての区間についても条件を満たす。よって条件を満たす区間は $(i-l+1) \times (r-i+1)$ 個となる。また、(1)について同じ区間を複数回数えないようにするため区間の最大値が複数ある場合は最も左の $c \lbrack i \rbrack$ を選ぶとする。

答えは ((1)と(2)を両方を満たすような区間の数)-((1)と(3)の両方を満たすような区間の数) となる。よってこれらの区間の数を高速に求めることができればよい。(1)を満たすような区間が $l_1, r_1$ で(2)を満たすような区間が $l_2, r_2$ であるとき、これら両方を満たすような区間は $\max (l_1, l_2)$ から $\min (r_1, r_2)$ となる。したがって(1)~(3)を求めることができれば答えがわかる。

(1)の $l$ を求めることを考える。 $r=i$ として $\max (c \lbrack j \rbrack, \ldots, c \lbrack r \rbrack) = c \lbrack i \rbrack$ を満たすような最大の $j$ が求まればよい。これは区間の最大値が単調増加することから二分探索を使って求めることができる。sparse table等の $O(1)$ でRMQができるデータ構造を用いることで $O(N \log N)$ で各 $i$ について $l$ を求めることができる。その他の $l,r$ についても同様に二分探索を行うことで求めることができ $O(N \log N)$ で解くことができた。

(1)で重複して数えないようにするため $c \lbrack i \rbrack$ と $i$ のpairの区間minを求めるとした。(2)(3)の区間が空の場合に注意。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
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> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

template <typename S>
struct sparseTable {
    using T = typename S::T;
    int n;
    vector<int> log2;
    vector<vector<T>> t;

    sparseTable(int nn) {
        n = nn;
        log2.assign(n+1, 0);
        for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
        t = vector<vector<T>>(log2[n]+1, vector<T>(n));
    }
    void init(vector<T> v) {
        for(int i=0; i<n; ++i) t[0][i] = v[i];
        for(int j=1; j<=log2[n]; ++j) {
            int w = 1LL<<(j-1);
            for (int i = 0; i+(w<<1) <= n; ++i) {
                t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
            }
        }
    }
    // [l, r]
    T query(int l, int r) {
        int j = log2[r - l];
        return S::op(t[j][l], t[j][r-(1 << j)+1]);
    }
};

// 集合T、結合則・可換・冪等律が成り立つ二項演算op
struct maximum {
    using T = ll;
    static T op(const T& a, const T& b) { return max(a, b); }
};
struct maximum_P {
    using T = PII;
    static T op(const T& a, const T& b) { return max(a, b); }
};

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll test;
    cin >> test;
    REP(tes, test) {
        ll n, k;
        cin >> n >> k;
        vector<ll> c(n), d(n);
        REP(i, n) cin >> c[i];
        REP(i, n) cin >> d[i];

        vector<PII> cc(n);
        REP(i, n) cc[i] = {c[i], i};
        sparseTable<maximum_P> seg1(n);
        seg1.init(cc);

        sparseTable<maximum> seg2(n);
        seg2.init(d);

        ll ret = 0;
        REP(i, n) {
            // max(c[l],…,c[r]) = c[i] となるようなl,r
            ll l1, r1;
            ll lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg1.query(mid, i) <= cc[i]) ub = mid;
                else lb = mid;
            }
            l1 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg1.query(i, mid) <= cc[i]) lb = mid;
                else ub = mid;
            }
            r1 = lb;

            // max(d[l],…,d[r]) <= c[i]+k となるようなl,r
            if(d[i] > c[i]+k) continue;
            ll l2, r2;
            lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(mid, i) <= c[i]+k) ub = mid;
                else lb = mid;
            }
            l2 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(i, mid) <= c[i]+k) lb = mid;
                else ub = mid;
            }
            r2 = lb;

            // max(d[l],…,d[r]) < c[i]-k となるようなl,r
            ll l3, r3;
            lb=-1, ub=i;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(mid, i) < c[i]-k) ub = mid;
                else lb = mid;
            }
            l3 = ub;
            lb=i, ub=n;
            while(ub-lb>1) {
                ll mid = (lb+ub)/2;
                if(seg2.query(i, mid) < c[i]-k) lb = mid;
                else ub = mid;
            }
            r3 = lb;

            // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<=c[i]+k
            ll l = max(l1, l2), r = min(r1, r2);
            ret += (i-l+1) * (r-i+1);
            // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<c[i]-k
            if(d[i] < c[i]-k) {
                l = max(l1, l3), r = min(r1, r3);
                ret -= (i-l+1) * (r-i+1);
            }
        }

        cout << "Case #" << tes+1 << ": ";
        cout << ret << endl;
    }

    return 0;
}

2019-04-21

Tenka1 Programmer Contest 2019 E - Polynomial Divisors

AtCoder 競技プログラミング

問題ページ

解法

解説放送で言ってることを自分流に書いたもの
pを一つ固定してその素数が条件を満たすか判定することを考える。pで割り切れるか考えるので以降ではmod pで考える。任意のxに対してf(x)=0 mod pとなればよい。フェルマーの小定理よりx=x^pである。したがって
f(x)
= a[N]x^N + a[N-1]x^(N-1) + … + a[1]x + a[0]
= (a[p-1]+a[2p-2]+…)x^(p-1) + … + (a[2]+a[p+1]+…)x^2 + (a[1]+a[p]+…)x + a[0]
となる。多項式がどのようなxに対しても0になる⇔係数が全て0 であるから係数が全て0か判定することでpが条件を満たすか判定することができる。係数を足してpの倍数になっているかの判定をO(N)ですればよい。
あとはpの候補全てに対してこの判定を行えばよい。pの候補の数を絞ることで全ての候補に対して判定を行っても間に合うようにする。

p<=N
10^4以下の素数は大した個数がないので全ての素数に対して判定を行う
p>N
フェルマーの小定理を使って変形したようにx^iの係数が複数のaの和になることがない。よってaNがpの倍数でないと条件を満たすことはない。したがってpの候補となるのはa[n]の素因数のみであり大した個数ではないので全てに対して判定を行えばよい。a[n]<0の場合に注意

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
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> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n+1);
    REP(i, n+1) cin >> a[n-i];

    auto test = [&](ll p) {
        if(a[0]%p) return false;
        vector<ll> sum(p);
        FOR(i, 1, n+1) sum[i%(p-1)] += a[i];
        bool flag = true;
        REP(i, p) if(sum[i]%p != 0) flag = false;
        return flag;
    };

    vector<ll> ans;

    // P <= N
    vector<bool> prime(n+2, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            if(test(i)) ans.push_back(i);
            for (int j = 2 * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }

    // P > N
    ll t = abs(a[n]);
    vector<ll> div;
    for(ll i=2; i*i<=t; ++i) {
        if(t%i==0) div.push_back(i);
        while(t%i==0) t/=i;
    }
    if(t>1) div.push_back(t);
    for(auto i: div) {
        if(i <= n) continue;
        bool flag = true;
        REP(j, n+1) if(a[j]%i != 0) flag = false;
        if(flag) ans.push_back(i);
    }

    for(auto i: ans) cout << i << endl;

    return 0;
}

2019-04-20

Tenka1 Programmer Contest 2019 D - Three Colors

競技プログラミング AtCoder

問題ページ

考えたこと

部分和問題っぽくて貪欲は無理そうだし制約小さいしまあDP
dp[i番目まで][R=j][G=j] みたいなDPを考える
R,G,Bは90000くらいまで取りうるのでどう考えても無理
三角形の成立条件を考える
R+G>B && R+B>G && B+G>R
どれか一つ和を持っておけば済むとかがあると嬉しいけど思いつかない
条件の否定を取って補集合の方を数えることにしてみる
R+G<=B || R+B<=G || B+G<=R になる
和集合を数えたいので包除原理っぽい
R+G<=Bだけを満たすのを数えるだけならDPすればできる
対称性があるので3倍すればよさそう
2つ条件を満たす場合を数え上げたい
R+G<=B && R+B<=G
いろいろ考えてしばらく迷走する
これ満たすのB=G, R=0 しかない
R=0 or G=0 or B=0 だったら三角形ができることはない
R>0 && G>0 && B>0 && R+G<=B のパターンを数え上げる
対称性でこれを3倍する
全体(R!=0&&G!=0&&B!=0の塗り方)からこの値を引けば答えになる
dp[i番目まで][j=R+G][k=(R>0)][l=(G>0)] = (組み合わせ数) としてDP

modintバグってたのとmake_vをグローバルにしたら爆速になったのとかが虚無だった

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
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> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
// const ll MOD = 1000000007;

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) { x = x * r.x % MOD; 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; }
};
using mint = modint<998244353>;
template<class T> mint operator*(T l, mint r) { return mint(l) *= r; }
template<class T> mint operator+(T l, mint r) { return mint(l) += r; }
template<class T> mint operator-(T l, mint r) { return mint(l) -= r; }
template<class T> mint operator/(T l, mint r) { return mint(l) /= r; }
template<class T> bool operator==(T l, mint r) { return mint(l) == r; }
template<class T> bool operator!=(T l, mint r) { return mint(l) != r; }
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }
string to_frac(mint v) {
    static map<ll, PII> mp;
    if(mp.empty()) {
        mp[0] = mp[mint::mod()] = {0, 1};
        FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {
            mp[(mint(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;
}

mint dp[300][90001][2][2];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    ll sum = 0;
    vector<ll> a(n);
    REP(i, n) cin >> a[i], sum += a[i];

    dp[0][0][0][0] = 1;
    dp[0][a[0]][1][0] = 1;
    dp[0][a[0]][0][1] = 1;
    FOR(i, 1, n) REP(j, sum+1) REP(k, 2) REP(l, 2) {
        if(j>=a[i]) {
            dp[i][j][k|1][l] += dp[i-1][j-a[i]][k][l];
            dp[i][j][k][l|1] += dp[i-1][j-a[i]][k][l];
        }
        dp[i][j][k][l] += dp[i-1][j][k][l];
    }

    mint ret = 0;
    FOR(i, 1, sum) if(i <= sum-i) ret += dp[n-1][i][1][1];
    cout << mint(3).pow(n) - mint(2).pow(n)*3 + 3 - ret*3 << endl;

    return 0;
}

2019-04-12

乱択

競技プログラミング

https://codeforces.com/blog/entry/61587 の必要なところのメモ

乱数生成

rand()

乱数生成の質が微妙なのでやめよう
こどふぉだと最大値が32767しかないのでさらにまずい

mt19937

C++11以上で追加された機能でメルセンヌツイスターで乱数を生成する

高速
最大値が2³¹-1
乱数の質もいい

64bitの乱数がほしいならmt19937_64を使うとできる

乱数のseedが他人にバレるとまずい
chrono::steady_clock::now().time_since_epoch().count()
とか
(uint64_t) new char
とかを使おう

一様乱数の生成

rand() % 1000 → 一様にならないのでだめ
uniform_int_distribution → これを使おう

配列のシャッフル

random_shuffle → 内部でrandを使ってるのでやめよう
shuffle → こっちを使おう

一様乱数を生成するコード

struct dice {
    mt19937 mt;
    dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
    // [0, x)の一様乱数
    ll operator()(ll x) { return this->operator()(0, x - 1); }
    // [x, y]の一様乱数
    ll operator()(ll x, ll y) {
        uniform_int_distribution<ll> dist(x, y);
        return dist(mt);
    }
} rnd;

int main() {
    cout << rnd(100) << endl;
    cout << rnd(30, 80) << endl;
}

rand()をどうやって落とす？

https://codeforces.com/blog/entry/61675

2019-04-09

Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory

競技プログラミング Codeforces

問題ページ

解法

頂点a,bを結ぶパスの辺をe本と固定したときの組み合わせ数を求める。まずn-2個の頂点からパス上のe-1個の頂点を選ぶ方法がP(n-2, e-1)通りである。次にパス上の辺の重みを決定する方法について考える。mをe分割する方法はm個のボールの間(m-1個)にe-1個の仕切りを入れると考えることができC(m-1, e-1)通りである。
パス以外の辺の重みは自由に決められるのでm^(n-1-e)通りである。ラベルつきの森が何通りあるか求めるにはCayley's_formulaを用いればよい。頂点数n、連結成分数kの森はk*n^(n-1-k)通りである。今回の条件設定に当てはめると(e+1)*n^(n-2-e)通りである。e=n-1のときに注意。
まとめると辺数がeのときP(n-2,e-1)*C(m-1,e-1)*m^(n-1-e)*(e+1)*n^(n-2-e)通りとなる。これを1<=e<=n-1について足せばよい。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
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> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

template<ll MOD>
struct modint {
    ll x;
    modint(): x(0) {}
    modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
    ll get() const { return x; }
    // 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);
    }
    ll extgcd(ll a, ll b, ll &x, ll &y) {
        ll g = a; x = 1, y = 0;
        if(b != 0) g = extgcd(b, a%b, y, x), y -= (a/b) * x;
        return g;
    }
    modint inv() {
        ll s, t; extgcd(x, MOD, s, t);
        return modint(s);
    }
    // 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; }
    // 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; }
    // Basic Operations
    modint &operator+=(modint that) {
        x += that.x;
        if(x >= MOD) x -= MOD;
        return *this;
    }
    modint &operator-=(modint that) {
        x -= that.x;
        if(x < 0) x += MOD;
        return *this;
    }
    modint &operator*=(modint that) {
        x = (ll)x * that.x % MOD;
        return *this;
    }
    modint &operator/=(modint that) {
        x = (ll)x * that.inv().x % MOD;
        return *this;
    }
    modint &operator%=(modint that) {
        x = (ll)x % that.x;
        return *this;
    }
    modint operator+(modint that) const { return *this += that; }
    modint operator-(modint that) const { return *this -= that; }
    modint operator*(modint that) const { return *this *= that; }
    modint operator/(modint that) const { return *this /= that; }
    modint operator%(modint that) const { return *this %= that; }
};
using mint = modint<1000000007>;
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

ll binpow(ll x, ll e) {
  ll ret = 1, p = x;
  while(e > 0) {
    if(e&1) {(ret *= p) %= MOD; e--;}
    else {(p *= p) %= MOD; e /= 2;} 
  }
  return ret;
}

template<bool bigN=false>
ll combi(ll N_, ll K_, ll mo=MOD) {
    const int NUM_=1e6+10;
    static ll fact[NUM_+1]={},factr[NUM_+1]={},inv[NUM_+1]={};
    auto binpow = [&](ll x, ll e) -> ll {
        ll a = 1, p = x;
        while(e > 0) {
        if(e%2 == 0) {p = (p*p) % mo; e /= 2;}
        else {a = (a*p) % mo; e--;}
        }
        return a;
    };
    if (fact[0]==0) {
        fact[0] = factr[0] = inv[0] = 1;
        FOR(i, 1, NUM_+1) fact[i] = fact[i-1] * i % MOD;
        factr[NUM_] = binpow(fact[NUM_], mo-2);
        for(int i=NUM_-1; i>=0; --i) factr[i] = factr[i+1] * (i+1) % MOD;
        // bigNがないならいらない
        // REP(i, NUM_+1) inv[i] = binpow(i, MOD-2);
    }
    if(K_<0 || K_>N_) return 0;
    // 前計算 O(max(N,K)) クエリ O(1)
    if(!bigN) return factr[K_]*fact[N_]%MOD*factr[N_-K_]%MOD;
    // Nが大きいけどKが小さい場合に使う 前計算 O(Klog(mod)) クエリ O(K)
    ll ret = 1;
    for(;K_>0;N_--,K_--) (ret *= N_%MOD) %= MOD, (ret *= inv[K_]) %= MOD;
    return ret;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m, a, b;
    cin >> n >> m >> a >> b;

    mint ret = 0, fact = 1;
    FOR(e, 1, n) {
        mint tmp = fact;
        tmp *= combi(m-1, e-1);
        tmp *= binpow(m, n-1-e);
        if(e != n-1) {
            tmp *= e+1;
            tmp *= binpow(n, n-2-e);
        }
        fact *= n-e-1;
        ret += tmp;
    }
    cout << ret << endl;

    return 0;
}

ferinの競プロ帳

競プロについてのメモ

CPSCO 2019

Codeforces Round #556 (Div. 2) D. Three Religions

解法

GCJ 2019 R1B Fair Fight

解法

Tenka1 Programmer Contest 2019 E - Polynomial Divisors

解法

Tenka1 Programmer Contest 2019 D - Three Colors

考えたこと

乱択

乱数生成

rand()

mt19937

一様乱数の生成

配列のシャッフル

一様乱数を生成するコード

rand()をどうやって落とす？

Codeforces Round #539 (Div. 2) F. Sasha and Interesting Fact from Graph Theory

解法