AtCoder ABC134 E - Sequence Decomposing を解く [C++]

こんにちは。今夜はABC169です。ここ数日競プロに触ってなかったので、やっとくか！ということで未解答だったABC134に挑戦しました。そしたらE問題が、先日勉強したDPの応用ですらっと解けて嬉しかったので書いています。

o-treetree.hatenablog.com

こちらの記事で取り上げた考え方が使えました。

問題
試行錯誤
DPテーブルの作成
解答
おしまい
参考

問題

↑から転載、一部改変

$N$ 個の整数からなる数列 $A=\{A_1,A_2,⋯,A_N\}$ が与えられます。$N$ 個それぞれの整数に対して、色を $1$ つ選んでその色を塗ります。この時、以下の条件を満たす必要があります: $$ A_i と A_j(i<j) が同じ色で塗られているならば A_i<A_jが成立する $$ 条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。

制約

$1 \le N \le 10^{5}$
$0 \le A_i \le 10^{9}$

入出力

//入力
N
A_1 A_2 ... A_N
//出力
Ans

（見やすさのため数列 $A$ を空白区切り1行で入力するとします（動作は（C++では）同じなので））

入出力例

（例1）

//入力
5
2 1 4 5 3
//出力
2

2, 3 を赤色
1, 4, 5 を青色

で塗ると条件を満たします

試行錯誤

問題の条件を達成するためには

\begin{align} i < j となる A_i, A_j をみたとき、 &A_i < A_j ならば同じ色で塗る\cr &A_i \ge A_j ならば違う色で塗る \end{align}

とすれば良いです。

ちょっとやってみましょう。入力例1を使います。

入力 - 2

色\個数	1
1	2

1つしか数字がないので1つ目の色（赤でも青でもいいけど「色1」とする）で塗ります。

入力 - 1

色\個数	1
1	2
2	1

$2 > 1$ なので1は「色1」で塗ることはできません。よって「色2」を用意してそれで塗ります。

入力 - 4

色\個数	1	2
1	2	4
2	1

$2 < 4$ なので4は2と同じく「色1」で塗ることができます。なぜ「色2」にしないかというのは、『もし次に2が来たら』というのを考えるとわかります。

4を「色1」で塗っておけば『もし次に2が来たら』2は「色2」で塗ることができますが、4を「色2」で塗ってしまうと『もし次に2が来たら』新しい2を「色1」でも「色2」でも塗ることはできない（$2 \ge 2$が真であり、$4 \ge 2$も真であるから）ので新しく「色3」を用意してあげなければなりません。

なんとなく見えてきましたが、満たさなければいけない条件は、言い換えると今作っている表で横に並ぶ数字（同じ色で塗っている）は単調増加（=もだめ）であるということです。

入力 - 3

色\個数	1	2
1	2	4
2	1	3

$4 > 3$ なので3を「色1」で塗ることはできませんが $1 < 3$ なので「色2」で塗ることができます。

入力 - 5

色\個数	1	2	3
1	2	4	5
2	1	3

$4 < 5$ なので5を「色1」で塗ることができます。

よって、入力1（数列 $A = \{2,1,4,5,3\}$）は2色で塗り分けられることがわかりました。

（2, 1, 4, 5, 3）

入出力例のところに書いた塗り方とは違いますがこれも条件を満たしています。

DPテーブルの作成

さて、以上の手順を見ると、毎回、数字を塗る色の判定に使うのは各色の行の一番右の数字です。よって

$$ dp[i] := 既に色 i で塗っている数字の最大値 $$

とすれば良さそうです。

ここで、「新たな数字を適切なところに繋げていって判定に必要な数字だけDPテーブルに出す」というのがちょっと前にやったこれ↓

o-treetree.hatenablog.com

に似てるなと思いました。

↑のときには、単調増加しているDPの列から「$a_p \le x < a_q$ となるところ」をlower_bound関数で見つけていました。今回はどうすれば良いのでしょう。

先ほどの入力例の操作をDPテーブルで書き直すと

入力 - 2

i	0
dp[i]	2

入力 - 1

i	0	1
dp[i]	2	1

入力 - 4

i	0	1
dp[i]	4	1

入力 - 3

i	0	1
dp[i]	4	3

入力 - 5

i	0	1
dp[i]	5	3

つまり入力 $x$ に対して

テーブルの先頭から見ていって $dp[i] < x$ となる $i$ があればdp[i] = xと書き換える
そうでなければ（すべての $i$ について $dp[i] \ge x$）DPテーブルの右端に $x$ を追加する

という操作で解けそうです。もちろん答えはDPテーブルのサイズです。

DPテーブルの右端に追加はpush_backで良いのですが、「テーブルの先頭から見ていって $dp[i] < x$ となる $i$ があればdp[i] = x」をどうやって実現するかが問題です。「降順でのupper_bound」みたいな処理なので、そういう判定ができるようにupper_bound関数をカスタマイズして使います。

o-treetree.hatenablog.com

↑この記事の最後に書いたようにして、upper_boundも判定に使う式をカスタマイズすることができます。具体的には

auto itr = upper_bound(dp.begin(), dp.end(), x, [](int a, int b){
    return a > b;
});

とします。こうすることで $x > dp[i]$ となる最初の $i$ を見つけ、見つからなければdp.end()を返します。

ちなみに、素の(?) upper_bound関数は

upper_bound(dp.begin(), dp.end(), x, [](int a, int b){
    return a < b;
});

という感じになっていて「xより大きい要素のうち最初のものを指すイテレータ」を返します。これの判定式をひっくり返すことで「xより小さい要素のうち最初のものを指すイテレータ」を返すようにする、という発想です。

あとはほぼ、DP（動的計画法）で最長増加部分列(LIS)問題を解くまでの過程メモ - おはやし日記の解法のコピーです。

解答

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define all(v) (v).begin(), (v).end()

int main(){
  int N;
  cin>>N;

  vi dp; //i番目の色で塗っている数字の最大値

  int x;
  for(int i=0; i<N; i++){
    cin>>x;
    auto itr = upper_bound(all(dp), x, [](int a, int b){
      return a > b;
    });
    if(itr!=dp.end()){
      *itr = x;
    }else{
      dp.pb(x);
    }
  }

  cout<<dp.size()<<endl;
}