全国統一プログラミング王決定戦予選

C - Different Strokes

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

方針

二人とも が大きいものから順に取っていきます。

i のうち、高橋君が食べるものの集合を 、青木さんが食べる分を と表すことにし、

とします。高橋君は X を最大化し、青木さんは最小化するように料理を選びます。

で、2つ目のシグマは一定ですから、高橋君から見て を最大化すればよいことが分かります。青木さんについても同様に示せます。

実装の際は tupleに(A+B, A, B) を詰めて、A+Bについてソートします。あとは上から順番に高橋君、青木さんの順に交互に分配していけばよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N;  cin >> N;
    vector<tuple<ll,ll,ll>> S(N);
    for(int i=0; i<N; i++){
        ll A, B;  cin >> A >> B;
        S[i] = make_tuple(A+B,A,B);
    }
    sort(S.begin(), S.end());

    ll ans = 0;
    for(int i=0; i<N; i++){
        int n = N-1-i;
        if(i%2==0){
            ans += get<1>(S[n]);
        }else{
            ans -= get<2>(S[n]);
        }
    }
    cout << ans << endl;
}

D - Restore the Tree

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_d

高橋君の辺の伸ばし方

高橋君は「ある頂点 からその子孫であるような頂点 に向かって」辺を伸ばします。ですので、入力例1で元の木は

であると考えることはできません。頂点2から頂点3へ辺を伸ばしたことになりますが、3は2の子孫ではないからです。

方針

まず、根は自分を宛先とする辺が 0 本であるような頂点です。

与えられたグラフから元の木を復元するには、根から各頂点への距離が最大になるような辺のみを残せばよいです。なぜなら、高橋君が付け足した辺 で は の子孫なので、付け足された辺は根から頂点 や、 の子孫へと向かう際のショートカットの経路になるからです。参考として、入力例2の場合が下図になります。

根からの距離の最大値を求めるのには深さ優先探索を使いました。頂点 i への距離が更新されるたびに i の親を更新していけばよいです。
ただし普通に深さ優先探索を行うと、ある頂点の距離が更新されると、その子孫の計算を全てやり直すことになりTLEします。

今回は根から順に最長距離を確定させていくので、辺が n 本入る頂点は、探索でその頂点に n 回目に到達したときに子孫の探索を行うようにすればよいです。実装においては、各頂点 i について親の数 nPar[i] を持っておき、探索で頂点 i に達するたびに nPar[i] をデクリメントします。 nPar[i] = 0 となったときに以降の探索を行えばよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> chi;
vector<int> nPar;
vector<int> dist;
vector<int> ans;

void dfs(int n){
    // 葉に達したら探索を終える
    if(chi[n].size()==0) return;

    int nChi = chi[n].size();
    // 頂点 n の子の、根からの距離を求める
    for(int i=0; i<nChi; i++){
        int nxt = chi[n][i];
        nPar[nxt]--;
        if(dist[nxt] < dist[n] + 1){
            // 距離が更新される時に、親を更新する
            dist[nxt] = dist[n] + 1;
            ans[nxt] = n;
        }
        // 頂点 nxt への nPar[nxt] 回目の参照のとき、以降の探索を行う。
        if(nPar[nxt]==0) dfs(nxt);
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    // chi[i][j] は頂点 i の j 番目の子
    chi = vector<vector<int>>(N+1, vector<int>());
    // 各頂点の親の数を数えておく
    nPar = vector<int>(N+1,0);
    for(int i=0; i<N+M-1; i++){
        int A, B;  cin >> A >> B;
        chi[A].push_back(B);
        nPar[B]++;
    }
    
    // 根を求める
    vector<bool> rootCand(N+1, true);
    for(int i=1; i<=N; i++){
        int nChi = chi[i].size();
        for(int j=0; j<nChi; j++) rootCand[chi[i][j]]=false;
    }
    int root;
    for(int i=1; i<=N; i++) if(rootCand[i]) root = i;
    
    // dist[i] は根から頂点 i への距離
    dist = vector<int>(N+1, 0);
    // ans[i] は頂点 i の親
    ans = vector<int>(N+1, 0);
    ans[root] = 0;
    // 根から深さ優先探索を行う
    dfs(root);
    for(int i=1; i<=N; i++){
        cout << ans[i] << endl;
    }
}