SRM603 Div1 Easy MaxMinTreeGame

概要

木のある辺を削除して2つに分かれた方の片方を残すという操作を先手は最大化,後手は最小化させるように交互に繰り返す.最終的に残るのはなにか

解法

辺が1つの頂点のうち最大のものを残す,という直感がそのままACした.
辺が2つ以上の頂点は1手で単体にすることができず,後手が削除することが可能だからそうなるようだ.
コンテストではないときは貪欲は証明してから書くようにしたい…

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(ll i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(ll i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
class MaxMinTreeGame{
public:
    int findend(vi edge,vi cost){
        int n=cost.size();
        vi vec(n,1);
        vec[0]=0;
        REP(i,n-1){
            vec[edge[i]]++;
        }
        int mi=INF;
        int res=INF;
        REP(i,n){
            if(mi>vec[i]){
                mi=vec[i];
                res=cost[i];
            }else if(mi==vec[i]){
                chmax(res,cost[i]);
            }
        }
        return res;
    }
};