SRM 554 500pt : TheBrickTowerMediumDivOne
問題概要
数列Xがある。数列を置換してY[i]=max(X[i+1],X[i])の和が最小になるようにしたい。そのような置換のうち辞書順最小のものを求める問題。
考えたこととか
- (やたら早い提出者がたくさんいるのを確認した上でオープン)
- 辞書順最小というと例の方法だけど、今回は判定関数作るの難しそうだなあ。
- しかし、大体ソートされたものになるんじゃないかなあ。
- ソートして元のキーを返すようにする。最後以外のサンプル合った。サンプル弱そうな気配がありそうだし提出者多いこともあるしチャレンジ祭になりそうな気がする。
- ソートされた最小値群は、左側に壁が無いからそれ以外のとスワップできるのか。
- サンプル合った。自信は無かったけど提出。
- あ、これ逆順でも問題ないじゃないか。これでいくらか落とせそう？
- 再提出。
- その後unimordalでありさえすれば良いとか、実は判定関数はソートするだけで計算できたとか知って無力感を得た。
