結果
| 問題 |
No.1951 消えたAGCT(2)
|
| コンテスト | |
| ユーザー |
 raven7959
|
| 提出日時 | 2022-05-23 10:04:57 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 412 ms / 3,000 ms |
| コード長 | 10,663 bytes |
| コンパイル時間 | 1,975 ms |
| コンパイル使用メモリ | 198,000 KB |
| 最終ジャッジ日時 | 2025-01-29 14:00:39 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n"
#define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n"
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vld = vector<long double>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvs = vector<vector<string>>;
using vvc = vector<vector<char>>;
using vvd = vector<vector<double>>;
using vvld = vector<vector<long double>>;
using vvvi = vector<vector<vector<int>>>;
using vvvl = vector<vector<vector<ll>>>;
using vvvvi = vector<vector<vector<vector<int>>>>;
using vvvvl = vector<vector<vector<vector<ll>>>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int INF = 1e9;
const ll LINF = 2e18;
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
bool ispow2(int i) { return i && (i & -i) == i; }
bool ispow2(ll i) { return i && (i & -i) == i; }
template <class T>
vector<T> make_vec(size_t a) {
return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
for (int i = 0; i < int(v.size()); i++) {
is >> v[i];
}
return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
for (int i = 0; i < int(v.size()); i++) {
os << v[i];
if (i < int(v.size()) - 1) os << ' ';
}
return os;
}
static uint32_t RandXor(){
static uint32_t x=123456789;
static uint32_t y=362436069;
static uint32_t z=521288629;
static uint32_t w=88675123;
uint32_t t;
t=x^(x<<11);
x=y; y=z; z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
static double Rand01(){
return (RandXor()+0.5)*(1.0/UINT_MAX);
}
// BinaryTrie<int,30> BT; などする
// void add(INT val): BTに入っている数字全てにvalをXORする
// INT get(Node *v): ポインタvに対応した値を返す(BTに入っている値,XORした時のk番目とかのときはあとで自分でXORする)
// Node* find(INT val): valに対応したポインタを返す
// void insert(INT val,size_t k=1): valをk個追加する
// bool erase(INT val): valを1個削除する
// bool erase(Node *v,size_t k=1): ポインタvに対応した値をk個削除する
// Node* get_max(INT val=0): valをXORした時の最大の要素と対応したポインタを返す(復元はget(*ptr)^valする)
// Node* get_min(INT val=0): 上の最小バージョン
// Node* lower_bound(INT val): val以上で最小の要素に対応するポインタを返す
// Node* upper_bound(INT val): valより大で最小の要素に対応するポインタを返す
// size_t order_of_val(INT val): valが小さい方から何番目か返す(val未満の数の個数+1を返すとも)
// Node* get_kth(size_t k,INT val=0): valをXORした時の小さい方からk番目(0-indexed)の要素に対応したポインタを返す(復元はget(*ptr)^valする)
template <typename INT, size_t MAX_DIGIT>
struct BinaryTrie{
struct Node{
size_t count;
Node *prev, *left, *right;
Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}
};
INT lazy;
Node *root;
// constructor
BinaryTrie() : lazy(0), root(emplace(nullptr)) {}
inline size_t get_count(Node *v) const { return v ? v->count : 0; }
// add and get value of Node
inline void add(INT val){
lazy ^= val;
}
inline INT get(Node *v){
if (!v)
return -1;
INT res = 0;
for (int i = 0; i < MAX_DIGIT; ++i){
if (v == v->prev->right)
res |= INT(1) << i;
v = v->prev;
}
return res ^ lazy;
}
// find Node* whose value is val
Node *find(INT val){
INT nval = val ^ lazy;
Node *v = root;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
bool flag = (nval >> i) & 1;
if (flag)
v = v->right;
else
v = v->left;
if (!v)
return v;
}
return v;
}
// insert
inline Node *emplace(Node *prev){
return new Node(prev);
}
void insert(INT val, size_t k = 1){
INT nval = val ^ lazy;
Node *v = root;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
bool flag = (nval >> i) & 1;
if (flag && !v->right)
v->right = emplace(v);
if (!flag && !v->left)
v->left = emplace(v);
if (flag)
v = v->right;
else
v = v->left;
}
v->count += k;
while ((v = v->prev))
v->count = get_count(v->left) + get_count(v->right);
}
// erase
Node *clear(Node *v){
if (!v || get_count(v))
return v;
delete (v);
return nullptr;
}
bool erase(Node *v, size_t k = 1){
if (!v)
return false;
v->count -= k;
while ((v = v->prev)){
v->left = clear(v->left);
v->right = clear(v->right);
v->count = get_count(v->left) + get_count(v->right);
}
return true;
}
bool erase(INT val){
auto v = find(val);
return erase(v);
}
// max (with xor-addition of val) and min (with xor-addition of val)
Node *get_max(INT val = 0){
INT nval = val ^ lazy;
Node *v = root;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
bool flag = (nval >> i) & 1;
if (!v->right)
v = v->left;
else if (!v->left)
v = v->right;
else if (flag)
v = v->left;
else
v = v->right;
}
return v;
}
Node *get_min(INT val = 0){
return get_max(~val & ((INT(1) << MAX_DIGIT) - 1));
}
// lower_bound, upper_bound
Node *get_cur_node(Node *v, int i){
if (!v)
return v;
Node *left = v->left, *right = v->right;
if ((lazy >> i) & 1)
swap(left, right);
if (left)
return get_cur_node(left, i + 1);
else if (right)
return get_cur_node(right, i + 1);
return v;
}
Node *get_next_node(Node *v, int i){
if (!v->prev)
return nullptr;
Node *left = v->prev->left, *right = v->prev->right;
if ((lazy >> (i + 1)) & 1)
swap(left, right);
if (v == left && right)
return get_cur_node(right, i);
else
return get_next_node(v->prev, i + 1);
}
Node *lower_bound(INT val){
INT nval = val ^ lazy;
Node *v = root;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
bool flag = (nval >> i) & 1;
if (flag && v->right)
v = v->right;
else if (!flag && v->left)
v = v->left;
else if ((val >> i) & 1)
return get_next_node(v, i);
else
return get_cur_node(v, i);
}
return v;
}
Node *upper_bound(INT val){
return lower_bound(val + 1);
}
size_t order_of_val(INT val){
Node *v = root;
size_t res = 0;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
Node *left = v->left, *right = v->right;
if ((lazy >> i) & 1)
swap(left, right);
bool flag = (val >> i) & 1;
if (flag){
res += get_count(left);
v = right;
}
else
v = left;
}
return res;
}
// k-th, k is 0-indexed
Node *get_kth(size_t k, INT val = 0){
Node *v = root;
INT nval = val ^ lazy;
if (get_count(v) <= k)
return nullptr;
for (int i = MAX_DIGIT - 1; i >= 0; --i){
bool flag = (nval >> i) & 1;
Node *left = (flag ? v->right : v->left);
Node *right = (flag ? v->left : v->right);
if (get_count(left) <= k)
k -= get_count(left), v = right;
else
v = left;
}
return v;
}
// debug
void print(Node *v, string prefix = ""){
if (!v)
return;
cout << prefix << ": " << v->count << endl;
print(v->left, prefix + "0");
print(v->right, prefix + "1");
}
void print(){
print(root);
}
vector<INT> eval(Node *v, int digit) const{
vector<INT> res;
if (!v)
return res;
if (!v->left && !v->right){
for (int i = 0; i < get_count(v); ++i)
res.push_back(0);
return res;
}
const auto &left = eval(v->left, digit - 1);
const auto &right = eval(v->right, digit - 1);
for (auto val : left)
res.push_back(val);
for (auto val : right)
res.push_back(val + (INT(1) << digit));
return res;
}
vector<INT> eval() const{
auto res = eval(root, MAX_DIGIT - 1);
for (auto &val : res)
val ^= lazy;
return res;
}
friend ostream &operator<<(ostream &os,
const BinaryTrie<INT, MAX_DIGIT> &bt){
auto res = bt.eval();
for (auto val : res)
os << val << " ";
return os;
}
};
void solve(){
int N;
cin>>N;
string S;
cin>>S;
vi cnt(26);
BinaryTrie<int,30> BT;
rep(i,N){
cnt[S[i]-'A']++;
BT.insert(i);
}
int d=0,ans=0;
while(true){
int x=cnt[(26-d)%26]+cnt[(28-d)%26]+cnt[(32-d)%26]+cnt[(45-d)%26];
if(!x) break;
ans++;
int p=BT.get(BT.get_kth(x-1));
cnt[S[p]-'A']--;
BT.erase(p);
int y=cnt[S[p]-'A'];
d=(d+y)%26;
}
cout<<ans<<endl;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
solve();
}