ferinの競プロ帳

競プロについてのメモ

CODE THANKS FESTIVAL 2018 G - Sum of Cards

問題ページ

解法

 n 頂点のグラフで考える. i枚目のカードの表に X,裏に  Y が書かれている場合,頂点  X と頂点  Y の間に辺を引く.問題文の条件をこのグラフ上に言い換えると,

  • 表裏を選ぶ操作→各辺を向き付けする.
  •  k 種類以上の整数が見える→出次数が1以上の頂点がk個以上にする.
  • 見えている数の和の最大化→  \sum_{v} ( 頂点  v から出ている辺の本数  )\times v の最大化

となる. a_i, b_i は順列になっていることから,このグラフは全頂点の次数が2で,各連結成分は一つのサイクルになっている.各サイクルごとに  j 種類使ったときに達成しうる最大値が計算できれば,あとはナップサックDPの要領で  K 種類以上の数が見えるときの和の最大値を求められる.したがって,各サイクルごとに  j 種類使ったときに達成しうる最大値を計算する方法を考える.

この問題では  k \leq n \leq 5000 であることから  O(NK) 程度の大きさのDPテーブルは持てる.このような問題では  dp \lbrack i \rbrack \lbrack j \rbrack = i 番目までで  j 種類使ったときの最大値 というような状態の持ち方が定石となる.このようにDPテーブルを保持したときに i, i-1 番目の頂点間の辺の向き付けに対応する遷移がどのようになるか考える. i-1 番目の頂点から  i-2 番目の頂点に向き付けされていて, i-1 番目から  i 番目へ向き付けする場合のみ,種類数  jが増加しない.よって種類数が増加するかどうかの判定のためには,直前の辺の向きをDPテーブルに持っておけば可能となる.サイクルの最後の頂点についての辺の向き付けで種類数が増加するかの判定を行うためには,サイクルの最初の頂点と最後の頂点の間の辺の向きをDPテーブルに持っておけば可能となる.

よって
 dp \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack \lbrack l \rbrack = サイクルの  i 番目までで  j 種類の数を使い直前の辺の向きが  k で最初の頂点と最後の頂点の辺の向きが  l のときの和の最大値
というDPテーブルを持つことで  i, i-1 番目の頂点間の辺の向き付けに対応する遷移を実現できる.具体的な遷移はソースコードを見てください.

まとめると,

  • グラフを構築してサイクルに分割
  • サイクルごとにDPして  j 種類の数を使ったときの和の最大値を求める
  • ナップサックDPでサイクルごとの値をまとめて最終的な答えを求める

とすればよい.

これ500点ってマジ???

#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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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[5010][5010][2][2], x[5010][5010];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

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

    vector<vector<ll>> g(n);
    REP(i, n) {
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    ll idx = 0;
    vector<vector<ll>> vs;
    vector<bool> used(n);
    function<void(ll)> dfs = [&](ll v) {
        used[v] = true;
        vs[idx].push_back(v+1);
        for(auto to: g[v]) {
            if(!used[to]) dfs(to);
        }
    };
    REP(i, n) {
        if(!used[i]) {
            vs.push_back(vector<ll>());
            dfs(i);
            idx++;
        }
    }

    memset(dp, -1, sizeof(dp));
    idx = 0;
    vector<vector<ll>> dp2(vs.size());
    for(auto v: vs) {
        // サイクルvについてDP
        const ll m = v.size();
        dp[0][1][1][1] = v[m-1];
        dp[0][1][0][0] = v[0];
        FOR(i, 1, m) FOR(j, 1, m+1) REP(k, 2) {
            if(dp[i-1][j][0][k] != -1) {
                chmax(dp[i][j][1][k], dp[i-1][j][0][k] + v[i-1]);
                if(i==m-1 && k==1) {
                    chmax(dp[i][j][0][k], dp[i-1][j][0][k] + v[i]);
                } else {
                    chmax(dp[i][j+1][0][k], dp[i-1][j][0][k] + v[i]);
                }
            }
            if(dp[i-1][j][1][k] != -1) {
                chmax(dp[i][j+1][1][k], dp[i-1][j][1][k] + v[i-1]);
                if(i == m-1 && k==1) {
                    chmax(dp[i][j][0][k], dp[i-1][j][1][k] + v[i]);
                } else {
                    chmax(dp[i][j+1][0][k], dp[i-1][j][1][k] + v[i]);
                }
            }
        }
        // dp2[i番目のサイクル][j種類使った] = 和の最大値
        dp2[idx].resize(v.size()+1);
        REP(i, m) REP(j, 2) REP(k, 2) {
            chmax(dp2[idx][i+1], dp[m-1][i+1][j][k]);
        }
        idx++;
        // dpの初期化
        REP(i, m) FOR(j, 1, m+1) REP(k, 2) REP(l, 2) {
            dp[i][j][k][l] = -1;
        }
    }

    // ナップサックDPの要領で連結成分ごとの値をまとめる
    memset(x, -1, sizeof(x));
    x[0][0] = 0;
    REP(i, dp2.size()) REP(j, K+1) REP(k, dp2[i].size()) {
        if(x[i][j] == -1) continue;
        chmax(x[i+1][min(j+k, K)], x[i][j] + dp2[i][k]);
    }
    cout << x[vs.size()][K] << endl;

    return 0;
}

