エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
TopCoder Marathon Match 120 "ReversalSort" - iwashi31’s diary
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
TopCoder Marathon Match 120 "ReversalSort" - iwashi31’s diary
問題概要 長さ N の数列が与えられる。下記の操作を任意回行って、コストをできるだけ抑えつつ昇順ソー... 問題概要 長さ N の数列が与えられる。下記の操作を任意回行って、コストをできるだけ抑えつつ昇順ソートせよ。 数列中の連続する区間を好きに選んで、その区間内の数列を反転する。コストは floor((区間の長さ)X)(X は入力で与えられ、0.0 ≦ X ≦ 3.0)。 全文はこちら。 解法 以下の 4 つの解法を試して、一番良かったものを採用する。 アルゴリズム概要 有効な X ① バブルソート 2.2 ~ ② 選択ソートっぽいやつ ~ 0.1 ③ 選択ソートっぽいやつ改 1.8 ~ 2.3 ④ 隣り合う要素の差の合計を最小化する貪欲 0.1 ~ 1.8 ① バブルソート X が大きい場合、バブルソートが最適解になる。 最適解になるのは X ≧ 2.71 くらいからのはずだが、他のアルゴリズムがかしこくないせいか X = 2.2 くらいでこれが採用されることもあった。 1 1 1 0 3