緑になりたいので過去問をやっています。銅相当を全部解くか、Cをすべて埋めるか考えてましたが、考えるのがめんどくさくなったのでC問題を埋めていました。
今回はABC165C問題です。このコンテストはD問題が銅色で、C問題が緑相当という不思議な回でした。
目次
1.問題
広義単調増加する数列に対してクエリが投げられ、条件を満たすときに与えられる特典の最大値を求めよという問題。
2.方針
全探索です。問題は数列の生成をどうするかというところ。
ただの数列ならばnext_permutationを使えばできますが、そもそも計算量的に無理。数列の長さが8ぐらいなら、数列を生成して広義単調増加しているか調べて・・・とかは間に合う気がしますが。
なので、再帰関数を用いてうまいこと実装します。
3.コード
4.解説
上記2つを参考にして実装しています。
数列生成は次の部分。
void dfs(vector<int> A) {
if (A.size() == n + 1) {
int score = 0;
/*得点計算が入る*/
ans = max(score, ans);
return;
}
A.push_back(A.back());
while (A.back() <= m) {
dfs(A);
A.back()++;
}
}
vectorの初期化の関係上、sizeがn+1になると数列ができたとして得点計算します。また、数列の得点計算に使う部分はvector内の1番目から最後までになるため、得点計算をするときにaとbをデクリメントする必要がありません。
5.おわりに
動画内で再帰を書くときに重要なことは
- 終了条件
- どうしたら次に繋がるか
らしいです。
そうと言っても再帰を考えるのは難しい・・・。