結果
問題 | No.2419 MMA文字列2 |
ユーザー |
![]() |
提出日時 | 2023-08-12 14:05:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 2,808 bytes |
コンパイル時間 | 1,939 ms |
コンパイル使用メモリ | 175,816 KB |
実行使用メモリ | 155,164 KB |
最終ジャッジ日時 | 2024-11-19 17:20:05 |
合計ジャッジ時間 | 5,475 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> /// @brief Union-Find 木 /// @note 1.4 高速化 + 省メモリ化 /// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find class UnionFind { public: UnionFind() = default; /// @brief Union-Find 木を構築します。 /// @param n 要素数 explicit UnionFind(size_t n) : m_parentsOrSize(n, -1) {} /// @brief 頂点 i の root のインデックスを返します。 /// @param i 調べる頂点のインデックス /// @return 頂点 i の root のインデックス int find(int i) { if (m_parentsOrSize[i] < 0) { return i; } // 経路圧縮 return (m_parentsOrSize[i] = find(m_parentsOrSize[i])); } /// @brief a のグループと b のグループを統合します。 /// @param a 一方のインデックス /// @param b 他方のインデックス void merge(int a, int b) { a = find(a); b = find(b); if (a != b) { // union by size (小さいほうが子になる) if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) { std::swap(a, b); } m_parentsOrSize[a] += m_parentsOrSize[b]; m_parentsOrSize[b] = a; } } /// @brief a と b が同じグループに属すかを返します。 /// @param a 一方のインデックス /// @param b 他方のインデックス /// @return a と b が同じグループに属す場合 true, それ以外の場合は false bool connected(int a, int b) { return (find(a) == find(b)); } /// @brief i が属するグループの要素数を返します。 /// @param i インデックス /// @return i が属するグループの要素数 int size(int i) { return -m_parentsOrSize[find(i)]; } private: // m_parentsOrSize[i] は i の 親, // ただし root の場合は (-1 * そのグループに属する要素数) std::vector<int> m_parentsOrSize; }; using namespace std; typedef long long ll; #define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rrep(i,a,b) for(ll i=(ll)(a-1);i>=(ll)(b);i--) #define MOD 998244353 //#define MOD 1e9+7 #define INF 1e16 //#define PI numbers::pi //#define E numbers::e template <typename T> bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template <typename T> bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} int main(){ string s; cin >> s; vector<vector<vector<ll>>> dp(s.size()+1,vector<vector<ll>>(3,vector<ll>(26,0))); rep(i,0,s.size()){ ll a=s[i]-'A'; rep(j,0,26){ dp[i+1][0][j]=dp[i][0][j]; dp[i+1][1][j]=dp[i][1][j]; dp[i+1][2][j]=dp[i][2][j]; } dp[i+1][0][a]++; dp[i+1][1][a]+=dp[i][0][a]; rep(j,0,26){ if(j!=a) dp[i+1][2][a]+=dp[i][1][j]; } } ll ans=0; rep(i,0,26) ans+=dp[s.size()][2][i]; cout << ans << endl; }