SRM551 div.1 250 ColorfulChocolates

練習会に出て1完。Medは解けそうでダメだった。

問題

数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。

解法

一箇所を固定してシミュレーションすればよい。
具体的にはある位置を決めたときに、左と右を1個ずつ見ていって、swap回数がなくなるまで、近い順に貪欲に決めた位置までswapしていけばよい。
ただし、1個つめると、次に同じ側で詰めるときはswap回数が1少なくなることに注意。
以下のコードのように左・右と1個ずつ見ていっても良いが、移動させる距離を列挙してソートする解法の方が実装が楽(hamkoさんの解法)。

計算量

以下のコードはO(N^2)
ソートする手法はO(N^2 log N)

コード

感想

左右から箱を詰めていくシミュレーションの問題、よくありそうなので、距離でソートする実装は心に留めておきたい