M-SOLUTIONS プロコンオープン C - Best-of-(2n-1)

問題ページ

解法

 a = \frac{A}{100}, b = \frac{B}{100}, c = \frac{C}{100} = 1-a-b とする.

高橋くんが勝つのが  n 回,青木くんが勝つのが  i 回,引き分けが  j 回起きるとする.

期待値の前にまず確率がどのようになるか考える.高橋くんが最後に勝つのは確定で,それ以外の部分は確率  a の操作が  n-1 回,確率  b の操作が  i 回,確率  c の操作が  j 回起きるような事象の確率である.高橋くんが勝つ確率は  a で,後半の事象の確率は独立試行であることを用いて  \frac{(n-1+a+b)!}{a!b!(n-1)!} a^{n-1} b^{i} c^{j} となる.よって確率は  \frac{(n-1+a+b)!}{a!b!(n-1)!} a^{n} b^{i} c^{j} となる.

期待値の定義から確率とゲームの回数の積を足し合わせることで期待値を計算すると  \sum_{i=0}^{n-1} \sum_{j=0}^{\infty} \frac{(n-1+i+j)!}{i!j!(n-1)!} a^{n} b^{i} c^{j} \times (n+i+j) = \sum_{i=0}^{n-1} \sum_{j=0}^{\infty} \frac{(n+i+j)!}{i!j!(n-1)!} a^{n} b^{i} (1-a-b)^{j} となる.無限級数の部分をWolframAlpha先生に計算してもらうと  \sum_{j=0}^{\infty} \frac{(i+j+n)!}{i! j! (n-1)!)} a^{n} b^{i} (1-a-b)^{j} = \frac{a^{n} b^{i} (i+n)! }{ i! (n-1)! (a+b)^{n+1+i} } と閉じた形になる.あとは  O(n) で和を計算すれば期待値が求まる.
https://ja.wolframalpha.com/input/?i=sum[(i%2Bj%2Bn)!%2F(i!j!(n-1)!)+an+bi+(1-a-b)j,+{j,+0,+inf}]&assumption="i"+->+"Variable"

青木くんが勝つ場合についても同様に計算でき,足し合わせることで答えが求まる.

#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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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; }
    friend modint pow(modint x, ll e) {
        modint a = 1;
        while(e > 0) {
            if(e%2 == 0) {x *= x; e /= 2;}
            else {a *= x; e--;}
        }
        return 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 = x * r.x % MOD; return *this;
    #endif
        unsigned long long y = 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; }
};
using mint = modint<1000000007>;
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;
}

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

    ll n, aa, bb, cc;
    cin >> n >> aa >> bb >> cc;

    mint fact = 1;
    FOR(i, 1, n) fact *= i;
    mint a(aa), b(bb), c(cc);
    a /= 100, b /= 100, c /= 100;

    mint ret = 0;
    mint x = 1, y = 1;
    FOR(i, 1, n+1) x *= i;
    REP(i, n) {
        if(i) x *= n+i, y *= i;
        ret += pow(a, n) * pow(b, i) * x / pow(a+b, i+n+1) / y / fact;
    }
    x = 1, y = 1;
    FOR(i, 1, n+1) x *= i;
    REP(i, n) {
        if(i) x *= n+i, y *= i;
        ret += pow(b, n) * pow(a, i) * x / pow(a+b, i+n+1) / y / fact;
    }

    cout << ret << endl;

    return 0;
}

AIM Tech Round 5 (rated, Div. 1 + Div. 2) D. Order book

問題ページ

解法

サンプル2について考える.

4
ADD 1
ADD 2
ADD 3
ACCEPT 2

