Indeedなう(予選B) D問題: 高橋くんと数列
補集合を思いつくのに時間がかかった。
問題:http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4
解法:「その数を1つでも含む連続する部分列」ではなく、「その数をひとつも含まない連続する部分列」を考え、それを可能な部分列の合計から引く。
連続する部分列と、列から左端と右端を選ぶのは1対1に対応し、その数は列がp個であったとすると、重複を許してp個から2個選ぶ場合の数になるから、通りとなる。本番書いたコードはかなり汚くてもうちょいキレイになりそう。
以下ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)n; i++) using namespace std; typedef long long ll; const int MAXN = 100100; int a[MAXN]; vector<int> pos[MAXN]; int main(void) { int N, C; cin >> N >> C; for (int i = 0; i < N; i++) { cin >> a[i]; pos[a[i]].push_back(i); } ll all = (ll)(N+1) * N / 2; for (int i = 1; i <= C; i++) { int p = pos[i].size(); ll minus = 0; if (p == 1) { ll n = pos[i][0]; minus += (n+1)*n/2; n = N-pos[i][0]-1; minus += (n+1)*n/2; } else { for (int j = 0; j < p; j++) { if (j == 0) { ll n = pos[i][j]; minus += (n+1)*n/2; } else if (j < p-1) { ll n = pos[i][j] - pos[i][j-1] - 1; minus += (n+1)*n/2; } else { ll n = pos[i][j] - pos[i][j-1] - 1; minus += (n+1)*n/2; n = N-pos[i][j]-1; minus += (n+1)*n/2; } } } cout << all-minus << endl; } return 0; }