ferinの競プロ帳

競プロについてのメモ

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;
}

Codeforces Round #551 (Div. 2) E. Serval and Snake

問題ページ

解法

  • パスの端点を一つも含まないような範囲
    範囲に入った後出ることを繰り返すので返ってくる値は必ず偶数
  • パスの端点を両方含むような範囲
    範囲から出た後入るを繰り返すので返ってくる値は必ず偶数
  • パスの端点を片方だけ含む範囲
    範囲内と範囲外を往復したあと出て終わりになるので返ってくる値は必ず奇数

各列/行を覆うような範囲を指定してどの行/列に端点があるのか?を特定する。その後二分探索を行うことで返ってくる値が奇数の範囲を見つける。

行/列の特定に1000回、二分探索にそれぞれ10回最悪でかかるので最悪ケースが来ると条件を満たさない。しかし行/列を指定する順番をランダムにすると最悪を引く確率はかなり小さそうだったので投げると通った。

#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;

// #define DEBUG
ll query(ll x1, ll y1, ll x2, ll y2) {
#ifdef DEBUG

#else
    cout << "? " << y1+1 << " " << x1+1 << " " << y2+1 << " " << x2+1 << endl;
    ll ret;
    cin >> ret;
    return ret;
#endif
}

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

    ll n;
    cin >> n;

    vector<ll> idx(n);
    iota(ALL(idx), 0);
    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(ALL(idx), mt);

    PII p1({-1, -1}), p2({-1, -1});
    for(auto i: idx) {
        ll num = query(0, i, n-1, i);
        if(num%2) {
            if(p1.first == -1 && p1.second == -1) p1.first = -1, p1.second = i;
            else {
                p2.first = -1, p2.second = i;
                break;
            }
        }
    }
    for(auto i: idx) {
        if(p2.first != -1 || p2.second != -1) break;
        ll num = query(i, 0, i, n-1);
        if(num%2) {
            if(p1.first == -1 && p1.second == -1) p1.first = i, p1.second = -1;
            else {
                p2.first = i, p2.second = -1;
                break;
            }
        }
    }

    ll lb=0,ub=n;
    while(ub-lb>1) {
        ll mid = (lb+ub)/2;

        ll num;
        if(p1.first == -1) num = query(mid, p1.second, ub-1, p1.second);
        else num = query(p1.first, mid, p1.first, ub-1);

        if(num%2) lb = mid;
        else ub = mid;
    }
    ll x1, y1;
    if(p1.first == -1) x1 = lb, y1 = p1.second;
    else x1 = p1.first, y1 = lb;

    lb=0,ub=n;
    while(ub-lb>1) {
        ll mid = (lb+ub)/2;

        ll num;
        if(p2.first == -1) num = query(mid, p2.second, ub-1, p2.second);
        else num = query(p2.first, mid, p2.first, ub-1);

        if(num%2) lb = mid;
        else ub = mid;
    }
    ll x2, y2;
    if(p2.first == -1) x2 = lb, y2 = p2.second;
    else x2 = p2.first, y2 = lb;

    cout << "! " << y1+1 << " " << x1+1 << " " << y2+1 << " " << x2+1 << endl;

    return 0;
}

AGC018 D - Tree and Hamilton Path

問題ページ

考えたこと

  • 完全グラフだと辺の本数が多すぎてつらそう
  • 木の任意の頂点間を移動できると思った方がよさそう
  • 任意の順番で木上を移動するとき最長となる経路長を答える問題になった
  • よくわからないので実験する
  • ある頂点からはじめて最も遠い頂点に移動するを繰り返すみたいな貪欲をしてみる
  • サンプル1で頂点1から始めると重み5の辺を一回しか通れない
  • 頂点2か頂点5から始めるとよさそう
  • 重みが小さい辺の端点から始めるといい?
  • サンプル2で試すと132じゃなくて128になる
  • 通れてない辺がありそう
  • 辺を通れる回数について考えることにする
  • ある辺で木を切断したときに連結成分の要素数がs1、s2になったとする
  • s1 = s2 の場合 s1*2-1回 しか通れない
  • s1 != s2 の場合 min(s1, s2)*2回 しか通れない
  • 各辺を通れる回数の上界はわかった
  • 上界を取れるとして計算するとサンプル2は合うがサンプル1は合わない
  • 上界を取れない木を見つけて適当な辺一つの重みを引けばよさそう…?
  • 上界を取れない木がどのようなものなのか考えたいので実験する
  • 上界を取れない木ならmin(辺の重み)を答えから引けばいいかなと思ったけどそうではなさそう
  • 上界を取れない辺は大体1頂点を端点として共有していそう…?
  • 頂点数の偶奇で上界を取れる木と取れない木の判定できるかと思ったけど違う
  • 上界を取れる木と取れない木の判定、上界を取れない辺がどの辺なのかがわからない

-----解説を見た-----

  • 上界を取れる木と取れない木の判定はs1==s2となる辺が存在するか?
  • 上界を取れない辺は重心を端点とする点

実験してたのを見返すと上界を取れない辺が中心付近なのはわかるので重心を端点とする点なのはわかってもよかったかもしれない
重心が絡むことに気づけると重心は1個の場合と2個の場合が存在してるのでそれぞれ場合分けして考えればこの条件も導けた…?

解説放送のやり方

パス  a_{1}, a_{2}, \ldots, a_{n} の距離は  \sum_{i=1}^{n} \text{depth}(a_{i}) + \text{depth}(a_{i+1}) - 2\times\text{depth}(\text{lca}(a_{i}, a_{i+1})) となる。どう順番を決めたところで  \text{depth}(a_{i}) の中間は変わらないのでどうでもよくて先頭と末尾だけ影響する。LCAの部分がいろいろ変わって厄介だけど重心を根に取ったグラフを考えるとLCAの部分は常に0にできることが示せる。結局先頭を重心、末尾を重心に隣接する点のうち深さが最小なものと取ればよい。

木の距離って言われたらとりあえずLCAを持ち出すのこの間こどふぉでも見たし覚えておいてよさそう

#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;

bool flag;
ll n, ans, centroid = -1;
vector<PII> g[100010];
ll dfs(ll v, ll p) {
    ll ret = 1;
    bool is_centroid = true;
    for(auto to: g[v]) {
        if(to.first == p) continue;
        ll sz1 = dfs(to.first, v);
        if(sz1 > n/2) is_centroid = false;
        ret += sz1;
        // sz と n-sz
        ll sz2 = n-sz1;
        if(sz1 == sz2) {
            ans += (sz1*2-1) * to.second;
            flag = true;
        } else {
            ans += min(sz1, sz2) * 2 * to.second;
        }
    }
    if(n-ret > n/2) is_centroid = false;
    if(is_centroid) centroid = v;
    return ret;
}

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

    cin >> n;
    REP(i, n-1) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    dfs(0, -1);
    if(!flag) {
        assert(centroid != -1);
        ll mi = LLINF;
        for(auto i: g[centroid]) {
            chmin(mi, i.second);
        }
        ans -= mi;
    }
    cout << ans << endl;

    return 0;
}

CPSCO 2019

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

Session1
A: 算数
B: 各文字の出現回数を数える
C: binom(32, 6) の全探索
D: 8*5n-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: 根を決めると残りの頂点をどのように子に分割するかが決められる
再帰的に構築

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

問題ページ

解法

まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいので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;
}