これ400ptか…。
https://community.topcoder.com/stat?c=problem_statement&pm=16794&rd=18497
問題
数列を用いて2人でゲームを行う。
数列長が1になるまで、交互に以下の手番を行う。
自分の手番では、連続する2要素を選択する。先手の場合は大きい方、後手の場合は大きい方を取り除く。
先手は最後に残る値が大きく、後手は最後に残る値が小さくなるようにしたい。
両者が最適手を取ると、残る値は何か。
解法
本番では、残る値vを総当たりし、元の数列をv以上か未満かで1/0に置き換えて、先手は1、後手は0を残すようにふるまうシミュレーションをした。
この問題はもっと短く解くこともできるようだ。
最後の手番では、両端の値が残るので、最後が先手後手どちらかによって小さいor大きい方を返す、でokとのこと。
例えば先手の場合、先頭要素が次の要素より大きいなら、先頭要素を消す真似はむざむざしないし、先頭要素が次の要素より小さいなら、そもそも消えないし…で両端の要素はお互いに消しにかからない、って理解でいいかな？
class MinMaxGame { public: int lastNumber(vector <int> A) { if(A.size()%2==0) return min(A[0],A.back()); else return max(A[0],A.back()); } }
まとめ
こういうのさっくり思いつかないな。
本番愚直なシミュレーションで通ったのでまぁよかったけど…。
