YKpages

ロボット分野で勉強したことのまとめ

AtCoder Beginner Contest 006 D - 今日から始める競プロ日記

AtCoder

はじめに

chokudaiさんの今日の一問に挑戦。

AtCoder Beginner Contest 006 D ( ABC 006 D ) 。

解説を読みながら自分なりにまとめていきます。

D - トランプ挿入ソート

数字が書かれたN枚のカードが並んでいる。

以下の操作を行う。

操作：一枚カードを抜き取り、任意の位置に挿入

カードを昇順に並べるために必要な操作の最小回数を求めよ。

atcoder.jp

解いた方針

解説を参考。

単純に並び替えを全通りやっていたらきりがないので工夫が必要になる。

ここでとりあえず挿入ソートについて調べてみる。

すると、 「一般に計算量のオーダはO(N^2)と遅いが、ある程度ソート済みの配列に対しては高速」 みたいなことが書かれていた。

ja.wikipedia.org

そこから考えられることとして、 挿入ソートは「与えられた配列がどの程度ソートされているか」によって計算量が変わってくるということが分かる。

つまり、 与えられた配列の中でソート済みの要素がいくつあるか数えれば良さそうだということが分かる。

たとえば、

1 3 5 2 4 6

という配列が与えられたとする。

この中でソート済みの要素の例として以下のような部分列がある。

1 3 5     6

この 1, 3, 5, 6 は昇順に並んでいる。

さらにここから、残りの 2, 4 を適切な場所に挿入すればすべての要素がソートされることが分かる。

つまり、必要な操作回数は2回。

以上のことから、 ソート済みの部分列の中で、最大の部分列の長さを求められれば答えが分かる ということになる。

動的計画法を用いて部分列の長さを計算

ソート済みの部分列の長さを求める計算にも工夫が必要。

愚直にやるとたぶんTLEする。

そこで動的計画法（DP）を使う。

まず、DP配列を作る（長さはN+1やN+2にする）

このDP配列では、 ソート済みの部分列の長さごとに管理をしていく。

  • 長さ1の部分列の最小値はdp[1]
  • 長さ2の部分列の最小値はdp[2]
  • 長さ3の部分列の最小値はdp[3]
  • ......

このようなDPをして何が分かるかというと、 さっき言った通り、ソート済みの部分列の中で最大の長さが求められる。

例として以下の配列を考える。

1 3 5 2 4 6

dp配列を初期化

[0]=-INF, [1]=INF, [2]=INF, [3]=INF, [4]=INF, [5]=INF, [6]=INF

各入力の値cに対して、dp[i] < c < d[i+1]を満たすか調べ、 満たした場合は更新する。

1が入力される。

[0]=-INF < 1 < [1]=INFより、長さ1の部分列の最小値は[1]=1になる

[0]=-INF, [1]=1, [2]=INF, [3]=INF, [4]=INF, [5]=INF, [6]=INF

3が入力される。

[1]=1 < 3 < [2]=INFより、長さ2の部分列の最小値は[2]=3になる。

[0]=-INF, [1]=1, [2]=3, [3]=INF, [4]=INF, [5]=INF, [6]=INF

5が入力される。

[2]=3 < 5 < [3]=INFより、長さ3の部分列の最小値は[3]=5になる。

[0]=-INF, [1]=1, [2]=3, [3]=5, [4]=INF, [5]=INF, [6]=INF

2が入力される。

[1]=1 < 2 < [2]=3より、長さ2の部分列の最小値は[2]=2になる。

[0]=-INF, [1]=1, [2]=2, [3]=5, [4]=INF, [5]=INF, [6]=INF

4が入力される。

[2]=2 < 4 < [3]=5より、長さ3の部分列の最小値は[3]=4になる。

[0]=-INF, [1]=1, [2]=2, [3]=4, [4]=INF, [5]=INF, [6]=INF

6が入力される。

[3]=4 < 6 < [4]=INFより、長さ3の部分列の最小値は[4]=6になる。

[0]=-INF, [1]=1, [2]=2, [3]=4, [4]=6, [5]=INF, [6]=INF

以上の計算より、ソート済みの部分列の最大の長さは4であることが分かった。

N - 4 = 6 - 4 = 2より、答えは2。

lower_bound を使って高速化

上で説明したdpは愚直にやるとO(N^2)となり遅い（一応それでもACはできた）。

そこでdp配列がソート済みであることを利用してlower_boundを使う。

lower_boundは二分探索で更新するべき場所を探してくれるのでO(NlogN)となる。

lower_boundの分かりやすい説明は以下の記事。ありがたい。

qiita.com

lower_boundは、「ソート済みの配列」と「Keyとなる値」を与えると、 Key以上で一番小さい値を配列の中から探してくれる。

ちなみに返り値はイテレータ。

コード

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1<<29;
 
int main()
{
        int N; cin >> N;
        vector<int> dp(N+2, INF); dp[0] = -INF;
 
        for(int i = 0; i < N; i++) {
                int c; cin >> c;
                auto itr = lower_bound(dp.begin(), dp.end(), c);
                dp[itr-dp.begin()] = c;
        }
 
        int ans = 0;
        for(int i = 0; i < N+1; i++) {
                if(dp[i] != INF) ans = N-i;
        }
 
        cout << ans << endl;
        return 0;
}

おわりに

難しかった。

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com