結果
問題 | No.2298 yukicounter |
ユーザー |
|
提出日時 | 2023-05-12 22:29:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 12,803 bytes |
コンパイル時間 | 2,682 ms |
コンパイル使用メモリ | 223,308 KB |
最終ジャッジ日時 | 2025-02-12 23:13:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
/*#include <bits/stdc++.h>using namespace std;int main(){*/// __builtin_popcount() ;// multiset ;// unordered_set ;// unordered_map ;// reverse ;/*#include <atcoder/all>using namespace atcoder ;// using mint = modint;// using mint = modint998244353 ;// using mint = modint1000000007 ;*/#include <bits/stdc++.h>using namespace std;/*#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;typedef cpp_int cp ;*///-------型-------typedef long long ll;typedef string st ;typedef long double ld ;typedef unsigned long long ull ;using P = pair<ll,ll> ;using run = pair<char,ll> ;using Edge = tuple<ll,ll,ll> ;using AAA = tuple<ll,ll,ll,ll> ;//-------型-------//-------定数-------const ll mod0 = 1000000007;const ll mod1 = 998244353 ;const ll LINF = 1000000000000000000 ; //(10^18)const ld pai = acos(-1) ;const ld EPS = 1e-10 ;//-------定数-------//-------マクロ-------#define pb push_back#define ppb pop_back#define pf push_front#define ppf pop_front#define all(x) x.begin(), x.end()#define rep(i,a,n) for (ll i = a; i <= (n); ++i)#define rrep(i,a,b,c) for (ll i = a ; i <= (b) ; i += c)#define ketu(i,a,n) for (ll i = a; i >= (n); --i)#define re return 0;#define fore(i,a) for(auto &i:a)#define V vector#define fi first#define se second#define C cout#define E "\n";#define EE endl;//-------マクロ-------//-------テンプレ文字列-------st zz = "abcdefghijklmnopqrstuvwxyz" ;st ZZ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;st tintin = "%" ;st Y = "Yes" ;st YY = "No" ;st KU = " " ;//-------テンプレ文字列-------void chmin(ll& x ,ll y){x = min(x,y) ;}void chmax(ll& x ,ll y){x = max(x,y) ;}ll max_element(V<ll> &A){ll res = *max_element(all(A)) ;return res ;}ll max_element_index(V<ll> &A){ll res = max_element(all(A)) - A.begin() ;return res ;}ll min_element(V<ll> &A){ll res = *min_element(all(A)) ;return res ;}ll min_element_index(V<ll> &A){ll res = min_element(all(A)) - A.begin() ;return res ;}vector<ll> Y4 = {0,1,0,-1} ;vector<ll> X4 = {1,0,-1,0} ;vector<ll> Y8 = {0,1,1,1,0,-1,-1,-1} ;vector<ll> X8 = {1,1,0,-1,-1,-1,0,1} ;ll gcd(ll a, ll b){if(b == 0){return a;}return gcd(b,a%b) ;}ll lcm(ll a, ll b){ll ans = a*b /gcd(a,b) ;return ans ;}template<class T> T pow_mod(T A, T N, T M) {T res = 1 % M;A %= M;while (N) {if (N & 1) res = (res * A) % M;A = (A * A) % M;N >>= 1;}return res;}// Miller-Rabin 素数判定bool nis(ll N) {if (N <= 1) return false;if (N == 2) return true;if (N == 3) return true ;if (N == 5) return true ;if (N == 7) return true ;if (N == 11) return true ;if (N % 2 == 0 || N % 3 == 0 || N % 5 == 0 || N % 7 == 0 || N % 11 == 0 ) return false ;vector<ll> A = {2, 325, 9375, 28178, 450775,9780504, 1795265022};ll s = 0, d = N - 1;while (d % 2 == 0) {++s;d >>= 1;}fore(a,A) {if (a % N == 0) return true;ll t, x = pow_mod<__int128_t>(a, d, N);if (x != 1) {for (t = 0; t < s; ++t) {if (x == N - 1) break;x = __int128_t(x) * x % N;}if (t == s) return false;}}return true;}// UF.initはいっかいだけならいいけど、二回目以降はrepで初期化vector<ll> par;class UnionFind {public:// サイズをGET!void init(ll sz) {par.resize(sz,-1);}// 各連結成分の一番上を返すll root(ll x) {if (par[x] < 0) return x;return par[x] = root(par[x]);}// 結合作業bool unite(ll x, ll y) {x = root(x); y = root(y);if (x == y) return false;if (par[x] > par[y]) swap(x,y);par[x] += par[y];par[y] = x;return true;}// 同じグループか判定bool same(ll x, ll y) { return root(x) == root(y);}// グループのサイズをGET!ll size(ll x) { return -par[root(x)];}};UnionFind UF ;vector<ll> enumdiv(ll n) {vector<ll> S;for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.pb(i); if (i*i != n) S.pb(n / i); }sort(S.begin(), S.end());return S;}template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;template<typename T> using max_priority_queue = priority_queue<T, vector<T>, less<T>> ;// 使用例 min_priority_queue<ll (ここは型)> Q ;vector<pair<long long, long long>> prime_factorize(long long N){vector<pair<long long, long long>> res;for(long long a = 2; a * a <= N; ++a){if(N % a != 0) continue;long long 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 binpower(ll a, ll b,ll c) {if(!b) return 1 ;a %= c ;ll d = binpower(a,b/2,c) ;(d *= d) %= c ;if(b%2) (d *= a) %= c ;return d ;}template<typename T>V<T> sr(V<T> A){sort(all(A)) ;reverse(all(A)) ;return A ;}map<ll,ll> Compression(V<ll> A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;map<ll,ll> res ;ll index = 0 ;fore(u,A){res[u] = index ;index ++ ;}return res ;}V<ll> sort_erase_unique(V<ll> &A){sort(all(A)) ;A.erase(unique(all(A)),A.end()) ;return A ;}struct sqrt_machine{V<ll> A ;const ll M = 1000000 ;void init(){A.pb(-1) ;rep(i,1,M){A.pb(i*i) ;}A.pb(LINF) ;}bool scan(ll a){ll pos = lower_bound(all(A),a) - A.begin() ;if(A[pos] == -1 || A[pos] == LINF || A[pos] != a)return false ;return true ;}};sqrt_machine SM ;ll a_b(V<ll> A,ll a,ll b){ll res = 0 ;res += upper_bound(all(A),b) - lower_bound(all(A),a) ;return res ;}struct era{ll check[10000010] ;void init(){rep(i,2,10000000){if(check[i] == 0){for(ll j = i + i ;j <= 10000000 ; j += i){check[j] ++ ;}}}}bool look(ll x){if(x == 1)return false ;if(check[x] == 0)return true ;else return false ;}ll enu_count(ll x){if(x == 1)return 1 ;if(check[x] == 0)return 1 ;return check[x] ;}};era era ;st ten_to_two(ll x){st abc = "" ;if(x == 0){return "0" ;}while(x > 0){abc = char(x%2 + '0') + abc ;x /= 2 ;}return abc ;}ll two_to_ten(st op){ll abc = 0 ;ll K = op.size() ;for(ll i = 0 ;i < K ;i++){abc = abc * 2 + ll(op[i] - '0') ;}return abc ;}ll powpow(ll A , ll B){ll res = 1 ;rep(i,1,B){res *= A ;}return res ;}V<run> Run_Length_Encoding(st S){ll N = S.size() ;V<pair<char,ll>> A ;ll count = 0 ;char cc ;bool RLEflag = false ;if(N == 1){A.pb({S[0],1}) ;RLEflag = true ;}rep(i,0,N-1){if(RLEflag == true)break ;if(i == 0){cc = S[i] ;count = 1 ;continue ;}if(i == N-1){if(S[i] == cc){A.pb({cc,count + 1}) ;}else{A.pb({cc,count}) ;A.pb({S[i],1}) ;}break ;}if(S[i] == cc){count ++ ;}else{A.pb({cc,count}) ;cc = S[i] ;count = 1 ;}}return A ;}struct Two_Dimensional_Vector{void pr(V<V<ll>> A){ll N = A.size() ;ll M = A[0].size() ;rep(i,0,N-1){rep(j,0,M-1){C << A[i][j] << KU ;}C << E}}V<V<ll>> iv(ll N , ll M){V<V<ll>> A(N,V<ll>(M)) ;rep(i,0,N-1){rep(j,0,M-1){cin >> A[i][j] ;}}return A ;}ll Matrix_count(V<V<ll>> A,ll x){ll N = A.size() ;ll M = A[0].size() ;ll count = 0 ;rep(i,0,N-1){rep(j,0,M-1){if(A[i][j] == x)count ++ ;}}return count ;}} ;Two_Dimensional_Vector tdv ;/*st Regex(st S, st A ,st B){return regex_replace(S,regex(A),B) ;}st erase_string(st S , st T){st ans = S.erase(S.find(T),T.length()) ;return ans ;}*/template <typename st> // string, vector どちらでもvector<ll> zalgorithm(const st& s) {ll n = ll(s.size());if (n == 0) return {};vector<ll> z(n);z[0] = 0;for (ll i = 1, j = 0; i < n; i++) {ll& k = z[i];k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]);while (i + k < n && s[k] == s[i + k]) k++;if (j + z[j] < i + z[i]) j = i;}z[0] = n;return z;}int main(void){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// SM.init() ;// era.init() ;// max_element(V<ll> A) Aの最大値を返す// max_element_index(V<ll> A) Aの最大値のindex// min_element(V<ll> A) Aの最小値を返す// min_element_index(V<ll> A) Aの最小値のindex// gcd(ll a , ll b) gcd// lcm(ll a ,ll b ) lcm// nis(ll a) 素数判定 素数ならtrue// UF UF.init(ll N) ; UF.root(i) ; UF.unite(a,b) ; UF.same(a,b) ; UF.size(i) ;// enumdiv(ll a )約数列挙// prime_factorize(ll p) aのb乗のかたちででてくる 配列で受け取る// binpower(a,b,c) aのb条 をcでわったやつをO(logb) ぐらいでだしてくれるやつ// sr(V<ll> A) 配列を入れたら、sort --→ reverse して返してくれる関数 受け取りは auto とかで// sort_erase_unique(V<ll> A) sortしてeraseしてuniqueする関数// Compression(V<ll> A) 座圧したmapを返す関数// SM.scan(ll a) で 平方数ならtrue が返ってくる。 範囲は √10^6まで SM.init() 必ず起動する。// a_b(A,a,b) [a,b]の個数 ---→ upper_bound(all(A),b) - lower_bound(all(A),a) ;// era.look(ll a) --→ true 素数 / era.enu_count(ll a) --→ 素因数の個数 1は1 、素数も1 その他はそのまんま 範囲は10^7まで// ten_to_two(ll x) 10進数を二進数にして返す。文字列で出力する事に注意 ll --→ st// two_to_ten(st a) 2進数を10進数にして返す。 st --→ ll// powpow(ll a,ll b) a^b を返す// Run_Length_Encoding(st S) ランレングス圧縮して配列を返す pair<char,ll>// Regex(st S, st A , st B) SのAをBに変えた文字列を返す 使う場合は消す// erase_string(st S , st T) Sの中のTを消す// Two_Dimensional_Vector tdv.pr(V<V<ll>> A) Aを出力 tdv.iv(N,M) 配列を受け取る main内で auto A = tdv.iv(N,M) ;とする Matrix_count(V<V<ll>> , x)Aのなかのxの個数を返す// (double)clock()/CLOCKS_PER_SEC>1.987// multisetで1つだけ要素消したかったら、 A.erase(A.find(x)) ;とする。// mod0 --→ 1000000007 mod1 --→ 998244353// 座圧した後、size変わることに注意。二回やらかしてますst S ;cin >> S ;st H = "yukicoder" ;st T = "" ;ll N = S.size() ;ll M = 0 ;while(M < N){T += H ;M += 9 ;}while(M > N){T.ppb() ;M -- ;}V<ll> sub(N) ;rep(i,0,N-1){if(i + 9 >= N+1)break ;st ss = S.substr(i,9) ;if(ss == H){rep(j,i,i+8){if(j < N)sub[j] = 1 ;}}}V<ll> Tsub(M) ;rep(i,0,M-1){if(i + 9 >= M+1)break ;st ss = T.substr(i,9) ;if(ss == H){rep(j,i,i+8){if(j < M)Tsub[j] = 1 ;}}}rep(i,0,N-1){if(sub[i] == 0)S[i] = 'a' ;}rep(i,0,M-1){if(Tsub[i] == 0)T[i] = 'a' ;}ll ans = 0 ;auto Z = zalgorithm(T+S) ;ll count = 0 ;fore(u,Z){if(count >= S.size())chmax(ans,u/9LL) ;count ++ ;}C << ans << E// if(dx < 0 || dy < 0 || dx >= W || dy >= H) continue ;// C << fixed << setprecision(10) << // 勝手に四捨五入してくれてるから安心してre}