ABC165 C問題復習

投稿者: | 2021年4月17日

緑になりたいので過去問をやっています。銅相当を全部解くか、Cをすべて埋めるか考えてましたが、考えるのがめんどくさくなったのでC問題を埋めていました。

今回はABC165C問題です。このコンテストはD問題が銅色で、C問題が緑相当という不思議な回でした。

1.問題

C - Many Requirements

広義単調増加する数列に対してクエリが投げられ、条件を満たすときに与えられる特典の最大値を求めよという問題。

2.方針

全探索です。問題は数列の生成をどうするかというところ。

ただの数列ならばnext_permutationを使えばできますが、そもそも計算量的に無理。数列の長さが8ぐらいなら、数列を生成して広義単調増加しているか調べて・・・とかは間に合う気がしますが。

なので、再帰関数を用いてうまいこと実装します。

3.コード

4.解説

ABC165 解説

上記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.おわりに

動画内で再帰を書くときに重要なことは

  • 終了条件
  • どうしたら次に繋がるか

らしいです。

そうと言っても再帰を考えるのは難しい・・・。

6.参考文献

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください