緑になりたいので過去問をやっています。銅相当を全部解くか、Cをすべて埋めるか考えてましたが、考えるのがめんどくさくなったのでC問題を埋めていました。
今回はABC165C問題です。このコンテストはD問題が銅色で、C問題が緑相当という不思議な回でした。
目次
1.問題
広義単調増加する数列に対してクエリが投げられ、条件を満たすときに与えられる特典の最大値を求めよという問題。
2.方針
全探索です。問題は数列の生成をどうするかというところ。
ただの数列ならばnext_permutationを使えばできますが、そもそも計算量的に無理。数列の長さが8ぐらいなら、数列を生成して広義単調増加しているか調べて・・・とかは間に合う気がしますが。
なので、再帰関数を用いてうまいこと実装します。
3.コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| #define rep(i, n) for (int i = 0; i < (n); i++) | |
| #define rep2(i, s, n) for (int i = (s); i < (n); i++) | |
| using namespace std; | |
| using ll = long long; | |
| using P = pair<int, int>; | |
| int n, m, q, ans = 0; | |
| int a, b, c, d; | |
| struct t { | |
| int a, b, c, d; | |
| }; | |
| vector<t> v; | |
| void dfs(vector<int> A) { | |
| if (A.size() == n + 1) { | |
| int score = 0; | |
| for (auto& [aa, bb, cc, dd] : v) { | |
| if (A[bb] - A[aa] == cc) score += dd; | |
| } | |
| ans = max(score, ans); | |
| return; | |
| } | |
| A.push_back(A.back()); | |
| while (A.back() <= m) { | |
| dfs(A); | |
| A.back()++; | |
| } | |
| } | |
| int main() { | |
| cin >> n >> m >> q; | |
| rep(i, q) { | |
| cin >> a >> b >> c >> d; | |
| v.push_back(t{a, b, c, d}); | |
| } | |
| dfs(vector<int>(1, 1)); | |
| cout << ans << endl; | |
| return 0; | |
| } |
by 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.おわりに
動画内で再帰を書くときに重要なことは
- 終了条件
- どうしたら次に繋がるか
らしいです。
そうと言っても再帰を考えるのは難しい・・・。