CSA Round #82 Restricted Arrays

問題概要

CS Academy
長さの数列とが与えられる。以下の条件を満たす数列はいくつあるか求める。
条件1. is minimum
条件2.
条件3. を満たすについて、ならば,ならばが成り立つ。

制約

考えたこと

まず条件1.なんですが、数列の最大値が最小のものになっているという感じだと考えられます(いい感じに訳せません)。2つ目のテストケースを見てみると、数列では条件1.を無視すると以下のような候補が考えられます。

下2つも条件2,3を満たすがの値がとることのできる最小値ではないので全ての条件を満たすのは上2つのみとなります。

問題文の理解はできましたが、なかなか考察は進みません。
こういう考えやすいケースから考え始めるのが良さそうです。 まず、の時これは1つ目のテストケースですが、この場合条件3は考慮しなくていいので、全てに1を使うことで条件1,2を満たしになります。

次にの時を考えてみます。この場合は条件3の与える範囲が数列全体なので、数列に含まれる数字の種類の数だけ用いれば数列を構成できそうです。つまり　からの範囲に現れる数字の種類　になります。

ではの場合はどうでしょうか。この時、からの範囲とからの範囲についての時と同様に考えればいいと思います。それぞれの区間で必要な種類数のmaxをとれば全体としてのが求まります。

なので与えられたについて、幅の個の区間に対してその区間に何種類の数字が使われているのかを調べるといいです。 実装では、幅の区間についてしゃくとりのように先頭から見ていくような感じにしました。

ここまでで、使える数字の種類()が求まったので、に何通りの候補があるかを調べていきます。

は自明に通り。に何通りあるを決める時、とその直前の個を見て、と同じ数字が直前の個の中にあるならば、そうでないならば直前個にある数字の種類　となるはず。

全てのを求め終わったら、をを取りながら計算することで答えが出ます。

提出コード

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  int maxB = 0;
  map<int, int> mp;
  rep(i, k) mp[a[i]]++;
  cmax(maxB, (int)mp.size());

  loop(i, k, n) {
    mp[a[i]]++;
    mp[a[i - k]]--;
    if (mp[a[i - k]] == 0) mp.erase(a[i - k]);
    cmax(maxB, (int)mp.size());
  }

  int ans = 1;
  map<int, int> m;
  vector<int> b(n);
  b[0] = maxB;
  m[a[0]] = 1;
  loop(i, 1, k) {
    if (m.count(a[i])) {
      m[a[i]]++;
      b[i] = 1;
    } else {
      b[i] = maxB - (int)m.size();
      m[a[i]]++;
    }
  }
  loop(i, k, n) {
    m[a[i - k]]--;
    if (m[a[i - k]] == 0) m.erase(a[i - k]);
    if (m.count(a[i])) {
      b[i] = 1;
    } else {
      b[i] = maxB - (int)m.size();
    }
    m[a[i]]++;
  }
  rep(i, n) {
    ans *= b[i];
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

感想

こういう問題は苦手ですが、あるケースを考えてその一つ小さい/大きいケースを考えていくのは有効なんだと感じる。言語化の能力が低いので、こんな説明で伝わるかが不安。