C問題 Spiral Rotation
D問題 ABA
i,j,kのうち真ん中のjを固定して考えることに気付けると、すんなり正解できる問題。
本番中はi,kに着目してしまって難しい実装になってしまっていた。。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <atcoder/all>
#define INF (1LL<<30)
template<class T> inline bool chmin(T& a, T b) {
if (a > b) { a = b; return true; }
else return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) { a = b; return true; }
return false;
}
long long popcount(long long n) {
long long ans = 0;
for (int x = 0; x <= 60; x++) if (((n >> x) & 1) == 1) ans++;
return ans;
}
struct TreeNode {
std::vector<int> Children;
bool IsVisited = false;
};
int main() {
std::string S;
std::cin >> S;
std::vector<long long> lcnt(26, 0), rcnt(26, 0);
for (int i = 0; i < S.size(); i++) rcnt[S[i] - 'A']++;
long long ans = 0;
for (int i = 0; i < S.size(); i++) {
rcnt[S[i] - 'A']--;
for (int c = 0; c < 26; c++) ans += (lcnt[c] * rcnt[c]);
lcnt[S[i] - 'A']++;
}
std::cout << ans << std::endl;
}
//int main() {
// std::string S;
// std::cin >> S;
// std::vector<std::vector<long long>> I(26, std::vector<long long>());
//
// for (long long n = 0; n < S.size(); n++) I[S[n] - 'A'].push_back(n);
//
// long long ans = 0;
// for (long long c = 0; c < I.size(); c++) {
// if (I[c].size() < 1) continue;
// for (long long n = 0; n < (I[c].size()); n++) {
// //for(long long nn=n+1; nn<I[c].size(); nn++) ans += (I[c][nn] - I[c][n] - 1);
//
// /*long long k = (I[c][I[c].size() - 1] - I[c][n] - 1);
// ans += (k * (k + 1) / 2);*/
//
// ans -= (I[c].size() - 1 - n) * I[c][n];
// ans += n * I[c][n];
// }
// ans -= (I[c].size() - 1) * I[c].size() / 2; //←ファッ！？
//
// /*long long s = I[c].size();
// long long k = (I[c][s - 1] - I[c][0] - 1);
// ans += (k * (k + 1) / 2);*/
//
// /*std::vector<long long> sum(I[c].size()+1,0);
// sum[0] = I[c][0];
// for (long long n = 1; n < I[c].size(); n++) sum[n] = (sum[n - 1] + (I[c][n] -I[c][0] - 1));
// ans += (sum[I[c].size() - 1] - sum[0]);*/
// }
// std::cout << ans << std::endl;
//}
コメント