ACCEPTが正常に行われるには2がBUYの最善かSELLの最善である必要がある.したがって2未満はBUY,2より大きいものはSELL以外にすることが不可能でどちらにすべきか確定する.

このsampleのようにACCEPTが行われたタイミングでBUYにすべきかSELL にすべきかを確定していく.ACCEPTのタイミングでどのような処理を行うか考える.
ACCEPT p

  • pが存在しない(ADDされていない or すでにACCEPTで消された) 不可能な操作列なのでans=0で終了
  • pが未確定
    • pがBUYの最善以下 もしくは pがSELLの最善以上 → 不可能
    • それ以外
      ans *= 2
      pより大きいものはSELL,p未満はBUYで確定する
      pを削除する
  • pが確定
    • pが最善ではない → 不可能
    • pが最善
      pより大きいものはSELL,p未満はBUYで確定する
      pを削除する

注意する点として最後がADDのケースがある.最後のACCEPTのあとにADDされたpのうち,BUYの最善とSELLの最善の間のものはBUYとSELLのどちらにするのか自由度がある.BUYとSELLを区切る位置がBUYの最善とSELLの最善の間のものの個数通り存在する.したがってこれを最後に答えに掛ける.

ここからは自分がどのように実装したかを書く.処理を行う上で必要なこととして pが存在するか?の判定,pが確定か?の判定,pはBUYとSELLのどちらか?の判定 などがある.これらを行うために 存在しているp,BUYに属しているp,SELLに属しているp をsetで持っておく.
また,未確定のものをBUYやSELLで確定したものに移す処理のため未確定のものをvectorで持っておく.
これらのデータ構造を用いることで どの処理をすべきなのか? を判定し順番に処理を行っていく.

場合分けとすべき処理をちゃんともれなく考える必要があって大変

#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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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<string> s(n);
    vector<ll> p(n);
    REP(i, n) cin >> s[i] >> p[i];

    ll ans = 1;
    vector<ll> v;
    set<ll> buy, sell, st;
    REP(i, n) {
        if(s[i] == "ADD") {
            v.push_back(p[i]);
            st.insert(p[i]);
        } else {
            // pが存在しない
            if(st.find(p[i]) == st.end()) {
                ans = 0;
                break;
            }
            // pが未確定
            else if(buy.find(p[i])==buy.end() && sell.find(p[i])==sell.end()) {
                ll buy_best = (buy.size()?(*(buy.rbegin())):-1);
                ll sell_best = (sell.size()?(*(sell.begin())):LLINF);
                if(buy_best > p[i] || p[i] > sell_best) {
                    ans = 0;
                    break;
                }
                (ans *= 2) %= MOD;
                st.erase(p[i]);
                for(auto j: v) {
                    if(j < p[i]) buy.insert(j);
                    else if(j > p[i]) sell.insert(j);
                }
            }
            // pが確定
            else {
                if(buy.size() && p[i] == *(buy.rbegin())) {
                    st.erase(p[i]);
                    buy.erase(p[i]);
                } else if(sell.size() && p[i] == *(sell.begin())) {
                    st.erase(p[i]);
                    sell.erase(p[i]);
                } else {
                    ans = 0;
                    break;
                }
                for(auto j: v) {
                    if(j < p[i]) buy.insert(j);
                    else if(j > p[i]) sell.insert(j);
                }
            }
            v.clear();
        }
        // cout << "i=" << i << endl << "v=" << v << endl << "st=" << st << endl << "buy=" << buy << endl << "sell=" << sell << endl;
    }

    ll tmp = 0;
    REP(i, v.size()) {
        ll buy_best = (buy.size()?(*(buy.rbegin())):-1);
        ll sell_best = (sell.size()?(*(sell.begin())):LLINF);
        if(buy_best < v[i] && v[i] < sell_best) {
            tmp++;
        }
    }
    cout << ans * (tmp+1) % MOD << endl;

    return 0;
}

Technocup 2019 - Elimination Round 1 E. Vasya and Good Sequences

問題ページ

解法

まず区間  l,r を一つ固定して,この区間が条件を満たせるかの判定を考える.

ビットが立っている数が同じであれば作れる数字の集合は同じなため  a \lbrack i \rbrack の値は本質ではなくビットが立っている数が大事. b \lbrack i \rbrack = a \lbrack i \rbrack のビットが立っている数とする.

 a \lbrack l \rbrack \text{ xor } \ldots \text{ xor } a \lbrack r \rbrack = 0 とできる方法があるかの判定は,
