チーム練習(05/13) - ferinの競プロ帳

Dashboard - 2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019) - Codeforces をやった。

C,F,I は気づいたら通ってた
B,K はわからん

A

得点が同じ人ごとにまとめておいて、点数が変化した人の分だけ更新するようにシミュレーションすると通るらしい

D

まず $v$ の値に関しては答えに何も関係がない。あるパス $P={e_1, \ldots, e_k}$ の長さは $\displaystyle \sum_{i=1}^k (l_i/v+c) = \frac{1}{v}\sum_{i=1}^k (l_i+vc)$ なので結局定数を足したものと変わらない。以降では $v=1$ として考える。

$c=\infty$ とすると、辺の本数を最小化したパスが最短となることがわかる。ようするに $c$ を増やすと辺の本数が減少していくので、辺の本数と関連があることがわかる。

$c=0$ で辺の本数を $k$ に固定したとき、最短となるパスを求める。 $\text{dist} \lbrack$ 辺の本数 $i \rbrack \lbrack$ 頂点 $j \rbrack =($ 始点からの最短距離 $)$ とすると、 $\text{chmin}(\text{dist} \lbrack i+1 \rbrack \lbrack to \rbrack , \text{dist} \lbrack i \rbrack \lbrack j \rbrack )$ という遷移で計算できる。

辺の本数が $k$ 本のパスで $c=x$ のときの最短路長は $\text{dist} \lbrack k \rbrack \lbrack n-1 \rbrack + kx$ である。 $k$ 本の直線の中で最小になるような $x \geq 0$ が存在する場合、辺の本数が $k$ のパスが最短になるような $c$ が存在する。このような直線集合はconvex hull trickの要領で求めることができる。

あとは長さが $k$ で最短となるようなパスに含まれる頂点を列挙し、答えから外す。残っている頂点集合を出力すれば良い。

▶ソースコード(クリックで展開)

#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)  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<vector<PII>> g(n);  
    REP(i, m) {  
        ll a, b, c;  
        cin >> a >> b >> c;  
        a--, b--;  
        g[a].push_back({b, c});  
        g[b].push_back({a, c});  
    }  
  
    // dist[頂点i][辺がj本] = (頂点0からの距離)  
    vector<vector<ll>> dist(n, vector<ll>(n, INF));  
    dist[0][0] = 0;  
    REP(i, n-1) REP(j, n) for(auto to: g[j]) {  
        chmin(dist[i+1][to.first], dist[i][j] + to.second);  
    }  
  
    // 最小を取りうるものだけに辺の本数を限定  
    deque<PII> st;  
    auto check = [&](const PII &a, const PII &b, const PII &c) {  
        __int128_t xa = c.second-a.second, ya = a.first-c.first,  
                   xb = b.second-a.second, yb = a.first-b.first;  
        return xa * yb < xb * ya;  
    };  
    auto insert = [&](ll a, ll b) {  
        PII p({a, b});  
        while(st.size()>=2 && check(st[st.size()-2], st[st.size()-1], p)) st.pop_back();  
        st.emplace_back(p);  
    };  
    for(int i=n-1; i>=1; --i) insert(i, dist[i][n-1]);  
    while(st.size() >= 2 && st[0].second > st[1].second) st.pop_front();  
  
    // 復元  
    vector<bool> mark(n);  
    vector<vector<bool>> visit(n, vector<bool>(n));  
    auto dfs = [&](auto &&self, ll edge, ll v) -> void {  
        mark[v] = visit[edge][v] = true;  
        if(v == 0) return;  
        for(auto to: g[v]) {  
            if(dist[edge-1][to.first] + to.second == dist[edge][v]) {  
                if(visit[edge-1][to.first]) continue;  
                self(self, edge-1, to.first);  
            }  
        }  
    };  
    for(auto i: st) dfs(dfs, i.first, n-1);  
  
    vector<ll> ans;  
    REP(i, n) if(!mark[i]) ans.push_back(i);  
    cout << ans.size() << "\n";  
    REP(i, ans.size()) cout << ans[i]+1 << (i+1==(ll)ans.size() ? '\n' : ' ');  
  
    return 0;  
}