AtCoder Beginner Contest 026 C - 今日から始める競技プロ日記
はじめに
chokudaiさんが今日の一問としてツイートしていたABC026のC問題を解いてみた。
14分で解いた。目標は20分だったのでまずまず良さげ。
今日の一問！ABC026より、高橋君の給料。今だと300点くらい？
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月20日
これも昨日と同じく「実装出来てほしい」系の問題。緑の人の目標タイムが20分くらい、って感じ。https://t.co/Z2MuWxj8lp
高橋君の給料
社員がN人、社長の社員番号が1である。
社員番号2～Nの社員には必ず直属の上司が一人存在する。
直属の部下がいない社員の給料は1。
直属の部下がいる社員の給料は、max(直属の部下たちの給料) + min(直属の部下たちの給料) + 1。
社長の給料を求めよ。
解き方
末端の社員から給料を求めていけば、 最終的に社長の給料が求められるなーと考えた（当たり前だけど）。
そこで問題なのがどうやってデータを扱うか。
必要な情報はある社員にどんな部下がいるかということ。
ということでこんな感じにまとめてみる。
サンプル2の場合
社員数：7人
| 社員番号 | 直属の上司 |
|---|---|
| 1 | なし |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 3 |
各社員の直属の部下たちをまとめる。
| 社員番号 | 直属の部下たち |
|---|---|
| 1 | 2, 3 |
| 2 | 4, 5 |
| 3 | 6, 7 |
| 4 | なし |
| 5 | なし |
| 6 | なし |
| 7 | なし |
このようにまとめた後、社員番号が一番大きい社員の給料から求めていく。
社員番号7,6,5,4の社員は部下がいないので給料1。
社員番号3の社員の部下は6,7で、max=1, min=1だから、社員番号3の社員の給料は1+1+1=3。
同じように計算して社員番号2の給料は1+1+1=3。
そして最後に社長（社員番号1）の給料は3+3+1=7。
したがって出力すべき答えは7。
コード
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<vector<int>> v(N+1);
vector<int> c(N+1, 1);
for(int i = 1; i < N; i++)
{
int a;
cin >> a;
v[a-1].push_back(i);
}
for(int i = N-1; i >= 0; i--)
{
if(v[i].size() == 0) continue;
int maxv = 1;
int minv = 1<<29;
for(auto& t: v[i])
{
maxv = max(maxv, c[t]);
minv = min(minv, c[t]);
}
c[i] = maxv + minv + 1;
}
cout << c[0] << endl;
return 0;
}
おわりに
良問だった
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 136 E - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 136 に参加。
今日はA～Dまで解いた。
Eが解けなかったので解説動画を見ながら解き方をまとめてみる。
（説明が下手くそなので参考程度に）
参考
公式の解説動画を参考にしました。 いつもありがとうございます。
ABC136の結果
- パフォーマンス：1109
- レート：706→755（+49）
E - Max GCD
長さNの整数列A1, A2, ......, ANが与えられる。
この整数列に対して、Ai に1を足し、Aj から1を引く、という操作を最大でK回行える。
操作後の整数列において、すべての要素を割り切ることができる正の整数の最大値を求める。
例（サンプル1）
与えられた整数列：8 20
// 8から1引き、20に1を足す 8 - 1 = 7 20 + 1 = 21 // 7の倍数になっていることが分かる 7 % 7 = 0 21 % 7 = 0
よって答えは 7 。
解き方
制約が
1 <= N <= 500 1 <= A <= 10^6 1 <= K <= 10^9
となっているので、可能性のあるすべての値を試そうとしてもTLEになる。
そこで、どうやったら計算量を減らせるかを工夫する必要があり、 まず以下の（1）,（2）について考える。
（1）数列全体の和は変化しない
まず、「 Ai に1を足し、Aj から1を引く」という操作を何回行っても、数列全体の和は変化しない。
8 + 20 = 28 //操作を一回行う 8 - 1 = 7 20 + 1 = 21 7 + 21 = 28 //もう一回操作を行ってみる 7 - 1 = 6 21 + 1 = 22 6 + 22 = 28
何回操作を行っても和は28。
よって、数列全体の和はどうやっても変化しない。
（2） 数列のすべての要素の最大公約数は、数列全体の和の約数でもある
数列のすべての要素の最大公約数（公約数）を求めてみると、 その値が数列全体の和の約数でもあることが分かる。
例として次の数列を考える。
14 21 35
この数列の要素はすべて7の倍数。
14 = 7 * 2 21 = 7 * 3 35 = 7 * 5
和を求めてみる。
14 + 21 + 35 = 70
当たり前だが、ここで求められた和である70は7の倍数。
70 = 7 * 10
この足し算はつまりこういうこと。
14 + 21 + 35 = (7 * 2) + (7 * 3) + (7 * 5) = 7 * 10 = 70
よって、数列のすべての要素の最大公約数（公約数）は、数列全体の和の約数でもある。
（1）,（2）より、数列全体の和の約数が答えになる
(1), (2)から、数列全体の和の約数の中に、 操作後の数列のすべての要素の最大公約数が存在することが分かった。
つまり、和の約数をすべて求めて、それぞれが条件を満たすか確認すればいいだけになった。
条件は二つ。
- 操作を行って整数列の最大公約数が、数列全体の和の約数になるかどうか
- 操作回数がK以下で済むかどうか
整数列の各要素をマイナス側とプラス側に分ける
条件を満たすか調べる。
例として次の整数列について考える。
1 1 2 2 3 5
和を求める。
1 + 1 + 2 + 2 + 3 + 5 = 14
和の約数を求める。
14の約数：1, 2, 7, 14
よって、答えは1 2 7 14のどれかである。
次に、整数列の要素をプラス側とマイナス側に分ける。
つまり、操作において+1する側と-1する側に分けるということ。
先ほどの整数列をもう一度見る（ちなみにソート済みであることが重要）。
1 1 2 2 3 5
ここで、この整数列の最大公約数を14にしたいとする。
つまり、各整数を14の倍数にしたい。14 × 0 = 0より0にしてもよい。
例えば左半分の1 1 2を0にして、右半分2 3 5を14にしようとする。
1 1 2 | 2 3 5
境界は真ん中
左半分 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 合計A = -4 右半分 14 - 2 = 12 14 - 3 = 11 14 - 5 = 9 合計B = 32
一度の操作では+1と-1を一回ずつ行うので、T回操作を行うと、合計でA=-T、B=Tであり、-A = Bとなるはずである。
つまり、-A != Bの場合はその操作は間違いである。
次に、左側と右側の境目を一つ右にずらしてみる。
1 1 2 2 | 3 5
左側 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 0 - 2 = -2 合計A = -6 右側 14 - 3 = 11 14 - 5 = 9 合計B = 20
これでも-A != Bであるため、これも間違いである。
さらに、境目を一つ右にずらしてみる。
1 1 2 2 3 | 5
左側 0 - 1 = -1 0 - 1 = -1 0 - 2 = -2 0 - 2 = -2 0 - 3 = -3 合計A = -9 右側 14 - 5 = 9 合計B = 9
このとき-A = Bであり、この操作は実行可能である。
また、このときの操作回数はB回となる。
このようにして、 ある最大公約数にするために操作が何回必要が求めることができる。
あとはこの解き方を実装すればよい（難しい......）。
set
解説でsetが使われていたのでちょっと調べてみた。
以下の記事を参考。
コード
解説動画で実装していたsnukeさんのコードを参考。
おわりに
考え方はなんとなくわかったけど、 実装はできる気がしない。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 137 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 137 に参加。
D問題はコンテスト中に解けなかったので、 公式の解説動画を見ながら自分なりにまとめてみる。
D - Summer Vacation
N件のアルバイトがあって、i 件目のアルバイトを請けると、 Ai 日後に Bi の報酬を得る。
今日から（0日目）から M 日後までに得られる最大の報酬を求める。
ただし、一日一件のアルバイトしか請けることができず、 一度請けたアルバイトはその後選ぶことはできない。
参考
公式の解説動画を参考にしました。ありがとうございます。
条件の厳しいところから考えると良いらしい
この問題を見たとき一瞬DPかなと思ったけど、 制約が
N <= 10^5 M <= 10^5
だったのでだめぽかった。
それ以外だと貪欲法で解けそうだなと考えるところまではいった。
こういう問題では条件の厳しいところから考えていくのがセオリーらしい。
この問題では考えるポイントが、一つのアルバイトに対して A と B の二つがあって、 そのまま単純にアルバイト同士を比較できない。
だけどうまくやれば報酬のみでアルバイト同士を比較できるようになる。
解き方
例題（サンプル1）
N = 5 M = 3 A : 1 1 1 2 2 B : 2 3 4 1 3
M日目までに得ることができる報酬を求める。
解き方として期限の一日前から選択するアルバイトを考えていくことが重要。
サンプルだと3日目が期限なので、 2日目に選択するアルバイトを考える。
この解き方の嬉しいところは、 2日目に選択できるのが「1日後に報酬が貰えるアルバイト」のみに限定されることである。
そうすると、「1日後に報酬が貰えるアルバイト」の中から報酬が最も高いアルバイトを選択すれば良いだけになる。
次に、1日目に選択するアルバイトを考える。
1日目に選択できるのは「2日後までに報酬が貰えるアルバイト」である。
同じように「2日後までに報酬が貰えるアルバイト」の中から報酬が最も高いアルバイトを選択すれば良い。
これを繰り返すことでこの問題が解ける。
コード
公式の解説動画を参考に書きました。ありがとうございます。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
// ある日まで行えるアルバイトのグループとして格納していく
// 最大でM日まで
vector<vector<int>> jobs(M);
for(int i = 0; i < N; i++)
{
int A, B;
cin >> A >> B;
// AがMを超えている場合はそのアルバイトは絶対にできない
if(A > M) continue;
// M-A日まで行えるアルバイト
jobs[M - A].push_back(B);
}
// 優先度付きキュー
// 追加と最大値を取り出す機能を持っている
priority_queue<int> q;
long long int ans = 0;
// 後ろから見ていく（この日まで行うことができるアルバイトグループを見ていく）
// 例：M-1日目には、一日後に報酬がもらえるアルバイトの中で一番報酬が大きいアルバイトを選ぶ
// また、一日後に報酬がもらえるアルバイトはM-2日目にも行えるのでそのままqueueに残しておく
for(int i = M-1; i >= 0; i--)
{
// jobsのi番目の報酬の配列をpriority_queueに突っ込んでいく
for(int b : jobs[i])
{
q.push(b);
}
if(!q.empty())
{
// qの最大値を取り出す
// 現在行うことができるアルバイトの中で報酬が最大のものを選択
ans += q.top();
// 取り出した値を削除、一度選択したアルバイトは二度と請けられない
q.pop();
}
}
cout << ans << endl;
return 0;
}
おわりに
さぼらないで精進しないとレートは上がらないなーと思いながら早数か月。 あと、説明ももっとうまくなりたい。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 137 C - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 137 に参加。
今日は A ～ C まで解いた。
C問題はかなりごり押しな実装をして解いてしまったけど、 解説動画で「mapを使うと簡単に実装できますよ」と教えてもらったので、 mapを使った実装方法を自分なりにまとめておく。
結果
- パフォーマンス：792
- レート：755 → 759 （+4）
C - Green Bin
N個の文字列が与えられる。
その中でアナグラムになっている文字列の組はいくつあるか。
参考
公式の解説動画を参考にしました。ありがとうございます。
map
mapはkeyとvalueをワンセットにして格納できる辞書みたいなデータ構造らしい。
とりあえず以下の記事を参考。
mapの利点はたくさんあるみたいで、 データの扱いやすさと探索の速さが特徴みたい。
私が一番驚いたことが、 存在しないkeyにアクセスすると、 自動でそのkeyが登録されるらしい。 自分で頑張ってそういう配列を実装しようとすると大変。
あと、for文を使ってmapにアクセスするときは以下の記事の内容も参考にしたい。
autoの話はこちらを参考。
コード
公式の解説動画を参考に書きました。ありがとうございます。
（スペースとtabが混ざってる気がする）
#include <iostream>
#include <string>
#include <map> // mapのために必要
#include <algorithm> // sortのために必要
using namespace std;
int main()
{
int N;
cin >> N;
// "Key"は string, "Value"は long long int
map<string, long long int> mp;
for(int i = 0; i < N; i++)
{
string s;
cin >> s;
// 入力した文字列をソートしてKeyとして利用
// ソートすればアナグラム同士の文字列は同じ文字列になる
sort(s.begin(), s.end());
// 文字列をKeyとしてmapに登録
// 未登録の文字列Keyも自動で登録される（すごい）
// 初期値は0になるので+1している
// 同じ文字列の数を数えている
mp[s]++;
}
long long int ans = 0;
// mpの要素を一つずつ取り出していく
for(auto& p : mp)
{
// Valueを取り出してkに入れる
long long int k = p.second;
// k個の中から2つ取り出す方法は```k×(k-1) / 2```通り
ans += (long long int)(k * (k-1) / 2);
}
cout << ans << endl;
return 0;
}
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 054 D - 今日から始める競プロ日記
はじめに
AtCoderの400点を埋めたい。
今日はABC054のD問題を解く。
と言いながら結局解説を読んだので 自分なりにまとめるだけ。
D - Mixing Experiment
物質Cを作る。
物質Cは物質Aと物質BをMa : Mbの比率で混ぜることで生成できる。
ここで、N種類の薬品が与えられる。
各薬品 i は、物質Aをaiグラム、物質Bをbiグラム含み、価格はciである。
物質Cを作るのに必要な最小予算を求める。
公式解説
まず、こっちを読んだほうがいい。
https://img.atcoder.jp/abc054/editorial.pdf
私の記事では図を載せているので、その分だけ分かりやすくなっていると信じたい。
解き方
DPを使って解く。
考え方として、それぞれの薬品においてその薬品を加えた場合と加えなかった場合の重さと最小予算を記録していく。
したがって、次のような三次元配列を作る。
dp[i][ca][cb] : 1～i 番目の薬品の組み合わせ（入れるor入れない）の結果、物質Aがcaグラム、物質Bがcbグラムになり、そのときの最小予算を更新していく
このとき、最小予算を更新していくため、dpのすべての値を無限大で初期化する。 しかし、dp[0][0][0]だけは0で初期化（i=0のときは薬品はまだ一つも加えてないから重さも予算も0）。
表にあらわすと以下の図のようになる。
例として入力例1を解いてみる。
入力例1
N=3 //薬品の種類 Ma : Mb = 1 : 1 //物質Cを作るための物質Aと物質Bの比率 a1=1, b1=2, c1=1 a2=2, b2=1, c2=2 a3=3, b3=3, c3=10
dp配列において、i 番目の要素から i+1 番目の要素を更新する。
更新方法以下の二つ。
1 : 薬品 i を加えない場合
dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
薬品を加えないので重さは変わらず、i 番目の予算を引き継ぐかどうかだけを判断している。
2 : 薬品 i を加える場合
dp[i+1][ca+A[i]][cb+B[i]] = min(dp[i+1][ca+A[i]][cb+B[i]], dp[i][ca][cb]+C[i])
薬品を加えるため重さが変化する。 そのため、i+1 番目における変化後の重さ（ca+A[i] と cb+B[i] ）の最小予算を更新する。
この更新の様子を表で書いてみると以下の図のようになる。
まず、i=0からi=1を更新。つまり、薬品1を加える場合と加えない場合の最小予算の更新。
次に、i=1からi=2を更新。つまり、薬品2を加える場合と加えない場合の最小予算の更新。
最後に、i=2からi=3を更新。つまり、薬品3を加える場合と加えない場合の最小予算の更新。
以上の計算より、結果は以下のようになる。
この表を見ると、条件Ma : Mb = 1 : 1を満たしているなかで最小予算は 3 である（ca=3, cb=3のとき）。
このようにしてDPを用いて問題を解くことができる。
コード
コードは公式の解説PDFにのっているのでそちらを参考にする。ありがたい。
https://img.atcoder.jp/abc054/editorial.pdf
おわりに
動的計画法は少しずつ分かってきた気がするけど、 いざ問題を解こうとすると、 どう解けばいいか分からない。 まだまだ理解が足りないらしい。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 135 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 135 に参加（2019/07/27）。
今回はCまで解いた。
DはDP（動的計画法）の典型問題らしかったけど分からんかった。
なので解説動画を見て自分なりにまとめてみる。
参考
AtCoder Beginner Contest 135 の公式解説動画。ありがたい。
結果
- パフォーマンス：882
- レート：683 → 706 (+23)
D - Digits Parade
数字（ 0 - 9 ）と ? からなる文字列 S が与えられる。
? は数字に置き換えることができる。
その文字列を整数とみなしたとき、13 で割って 5 余る数は何通りあるか数える問題。
答えは大きくなる可能性があるから10^9+7で割った余りを答える。
各桁ごとに余りを考える
文字列 S は最大で長さ10^5になるので、
何も考えずに全通りを 13 で割って余りが 5 になるかどうか数えると、
計算量は最大で10^(10^5)になるから時間内には解けない。
そのため解き方を工夫する必要がある。
そこで、各桁ごとに余りを考えていくことが大切。
例として274を13で割ったときの余りを考えてみる。
まず、274は1×4と10×7と100×2の3つに分解できる（これが各桁ごとに見るということ）。
この3つの値をそれぞれ13で割って余りを求める。
ここで求められた各桁の余りの和を求める。
5 + 5 + 4 = 14
この合計を13で割って余りを求めると、14 % 13 = 1で余りは1となる。
つまり、274を 13 で割ると余りは 1 ということになる。
? を含んでいる場合
例として?44について考える。
?44についても先ほどと同様に考えてみる。
上の図のように、?44を 13 で割ると、余り = 4 + 1 + ( ? × 9 )となる。
このとき、? に 0 ～ 9 を入れることで、全通りの余りを求めることができる。
余りの計算はこんな感じ。
4 + 1 + 0 = 5 → 5 4 + 1 + 9 = 14 → 1 4 + 1 + 18 = 23 → 10 4 + 1 + 27 = 32 → 6 4 + 1 + 36 = 41 → 2 4 + 1 + 45 = 50 → 11 4 + 1 + 54 = 59 → 7 4 + 1 + 63 = 68 → 3 4 + 1 + 72 = 77 → 12 4 + 1 + 81 = 86 → 8
このようにして、? を含んだ整数でも余りを求めることができる。
動的計画法（DP）を用いて解く
動的計画法を用いると効率よく計算を行うことができる。
さっき例としてあげた274 % 13は、
4 % 13 = 4 70 % 13 = 5 200 % 13 = 5
より、
4 + 5 + 5 = 14 14 % 13 = 1
という計算を行って、余りが 1 ということが分かった。
これを以下のように表で表す。
（この表では、0 + 4 + 5 + 5 = 14 → 1という計算が行われている。）
この表から分かる通り、一つ前の桁の余りの個数から、次の桁の余りの個数を計算して求めることができる。
一度計算した結果を記録していくことで、効率的に全通りの計算を行うことができる。
計算量のオーダーはおそらくO(N)のはず（違うかな？）。
? を含んだ整数のDP
先ほど例にあげた?44でも、このDPで計算してみる。
? がある場合、? に 0～9 を入れて10通りにおける余りの計算を行うことになる。
これは以下のように表で表す。
また、この余りの計算は余りの数分だけ行う（つまり 0 ～ 12 の 13回）。
コード
コードは公式の解説動画を参考にしました。
ありがとうございます。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
string S;
cin >> S;
// ( mod 13 )
const int N = 13;
//dp配列
vector<int64_t> dp(N);
// 0%13=0なので余り0の個数を1にする
dp[0] = 1;
//答えはこれで割った余りを出力
int64_t mod = 1e9+7;
//何の位かを表す（1の位、10の位、100の位、......）
int64_t mul = 1;
//文字列を一桁ずつ見ていく（1の位から見ていくよ）
for(int i = S.size()-1; i >= 0; i--)
{
//更新したdp配列
vector<int64_t> nextDP(N);
char c = S[i];
if(c == '?')
{
//'?'が0-9の場合をそれぞれ考えていく
for(int k = 0; k < 10; k++)
{
//各余りの個数を更新
for(int j = 0; j < N; j++)
{
//一つ前のdp配列のインデックス j から、
//次のdp配列のインデックスは K * mul 分だけずれる
//（上で説明した表の"+4"みたいなこと）
nextDP[(k * mul + j) % 13] += dp[j];
nextDP[(k * mul + j) % 13] %= mod;
}
}
}
else
{
//文字cをintに変換
int k = (int)(c - '0');
//各余りの個数を更新
for(int j = 0; j < N; j++)
{
//一つ前のdp配列のインデックス j から、
//次のdp配列のインデックスは K * mul 分だけずれる
//（上で説明した表の"+4"みたいなこと）
nextDP[(k * mul + j) % 13] += dp[j];
nextDP[(k * mul + j) % 13] %= mod;
}
}
//dp配列を更新
dp = nextDP;
//次の位に更新
mul *= 10;
//ここで余りをとっても結果は変わらない
mul %= N;
}
//余り5の個数を出力
cout << dp[5] << endl;
return 0;
}
おわりに
もっと簡単にスマートに説明できそう。
おそらく私が完璧に理解できていない。
今日から始める競プロ日記のまとめページ
AtCoder Beginner Contest 134 E - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest (ABC) 134 E を解いてみた。
E - Sequence Decomposing
数列 A1, A2, ...... , AN が与えられる。
このとき、それぞれの整数を以下の条件を満たすように色を塗っていく。
同じ色で塗られている整数 Ai と Aj (i < j) において、Ai < Aj が成り立つ
参考
解説動画いつも分かりやすくてありがたい。
今回の解き方
まず、例として以下の数列を考える。
2 1 4 5 3
まず先頭から値を一つずつ順番に見ていって、条件に合うように空の配列に入れていくとする。
流れは以下のようになる。（B[0], B[1]は空の配列）
初期状態 B[0] : 空 B[1] : 空 ...... ...... B[M] : 空 一つ目の値：2 B[0] : 2 ← 入れる 二つ目の値：1 B[0] : 2 B[1] : 1 ← 入れる（2 < 1 だからA[0]には入れられない） 三つ目の値：4 B[0] : 2 4 ← 入れる B[1] : 1 四つ目の値：5 B[0] : 2 4 5 ← 入れる B[1] : 1 五つ目の値：3 B[0] : 2 4 5 B[1] : 1 3 ← 入れる
このとき、配列の数（B[0], B[1]の二つ）が色の数ということになる。
よって答えは2。
しかし、この解き方では計算量がO(N^2)くらいになると思うので間に合わない（たぶん）。
そこで空の配列は一つだけにして考えてみる。
行う処理は以下の二つ。
- 次に入れる値が配列に格納されているどの値よりも小さければ先頭にいれる
- それ以外の場合は、次に入れる値より小さくて一番大きな値を書き換える
解き方はこんな感じ。
初期状態 B : 空 一つ目の値：2 B : 2 二つ目の値：1 B : 1 2 ← 前から入れる 三つ目の値：4 B : 1 4 ← 2を書き換える（4より小さくて一番大きな値である2を書き換え） 四つ目の値：5 B : 1 5 ← 4を書き換える（5より小さくて一番大きな値である4を書き換え） 三つ目の値：3 B : 3 5 ← 1を書き換える（3より小さくて一番大きな値である1を書き換え）
Bの長さが答えとなるので（つまり色の数）、答えは 2。
このとき、Bは常に昇順になっている。
よって、二分探索的なものを使うことができるので計算量はO(NlogN)となる。
ここでいう二分探索的なものがlower_bound()である。
lower_bound()を使えば、ある値以上で一番小さい値のインデックスを求めることができる。
これにより、先の例で示したような「Xより小さくて一番大きな値であるYを書き換え」という処理を行うことができる。
また、配列の先頭に値を入れるという処理はdeque（デックと読むらしい）を使うことで可能となる。
dequeは両端のどちらからでも値を出し入れすることができるvectorの拡張版らしい。
push_front()で配列の先頭に値を入れることができる。
コード
コードはAtCoder公式の解説動画を参考にさせていただきました。
ありがとうございます。
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> a(N);
for(int i = 0; i < N; i++)
{
cin >> a[i];
}
//両端キュー、前からも値を入れることが可能
//昇順に並べていく
deque<int> d;
for(int i = 0; i < N; i++)
{
//a[i]以上の値の中で一番小さい値のインデックスを返す
int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
//a[i]以上の値が存在しないときはキューの一番最初に入れる
//（つまり別の色を塗る）
if(p == 0)
{
d.push_front(a[i]);
}
//a[i]以上の値より一つ左隣り（インデックスが一つ小さい）値を書き換える
//つまりa[i]より小さい値の中でで一番大きな値を書き換える
//（同じ色で塗るということ）
else
{
d[p-1] = a[i];
}
}
//dの長さが色の数になっている
//（別の色を塗るたびに先頭に挿入しているから）
int ans = d.size();
cout << ans << endl;
return 0;
}
おわりに
今日は自分にとってちょっと難しめの問題を解いてみた。
本番で解けたら嬉しい。