「色  i のボールが  b \lbrack i \rbrack 個あって違う色のボールをペアにできるとき,全てのボールがいずれかのペアに含まれるようなペアの作り方はあるか?」 という問題に帰着できる.この問題は  \sum_{i=l}^{r} b \lbrack i \rbrack が偶数 かつ  \max(b \lbrack i \rbrack) \leq (\sum_{i=l}^{r} b \lbrack i \rbrack)/2 であれば可能となる.

右端  r に対してこの条件を満たす左端  l が何個あるか?という問題を各  r に対して解けばよい.
 \sum_{i=l}^r b \lbrack i \rbrackが偶数 となる左端  l の個数は  \bmod 2 で合計が0/1となる区間  \lbrack i, r \rbrack がそれぞれ何個あるかを管理しておくことで求められる.  \max(b \lbrack i \rbrack) \leq (\sum_{i=l}^{r} b \lbrack i \rbrack)/2 を「満たさない」左端  l b \lbrack i \rbrack \leq 60 なことから  l \geq r-60 に絞られ,全探索が可能である.

満たさない区間の長さが高々60なことに気づかなかった…

#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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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);
    REP(i, n) {
        ll t;
        cin >> t;
        a[i] = __builtin_popcountll(t);
    }

    ll ret = 0;
    vector<ll> parity(2);
    parity[a[0]%2]++;
    FOR(r, 1, n) {
        if(a[r]%2) swap(parity[0], parity[1]);
        // 条件を満たすlが何個あるか
        ll cnt = parity[0];
        ll ma = a[r], sum = a[r];
        for(ll l=r-1; l>=max(0LL,r-60); --l) {
            chmax(ma, a[l]);
            sum += a[l];
            if(sum%2==0 && ma > sum/2) {
                cnt--;
            }
        }
        ret += cnt;
        parity[a[r]%2]++;
    }
    cout << ret << endl;

    return 0;
}

Codeforces Round #290 (Div. 1) C. Fox And Dinner

問題ページ

解法

2以外の偶数は素数にならないことからa[i]とa[j]の偶奇が一致するときa[i]+a[j]は素数にならない
a[i]+a[j]が素数であれば頂点iと頂点jを結んだグラフは二部グラフになる
二部グラフから各頂点の次数が2になるように辺集合を選ぶ問題に帰着できた
これは二部マッチングと同様にフローを使って求めることができる

source → 奇数 に容量2の辺
偶数 → sink に容量2の辺
奇数 → 偶数 に容量1の辺

maxflowがNであれば条件を満たす分割がある
フローの結果、流れている辺が辺集合に属すると判断できるので復元も可能

閉路で分割
→頂点の次数が全て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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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;

struct FordFulkerson {
    struct edge {
        int to;
        ll cap;
        int rev;
        bool isrev;
    };

    vector<vector<edge>> g;
    vector<int> used;
    int timestamp;

    FordFulkerson() {}
    FordFulkerson(int n) : g(n), used(n, -1), timestamp(0) {}

    void add_edge(int from, int to, ll cap) {
        g[from].emplace_back((edge){to, cap, (int)g[to].size(), false});
        g[to].emplace_back((edge){from, 0, (int)g[from].size()-1, true});
    }

