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より大きいものの配列
*比較はどちらかの残った要素がゼロになるまでおこる