SRM603 div1 Easy MaxMinTreeGame

メモ

Atcoderの D - ABS と似た考察でいけた。

先攻が3ターン目以降で良い点数を狙うことができない系の問題。後攻が2ターン目で得られる最小の得点で終了させるから。

なので1ターン目で終了する時の最大値を出力すればOK。

今回は葉の頂点の中でのコストの最大値を出力すればOK。

コード

class MaxMinTreeGame {
public:
  int findend(vector <int> edges, vector <int> costs) {
    int n = costs.size();
    int eda[n];
    CLR(eda);
    FOR(i,0,n-1) {
      eda[edges[i]]++;
      eda[i+1]++;
    }
    int ans = 0;
    FOR(i,0,n) if(eda[i]==1) ans = max(ans, costs[i]);
    return ans;
  }
};

Atcoderの問題解いてたからこの方針が思いついた