TopCoder SRM 603 Div1 Easy MaxMinTreeGame [1人競技プログラミング Advent Calendar 2016 4日目]
この記事は1人競技プログラミング Advent Calendar 2016 4日目の記事です。
問題概要:
TopCoder Statistics - Problem Statement
ノードにコストがある木が与えられる。
2人のプレイヤーがノード数1になるまで下記の行動を順番に取ることが出来る。
・1個のエッジを選んで消す
・上記の手順後、2個になった木の内片方を消す
先手プレイヤーは最終的に残ったノードのコストを出来る限り大きく、後手プレイヤーは出来る限りコストを小さくしたい。
お互い最適にプレイした際の答えを出力せよ。
解いた方法:
例えば先手プレイヤーが最終的に残したいノードの木を残したとしても後手プレイヤーが消すことが出来る。(逆も成り立つ)
なので、先手プレイヤーが最初の1手でノード数1になるような最もコストの高いノード(要するに葉ノード)を1手目で残すのが最適戦略となる。
#include<bits/stdc++.h> #define MP make_pair #define PB push_back #define ALL(x) (x).begin(),(x).end() #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<(n);i++) #define REP2(i,d,n) for(int i=(d);i<(n);i++) #define RREP(i,n) for(int i=(n);i>=0;i--) #define CLR(a) memset((a),0,sizeof(a)) #define MCLR(a) memset((a),-1,sizeof(a)) #define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef vector<LL> VLL; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const LL INFL = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-9; const int DX[]={1,0,-1,0},DY[]={0,-1,0,1}; class MaxMinTreeGame { public: vector<int> edges; vector<int> costs; int findend(vector<int> _edges, vector<int> _costs) { edges = _edges, costs = _costs; VI counts; REP(i, costs.size()) counts.PB(0); int res = 0; REP(i, edges.size()){ counts[i+1]++; counts[edges[i]]++; } REP(i, costs.size()){ if(counts[i] == 1) res = max(res, costs[i]); } return res; } };