システスまだだけど多分ABCDの4完
A. Favorite Sequence
dequeを使って左右から取り出していく
B. Last Year's Substring
"2020"を分割する組み合わせは、
"2020"+""・"202"+"0"・"20"+"20"・"202"+"0"・""+"2020"だけなので、その通りに場合分け
C. Unique Number
bit全探索で、i番目のbitが立っている時iを足す……ってやって、合計値がxになるもののうち、桁数(bitが立っている数)が最小のものを出力
D. Add to Neighbour and Remove
最大でもN-1回の操作でできる。
累積和を取って、累積和に出てくる数字それぞれについて、数列を全部その数字にすることが可能か見る。最初に10^8全部見てて1ペナ……。
E1. Close Tuples (easy version)
じゅぴろさんに教えてもらった。
最小の数を1つ決めると、1種類の数字から3つ取る場合・2種類の数字から3つ取る場合・3種類の数字から3つ取る場合が考えられる(元々数列のどの位置にあったかは関係ない)。最小の数を1~N-2まで見て、すべての場合を足し合わせていく。
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e12;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int COM(int a, int n){
int X = 1;
int Y = 1;
if( a < n ) return 0;
for( int i = a; i >= a-n+1; i-- ) X *= i;
for( int i = 2; i <= n; i++ ) Y *= i;
return X/Y;
}
signed main(){
int T;
cin >> T;
for( int t = 0; t < T; t++ ){
int N;
cin >> N;
vector<int> cnt(N+10);
rep(i, N){
int A;
cin >> A;
cnt[A]++;
}
int ans = 0;
for( int i = 0; i <= N; i++ ){
if( cnt[i] > 0 ){
ans += COM(cnt[i], 3);
ans += cnt[i]*COM(cnt[i+1], 2) + COM(cnt[i], 2)*cnt[i+1] + cnt[i]*COM(cnt[i+2], 2) + COM(cnt[i], 2)*cnt[i+2];
ans += cnt[i]*cnt[i+1]*cnt[i+2];
}
}
cout << ans << endl;
}
}
E2は起きてから考えます。オヤスミ……。