SRM#664Div.2

今回は色々駄目でレートが減少。Easyすらミスで死んでるのはつらい。冷静にやれば全部通せそうなのもつらい。

Easy:

受け取った数字を文字列にして一要素ずつ比較する。違ってる個数が1個以下なら"happy"

Med:

愚直解が解。a+b+cがわかっているのでdpで十分。再帰は局面の数を見積もればオーダーがわかるので大丈夫そうというのがわかる。dpはその数の組をチェックしたらtrueにしてたどった数の組がわかるために使う。

あとはsortしたりとかあるけど普通にやるだけ。

Hard:

マージソートが再帰なんだから解も再帰やろ(暴論)。もととなる配列があって、それはふたつの結合からできている。そのときに何回比較してるかわかればいい。あとはそれを再帰的にやればいい。

イメージ的にマージソートまんまかもしれない。

r[1, 2, 3, 4] + l[5, 8, 6, 7]

mer[1, 5, 8, 2, 3, 6, 4, 7]

＊同じ配列内で順序が入れ替わることはない。

＊結合前はsize/2以下のものの配列とsize/2より大きいものの配列

＊比較はどちらかの残った要素がゼロになるまでおこる