スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #165 (Div. 1) B : Greenhouse Effect

長さ n の整数列 a が与えられる。
「a の要素を一つ選んで a の好きな位置に挿入する」という操作を繰り返して a をソートしたい。
最小で何回の操作が必要か?

・ 1 ≦ n, m ≦ 5000
・ すべての k = 1, 2, ..., m に対して a[i] = k となる i が存在する

解法

a の最長非減少部分列 a' はそのままにしておいて、a' に含まれなかった要素を挿入しなおすのが最適な戦略。( なぜ?? )
m に関する制約は使わない。

LIS は O(n^2) なり O(n log n) なりで求めればよい。

コンテスト中は ( 昔ほぼ同じ問題を考察したことがあったのに!! ) これが思いつかず、もっとややこしいことを考えていた。

ソースコード

http://www.codeforces.com/contest/269/submission/3065578
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。