    ll dfs(int idx, const int t, ll flow) {
        if(idx == t) return flow;
        used[idx] = timestamp;
        for(auto &e : g[idx]) {
            if(e.cap > 0 && used[e.to] != timestamp) {
                ll d = dfs(e.to, t, min(flow, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    ll max_flow(int s, int t) {
        ll flow = 0;
        ++timestamp;
        for(ll f; (f = dfs(s, t, INF)) > 0; timestamp++) {
            flow += f;
        }
        return flow;
    }
};
ostream &operator <<(ostream& out, const FordFulkerson& a){
    out << "-----" << endl;
    for(int i = 0; i < (ll)a.g.size(); i++) {
        for(auto &e : a.g[i]) {
            if(e.isrev) continue;
            auto &rev_e = a.g[e.to][e.rev];
            out << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
        }
    }
    out << "-----" << endl;
    return out;
}

vector<bool> eratosthenes(ll n=1000000) {
    vector<bool> prime(n, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = 2 * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }
    return prime;
}

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

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

    auto prime = eratosthenes(20001);

    FordFulkerson flow(n+2);
    ll s = n, t = n+1;
    REP(i, n) {
        if(a[i]%2) flow.add_edge(s, i, 2);
        else flow.add_edge(i, t, 2);
    }
    REP(i, n) REP(j, n) {
        if(a[i]%2 && a[j]%2==0 && prime[a[i]+a[j]]) {
            flow.add_edge(i, j, 1);
        }
    }

    if(flow.max_flow(s, t) != n) {
        cout << "Impossible" << endl;
        return 0;
    }

    vector<vector<ll>> v(n);
    REP(i, n) {
        for(auto e: flow.g[i]) {
            if(!e.isrev && e.cap == 0 && e.to < n) {
                // i と e.to は隣接
                v[i].push_back(e.to);
                v[e.to].push_back(i);
            }
        }
    }

    vector<bool> used(n);
    function<vector<ll>(ll,ll)> dfs = [&](ll ver, ll pre) {
        vector<ll> ret;
        used[ver] = true;

        if(v[ver][0]!=pre && !used[v[ver][0]]) ret = dfs(v[ver][0], ver);
        else if(v[ver][1]!= pre && !used[v[ver][1]]) ret = dfs(v[ver][1], ver);

        ret.push_back(ver);
        return ret;
    };

    vector<vector<ll>> ans;
    REP(i, n) if(!used[i]) ans.push_back(dfs(i, -1));

    cout << ans.size() << endl;
    REP(i, ans.size()) {
        cout << ans[i].size();
        for(auto j: ans[i]) cout << " " << j+1;
        cout << endl;
    }

    return 0;
}

Codeforces Round #557 (Div. 2) [based on Forethought Future Cup - Final Round] C. Thanos Nim

問題ページ

解法

どのような状態が勝ち/負けなのか考える。n=6で試してみる。0が4個以上の場合操作できないのでその時点で負けである。0が3個以下の場合、0が4個以上になるように操作して相手に渡せばよいので勝ちになる。1が4個以上の場合、どう操作しても0が3個以下の状態にしか移動できないので負けになる。1が3個以下の場合、1が4個以上になるように操作して渡せば良いので勝ちである。

0 0 0 0 0 0 → 負け
0 0 0 0 0 ? → 負け
0 0 0 0 ? ? → 負け
0 0 0 ? ? ? → 勝ち
0 0 ? ? ? ? → 勝ち
0 ? ? ? ? ? → 勝ち

1 1 1 1 1 1 → 負け
1 1 1 1 1 ? → 負け
1 1 1 1 ? ? → 負け
1 1 1 ? ? ? → 勝ち
1 1 ? ? ? ? → 勝ち
1 ? ? ? ? ? → 勝ち

以上のように実験より最小の要素がn/2個以下であれば勝ち、n/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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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;
    ll mi = LLINF, cnt = 0;
    REP(i, n) {
        ll a;
        cin >> a;
        if(mi > a) mi = a, cnt = 1;
        else if(mi == a) cnt++;
    }

    if(cnt <= n/2) cout << "Alice" << endl;
    else cout << "Bob" << endl;

    return 0;
}

Codeforces Round #554 (Div. 2) D. Neko and Aki's Prank

問題ページ

解法

木において最大マッチングを考える場合、葉が隣接する辺から貪欲に取っていけばよい。葉が隣接する辺を取らなかったことでマッチングに追加できる辺の本数は高々1本なので取らないことで得をすることはないからである。よってTrie木で根からの距離(=深さ)が奇数の頂点からの辺をマッチングに加えれば良い。
Trie木で深さが奇数の頂点が何個あるか?という問題に帰着できた。 dp \lbrack i \rbrack \lbrack j \rbrack = ( 正しい括弧列のprefixで開き括弧を  i 個、閉じ括弧を  j 個使った括弧列の個数  )としたdpを行うことで求めることができ、答えは  \sum_{(i+j)\%2=1} dp \lbrack i \rbrack \lbrack j \rbrack となる。

最初  n \le 10^{5} かと思ってカタラン数から高速に求められる…?とか考えてたら  O(n^{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(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &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<1000000007>;
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[1010][1010];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;

    dp[0][0] = 1;
    REP(i, n+1) REP(j, i+1) {
        if(i+1<n+1 && j<=i+1) dp[i+1][j] += dp[i][j];
        if(j+1<n+1 && j+1<=i) dp[i][j+1] += dp[i][j];
    }

    mint ret = 0;
    REP(i, n+1) REP(j, i+1) if((i+j)%2) ret += dp[i][j];
    cout << ret << endl;

    return 0;
}