SRM715 div2

先日のSRMに出ました

SRMに出るのは初めてでいろいろ戸惑った・・

easy

4重ループをかくとACする

medium

+-+とか-+-とかいうのは明らかに無駄でやらないほうがマシなのでありえるのは

--..+++か++..----のみだけどこれは片方だけやっても最大-最小は変わってないので

どちらかのみを実行するとしてよいから

結局+と-の個数を数えて大きいほうが答え

hard

a1[0]は必ず木の根になる(これをrとおく)

a2の要素のうち、rがあるindexより左の要素は、根の左の部分木

同様にrがあるindexより右の要素は根の右の部分木

これにより根の左と右の部分木のサイズが分かるので、a1,a3を分割できる

この時点で整合性がとれていない場合はImpossible(setにぶちこんで==とかでかくにんすればいいかな)

あとは再帰関数で左と右の部分木に対してチェックしていく

このとき{s[0],s[2],s[4]},{s[1],s[3],s[5]}は{"pre","in","post"}に等しいという謎に見える制約が効いてきて、6つのvectorを頑張って並び替えて同じ関数を呼ぶだけでよくなる

後は左の部分木と右の部分木が両方PossibleだったらPossible,そうでなければImpossibleを返すようにすればよい

ただし、空のvectorが渡されてきた場合はPossibleを返すようにしないと根を確保しようとする時点でout of rangeで落ちる

div2で2位になってレートが1765になった(レーティングシステムなんとかして)

次はdiv1でぼっこぼこにされてきます