結果
問題 | No.2997 Making YuzuKizu |
ユーザー |
|
提出日時 | 2024-12-22 10:25:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 14,606 bytes |
コンパイル時間 | 5,149 ms |
コンパイル使用メモリ | 267,256 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-22 10:25:23 |
合計ジャッジ時間 | 5,942 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 17 |
コンパイルメッセージ
In file included from main.cpp:3: main.cpp: In function 'vvl BFS_grid(vs&, char, char, ll)': main.cpp:358:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 358 | auto [x, y] = que.front(); | ^
ソースコード
#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); string S;cin >> S; ll N = S.size(); vl cnt(122); rep(i, N)cnt[S[i]]++; cout << min({cnt['y'], cnt['u'], cnt['k'], cnt['a'], cnt['r'], cnt['i']}) << ' '; cout << min({cnt['a'] / 2, cnt['k'], cnt['r'], cnt['i']}) << ' '; cout << min({cnt['y'], cnt['u'] / 3, cnt['z'] / 2, cnt['k'], cnt['i']}) << endl; } #else // INCLUDED_MAIN #include <bits/stdc++.h> #include <atcoder/all> #include <cassert> using namespace std; using namespace atcoder; #define INF 1LL << 60 #define MOD 998244353 typedef long long ll; typedef long double ld; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vc<vvl>; using vs = vc<string>; using vvs = vv<string>; using vb = vc<bool>; using vvb = vv<bool>; using lP = pair<ll, ll>; using sP = pair<string, string>; using vlP = vc<lP>; using vsP = vc<sP>; using RLEs = vc<pair<char, ll>>; #define rep(i,n) for(ll i = 0; i < (n); ++i) #define rrep(i,n) for(ll i = 1; i <= (n); ++i) #define drep(i,n) for(ll i = (n)-1; i >= 0; --i) #define nfor(i,s,n) for(ll i=s;i<n;++i) #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define YES cout<<"Yes"<<endl #define NO cout<<"No"<<endl #define OK cout<<"ok"<<endl #define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}// if(a==b)YN; #define dame cout<<-1<<endl template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } string atoz = "abcdefghijklmnopqrstuvwxyz"; string TA = "Takahashi"; struct Edge { ll to; ll weight; Edge(ll t, ll w) : to(t), weight(w) { } }; using Graph = vector<vector<Edge>>; //////////////////////////////////////////// //maths ll floor(ll n, ll a){ return n / a - (n % a < 0); } //n / aの切り上げ ll ceil(ll n, ll a){ return n / a + ((n ^ a) >= 0) * (n % a != 0); } ll ceil_double(double n){ ll N = n; if(n <= N)return n; else return N + 1; } //xとyの最大公約数 ll gcd(ll x, ll y){ if(x % y == 0)return y; else return gcd(y, x % y); } //xとyの最小公倍数 ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } ll pow_ll(ll x, ll n){ ll ans = 1; while(n > 0){ if(n & 1)ans *= x; x *= x; n >>= 1; } return ans; } ll pow_mod(ll x, ll n, ll mod){ x = x % mod; if(n == 0)return 1; else if(n % 2 == 1){ return (x * pow_mod(x, n - 1, mod)) % mod; } else return pow_mod((x * x) % mod, n / 2, mod) % mod; } ll comb(ll n, ll k, ll mod){ ll x = 1; for(ll i = n - k + 1; i <= n; ++i)x = x * i % mod; ll y = 1; for(ll i = 1; i <= k; ++i)y = y * i % mod; y = pow_mod(y, mod - 2, mod); return x * y % mod; } ll mod_n(ll N, ll div){ if(N == abs(N))return N % div; else return (N % div + div) % div; } //not_sqrt ll dist(ll sx, ll sy, ll ex, ll ey){ return pow(abs(ex - sx), 2) + pow(abs(ey - sy), 2); } ll dist_M(ll sx, ll sy, ll ex, ll ey){ return abs(sx - ex) + abs(sy - ey); } ll count_range(ll n, ll m){ return ((m - n + 1) * (n + m)) / 2; } ll count_sum(ll A, ll D, ll L, ll N){ if(A == -1)return (N * (2 * L - (N - 1) * D)) / 2; else if(L == -1)return (N * (2 * A + (N - 1) * D)) / 2; else if(N == -1)return (((L - A) / D + 1) * (A + L)) / 2; else return (N * (A + L)) / 2; } //素数判定 bool is_Prime(ll num){ if(num == 1)return false; for(ll i = 2; i * i <= num; ++i){ if(num % i == 0)return false; } return true; } //約数列挙 vl enum_divisors(ll N) { vl res; for (ll i = 1; i * i <= N; ++i) { if (N % i == 0) { res.push_back(i); if (N/i != i) res.push_back(N/i); } } sort(res.begin(), res.end()); return res; } //素因数分解 vlP prime_factorize(ll N) { vlP res; for (ll a = 2; a * a <= N; ++a) { if (N % a != 0) continue; ll ex = 0; while (N % a == 0) { ++ex; N /= a; } res.push_back({a, ex}); } if (N != 1) res.push_back({N, 1}); return res; } ll count_Multiple(ll R, ll div, ll mod){ if(R == 0)return 0; ll res = R / div; if(mod <= R % div && 0 < mod)++res; return res; } //[L,R]をdivで割ったあまりがmodになる個数 ll count_Multiple(ll L, ll R, ll div, ll mod){ return count_Multiple(R, div, mod) - count_Multiple(L - 1, div, mod); } //n進数のsをm進数のresにする string ntom(string str, const ll n, const ll m){ unsigned long sum = 0; string res; for(char c : str){ sum = sum * n + (c - '0'); } do{ ll num = sum % m; res = static_cast<char>(num + '0') + res; sum /= m; } while (sum); return res; } struct Vector{ ll x, y; ll cross(const Vector &other)const{ return x * other.y - y * other.x; } ll dot(const Vector &other)const{ return x * other.x + y * other.y; } }; //<AOB 0:時計 1:反時計 bool is_lessthan180(const Vector &OA, const Vector &OB, bool o){ if(o)return (OA.cross(OB) > 0); else return (OA.cross(OB) < 0); } //string string S_lower(string &str){ for(ll i = 0; i < (ll)str.size(); ++i)str[i] = tolower(str[i]); return str; } bool is_Scontain(string &str, string &substr){ return str.find(substr) != string::npos; } ll S_count(string &S, char c){ ll cnt = 0; for(ll i = 0; i < (ll)S.size(); ++i)if(S[i] == c)cnt++; return cnt; } vc<pair<char, ll>> RLE(string &S){ ll len = S.size(); vc<pair<char, ll>> ret; for(ll i = 0; i < len;){ ll j = i + 1; while(j < len && S[i] == S[j])j++; ret.push_back({S[i], j - i}); i = j; } return ret; } string RLE_D(vc<pair<char, ll>> &ret){ string S; for(auto x : ret){ rep(i, x.second)S.push_back(x.first); } return S; } template<class T>string to_string(T N, ll len, char c){ string val = to_string(N); return string(len - (ll)val.size(), c) + val; } //graphs void count_Cycles_sub(Graph &G, ll v, vb &seen, vb &finished, ll &count, bool YM, ll parent){ seen[v] = true; for(Edge &e : G[v]){ ll nv = e.to; if(!YM && nv == parent)continue; if(finished[nv])continue; if(seen[nv] && !finished[nv])++count; if(seen[nv])continue; count_Cycles_sub(G, nv, seen, finished, count, YM, v); } finished[v] = true; } //1:有向 0:無向 ll count_Cycles(Graph &G, ll s, bool YM){ ll count = 0; vb seen(ll(G.size())), finished(ll(G.size())); count_Cycles_sub(G, s, seen, finished, count, YM, -1); return count; } vl count_ConnectedComponents(Graph &G){ vl ans; vb seen(ll(G.size())); rrep(i, ll(G.size()) - 1){ if(seen[i])continue; queue<ll> que; seen[i] = true; que.push(i); while (!que.empty()) { ll v = que.front(); que.pop(); for(Edge &e : G[v]){ if (seen[e.to]) continue; seen[e.to] = true; que.push(e.to); } } ans.push_back(i); } return ans; } bool is_GraphPath(Graph &G){ ll N = G.size() - 1; vl val = count_ConnectedComponents(G); if((ll)val.size() != 1)return false; ll o = 0, t = 0; for(ll i = 1; i <= N; ++i){ if(G[i].size() == 1)++o; else if(G[i].size() == 2)++t; else return false; } if(o != 2 || o + t != N)return false; return true; } //s == -1 : all v vl BFS(Graph &G, ll s){ vl dist(ll(G.size()), -1); vl val = count_ConnectedComponents(G); for(auto p : val){ queue<ll> que; dist[(s==-1?p:s)] = 0; que.push((s==-1?p:s)); while (!que.empty()) { ll v = que.front(); que.pop(); for(const Edge &e : G[v]){ if (dist[e.to] != -1) continue; dist[e.to] = dist[v] + e.weight; que.push(e.to); } } if(s != -1)break; } return dist; } ll BFS_M(Graph &G, ll s){ vl v = BFS(G, s); return *max_element(nall(v)); } ll BFS_m(Graph &G, ll s){ vl v = BFS(G, s); return *min_element(nall(v)); } vvl BFS_grid(vs &G, char s, char f, ll init){ vl DX = {-1, 0, 1, 0}, DY = {0, 1, 0, -1}; ll H = G.size(), W = G[0].size(); vvl dist(H, vl(W, init)); queue<lP> que; if(s == ' '){ que.push({0, 0}), dist[0][0] = 0; }else{ for(ll i = 0; i < H; ++i){ for(ll j = 0; j < W; ++j){ if(G[i][j] == s)que.push({i, j}), dist[i][j] = 0; } } } while(!que.empty()){ auto [x, y] = que.front(); que.pop(); for(ll d = 0; d < ll(DX.size()); ++d){ ll nx = x + DX[d], ny = y + DY[d]; if(nx < 0 || nx >= H || ny < 0 || ny >= W)continue; if(G[nx][ny] == f)continue; if(dist[nx][ny] != init)continue; que.push({nx, ny}); dist[nx][ny] = dist[x][y] + 1; } } return dist; } vl dijkstra(Graph &G, ll s){ vl dist(ll(G.size()), INF); priority_queue<lP, vlP, greater<lP>> que; dist[s] = 0; que.push({0, s}); while (!que.empty()) { lP p = que.top(); ll d = p.first; ll v = p.second; que.pop(); if(d > dist[v])continue; for(auto &e : G[v]){ if(d + e.weight < dist[e.to]){ dist[e.to] = d + e.weight; que.push({dist[e.to], e.to}); } } } return dist; } void DFS_tree(Graph &G, ll v, ll p, ll d, vl &depth, vl &size){ depth[v] = d; for(auto &e : G[v]){ if(e.to == p)continue; DFS_tree(G, e.to, v, d + 1, depth, size); } size[v] = 1; for(auto &e : G[v]){ if(e.to == p)continue; size[v] += size[e.to]; } } vl eulerTour(Graph G, ll s){ for(auto &v : G){ sort(v.begin(), v.end(), [](const Edge &a, const Edge &b){ return a.to < b.to; }); } vl val; function<void(ll, ll)> f = [&](ll v, ll pre){ val.push_back(v); for (auto &e : G[v]) { if (e.to != pre) { f(e.to, v); val.push_back(v); } } }; f(s, -1); return val; } struct UnionFind{ private: vl par, rank, size_; public: UnionFind(ll N) : par(N), rank(N), size_(N, 1){ for(int i = 0; i < N; i++) par[i] = i; } ll root(ll x){ if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(ll x, ll y){ x = root(x); y = root(y); if (x == y) return; if(rank[x] < rank[y]){ par[x] = y; size_[y] += size_[x]; }else{ par[y] = x; size_[x] += size_[y]; if(rank[x] == rank[y])++rank[x]; } } bool same(ll x, ll y){ return root(x) == root(y); } ll size(ll x){ return size_[root(x)]; } ll countSets(){ ll cnt = 0; for(ll i = 0; i < ll(par.size()); ++i)if(par[i] == i)++cnt; return cnt; } }; //others template<class T>void PrintContainer(const T &C){ cout << "[ "; for(auto &c : C)cout << c << ' '; cout << "]\n"; } //trueならcontinue bool out_grid(ll i, ll j, ll h, ll w) { return (!(0 <= i && i < h && 0 <= j && j < w)); } struct CircularRing{ private: ll N; public: CircularRing(ll N_) : N(N_) {} //0:時計1:反時計[s, e] bool cross(ll s, ll e, ll x, ll rote){ if(rote == 0){ if(s > e)return (s <= x || x <= e); else return (s <= x && x <= e); }else{ if(s < e)return (s <= x || x <= e); else return (e <= x && x <= s); } } ll dist(ll s, ll e, ll m, ll rote){ if(rote == -1 && s > e)swap(s, e); if(m == -1){ if(rote == -1){ return min(e - s, N - (e - s)); }else if(rote == 0){ if(s < e)return e - s; else return N - (s - e); }else{ if(s > e)return s - e; else return N - (e - s); } }else{ if(rote == -1){ if(e - s <= N - (e - s)){ if(s < m && m < e)return N - (e - s); else return e - s; }else{ if(e < m || m < s)return e - s; else return N - (e - s); } }else{ if(cross(s, e, m, rote))return -1; else return dist(s, e, -1, rote); } } } }; vl press_xy(vl &A){ vl B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); vl res(ll(A.size())); for(ll i = 0; i < ll(A.size()); ++i){ res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin(); } return res; } template<class T>void reverse(T &C, ll L, ll R){ auto itl = next(C.begin(), L); auto itr = next(C.begin(), R + 1); reverse(itl, itr); } template <class T> bool is_reverse(T &C){ ll len = C.size(); for(ll i = 0; i < len / 2; ++i)if(C[i] != C[len - i - 1])return false; return true; } template <class T> bool is_reverse(T &C, ll s, ll e){ ll len = e - s + 1; for(ll i = 0; i < len / 2; ++i)if(C[i + s] != C[len - i - 1 + s])return false; return true; } ll binary_search_index(vl &C, ll key){ auto it = lower_bound(C.begin(), C.end(), key); if(it != C.end() && *it == key)return (it - C.begin()); else return -1; } struct BIT{ private: ll n; vector<ll> a; public: BIT(ll n) : n(n), a(n + 1, 0){} void add(ll i, ll x){ i++; if(i == 0) return; for(ll k = i; k <= n; k += (k & -k))a[k] += x; } ll sum_sub(ll i){ i++; ll s = 0; if(i == 0) return s; for(ll k = i; k > 0; k -= (k & -k)){ s += a[k]; } return s; } ll sum(ll i, ll j){return sum_sub(j) - sum_sub(i - 1);} ll lower_bound(ll x){ if(x <= 0){ return 0; }else{ ll i = 0; ll r = 1; while(r < n) r = r << 1; for(ll len = r; len > 0; len = len >> 1){ if(i + len < n && a[i + len] < x){ x -= a[i + len]; i += len; } } return i; } } }; ll count_inversions(vl &v){ ll ans = 0, len = v.size(); BIT b(len); for(ll i = 0; i < len; ++i){ ans += i - b.sum_sub(v[i]); b.add(v[i], 1); } return ans; } template <class T> ll count_inversions(vector<T> S, vector<T> E){ map<T, ll> mp; if(S.size() != E.size())return -1; ll len = S.size(); for(ll i = 0; i < len; ++i)mp[S[i]] = i; vector<ll> val(len); for(ll i = 0; i < len; ++i)val[i] = mp[E[i]]; return count_inversions(val); } //1-indexed struct Kthset{ private: multiset<ll>L, R; ll K; public: Kthset(ll k) : K(k){} void insert(ll v){ R.insert(v); if((ll)L.size() < K){ L.insert(*R.begin()); R.erase(R.begin()); }else if(*R.begin() < *L.rbegin()){ L.insert(*R.begin()); R.erase(R.begin()); R.insert(*L.rbegin()); L.erase(--L.end()); } } void erase(ll v){ auto itl = L.find(v), itr = R.find(v); if(itl != L.end()){ L.erase(itl); }else if(itr != R.end()){ R.erase(itr); } if((ll)L.size() < K && !R.empty()){ L.insert(*R.begin()); R.erase(R.begin()); } } ll getKth(){return *L.rbegin();} }; //////////////////////////////////////////// #endif // INCLUDED_MAIN