#861519 (C++14) No.2276 I Want AC

提出ソース

結果

問題	No.2276 I Want AC
ユーザー	inkkk
提出日時	2023-04-21 22:16:17
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	12,659 bytes
コンパイル時間	1,765 ms
コンパイル使用メモリ	169,268 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-06 15:46:08
合計ジャッジ時間	7,031 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	33 ms 5,248 KB
testcase_12	AC	107 ms 5,248 KB
testcase_13	AC	32 ms 5,248 KB
testcase_14	AC	15 ms 5,248 KB
testcase_15	AC	56 ms 5,248 KB
testcase_16	AC	50 ms 5,248 KB
testcase_17	AC	101 ms 5,248 KB
testcase_18	AC	77 ms 5,248 KB
testcase_19	AC	4 ms 5,248 KB
testcase_20	AC	100 ms 5,248 KB
testcase_21	AC	42 ms 5,248 KB
testcase_22	AC	20 ms 5,248 KB
testcase_23	AC	122 ms 5,248 KB
testcase_24	AC	121 ms 5,248 KB
testcase_25	AC	121 ms 5,248 KB
testcase_26	WA	-
testcase_27	AC	128 ms 5,248 KB
testcase_28	AC	93 ms 5,248 KB
testcase_29	AC	75 ms 5,248 KB
testcase_30	AC	125 ms 5,248 KB
testcase_31	AC	53 ms 5,248 KB
testcase_32	AC	124 ms 5,248 KB
testcase_33	AC	125 ms 5,248 KB
testcase_34	AC	91 ms 5,248 KB
testcase_35	AC	30 ms 5,248 KB
testcase_36	AC	30 ms 5,248 KB
testcase_37	AC	34 ms 5,248 KB
testcase_38	WA	-
testcase_39	AC	30 ms 5,248 KB
testcase_40	AC	30 ms 5,248 KB
testcase_41	AC	30 ms 5,248 KB
testcase_42	AC	35 ms 5,248 KB
testcase_43	AC	34 ms 5,248 KB
testcase_44	AC	81 ms 5,248 KB
testcase_45	AC	126 ms 5,248 KB
testcase_46	AC	127 ms 5,248 KB
testcase_47	AC	81 ms 5,248 KB
testcase_48	WA	-
testcase_49	AC	123 ms 5,248 KB
testcase_50	AC	127 ms 5,248 KB
testcase_51	AC	126 ms 5,248 KB
testcase_52	AC	128 ms 5,248 KB
testcase_53	AC	119 ms 5,248 KB
testcase_54	AC	63 ms 5,248 KB
testcase_55	AC	57 ms 5,248 KB
testcase_56	AC	44 ms 5,248 KB
testcase_57	AC	33 ms 5,248 KB
testcase_58	AC	39 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define rrep(i, s, n) for (ll i = s; i >= (ll)(n); i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(),(x).rend()
#define SORT(x) sort(x.begin(),x.end())
#define REVERSE(x) reverse( x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define pb push_back
#define fi first
#define se second
#define inf 2e18
#define eps 1e-9
#define BIT(x,i)(((x)>>(i))&1)
#define mint Fp<mod>
// const int mod = 1000000007;
const int mod = 998244353;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
using ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
/* ビット列による集合の扱い
// https://primenumber.hatenadiary.jp/entry/2016/12/01/000000
*/
// vector<vector<vector<int>>> dp(N, vector<vector<int>>(3,vector<int>(2e5+1,1)));
// printf("x = %d, pi = %.10lf\n", x, pi);
	// cout << fixed << setprecision(15);
	// cout << ans;
// string s = to_string(number);
	// str.substr(開始位置, 取り出す長さ);
// int n = stoi(s); stoll, stod
	// __gcd(x,y); 最大公約数,計算量log(x+y)
	// a / __gcd(a,b) * b; 最小公倍数
//for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
	//bitset<ビット数> s(tmp);
	//rep(i,0,N) if( s.test(i)) sum+=A[i];

// while (next_permutation(配列変数.begin(), 配列変数.end()));

/*座標圧縮*/
	// vector<int> A = a;	//コピー
	// SORT(A);
	// A.erase(unique(all(A)),A.end());	//重複を削除
	// rep(i,0,n) a[i] = POSL(A,a[i])+1;	//何番目の大きさか

// 二分探索
	// ll left = -1;
	// ll right = (int)a.size();
  	// /* どんな二分探索でもここの書き方を変えずにできる！ */
  	// while (right - left > 1) {
    // 	ll mid = left + (right - left) / 2;
    // 	if (isOK(mid, key) == true or false) right = mid;
    // 	else left = mid;
  	// }
/*凸関数の頂点を求める三分探索*/
	// ll l = 0, r = a / b;
    // while (r - l > 2) {
    //     ll m1 = (l * 2 + r) / 3;
    //     ll m2 = (l + r * 2) / 3;
    //     if (f(m1) > f(m2)) l = m1;
    //     else r = m2;
    // }
/* nCk の事前計算*/
	// vector<vector<ll>> nCk(n+1,vector<ll>(n+1,0));
	// rep(i,1,n+1) nCk[i][1] = 1;
	// rep(i,2,n+1){
	// 	rep(j,2,n+1){
	// 		nCk[i][j] = nCk[i-1][j-1] + j*nCk[i-1][j];
	// 	}
	// }
// セグメント木
	// class segment_tree {
	// 	private:
	// 	int sz;
	// 	std::vector<int> seg;
	// 	std::vector<int> lazy;
	// 	void push(int k) {
	// 		if (k < sz) {
	// 			lazy[k * 2] = max(lazy[k * 2], lazy[k]);
	// 			lazy[k * 2 + 1] = max(lazy[k * 2 + 1], lazy[k]);
	// 		}
	// 		seg[k] = max(seg[k], lazy[k]);
	// 		lazy[k] = 0;
	// 	}
	// 	void update(int a, int b, int x, int k, int l, int r) {
	// 		push(k);
	// 		if (r <= a || b <= l) return;
	// 		if (a <= l && r <= b) {
	// 			lazy[k] = x;
	// 			push(k);
	// 			return;
	// 		}
	// 		update(a, b, x, k * 2, l, (l + r) >> 1);
	// 		update(a, b, x, k * 2 + 1, (l + r) >> 1, r);
	// 		seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
	// 	}
	// 	int range_max(int a, int b, int k, int l, int r) {
	// 		push(k);
	// 		if (r <= a || b <= l) return 0;
	// 		if (a <= l && r <= b) return seg[k];
	// 		int lc = range_max(a, b, k * 2, l, (l + r) >> 1);
	// 		int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);
	// 		return max(lc, rc);
	// 	}
	// 	public:
	// 	segment_tree() : sz(0), seg(), lazy() {};
	// 	segment_tree(int N) {
	// 		sz = 1;
	// 		while (sz < N) {
	// 			sz *= 2;
	// 		}
	// 		seg = std::vector<int>(sz * 2, 0);
	// 		lazy = std::vector<int>(sz * 2, 0);
	// 	}
	// 	void update(int l, int r, int x) {
	// 		update(l, r, x, 1, 0, sz);
	// 	}
	// 	int range_max(int l, int r) {
	// 		return range_max(l, r, 1, 0, sz);
	// 	}
	// };
// modint
	template<int MOD> struct Fp {
		long long val;
		constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
			if (val < 0) val += MOD;
		}
		constexpr int getmod() { return MOD; }
		constexpr Fp operator - () const noexcept {
			return val ? MOD - val : 0;
		}
		constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
		constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
		constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
		constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
		constexpr Fp& operator += (const Fp& r) noexcept {
			val += r.val;
			if (val >= MOD) val -= MOD;
			return *this;
		}
		constexpr Fp& operator -= (const Fp& r) noexcept {
			val -= r.val;
			if (val < 0) val += MOD;
			return *this;
		}
		constexpr Fp& operator *= (const Fp& r) noexcept {
			val = val * r.val % MOD;
			return *this;
		}
		constexpr Fp& operator /= (const Fp& r) noexcept {
			long long a = r.val, b = MOD, u = 1, v = 0;
			while (b) {
				long long t = a / b;
				a -= t * b; swap(a, b);
				u -= t * v; swap(u, v);
			}
			val = val * u % MOD;
			if (val < 0) val += MOD;
			return *this;
		}
		constexpr bool operator == (const Fp& r) const noexcept {
			return this->val == r.val;
		}
		constexpr bool operator != (const Fp& r) const noexcept {
			return this->val != r.val;
		}
		friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
			return os << x.val;
		}
		friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
			if (n == 0) return 1;
			auto t = modpow(a, n / 2);
			t = t * t;
			if (n & 1) t = t * a;
			return t;
		}
	};
/**************** 二項係数の計算******************/
// 使い方 COMinit(); ans = COM(n,m);
	// #define MAX 201010
	// mint fac[MAX], finv[MAX], inv[MAX];
	// // テーブルを作る前処理
	// void COMinit() {
	// 	fac[0] = fac[1] = 1;
	// 	finv[0] = finv[1] = 1;
	// 	inv[1] = 1;
	// 	for (int i = 2; i < MAX; i++){
	// 		fac[i] = fac[i - 1] * i;
	// 		inv[i] = (mint)mod - inv[mod%i] * (mod / i);
	// 		finv[i] = finv[i - 1] * inv[i];
	// 	}
	// }
	// // 二項係数計算
	// mint COM(int n, int k){
	// 	if (n < k) return 0;
	// 	if (n < 0 || k < 0) return 0;
	// 	return fac[n] * (finv[k] * finv[n - k]);
	// }
// 二項係数（N=60以下）
	// vector<vector<ll>> nCk(N+1,vector<ll>(N+1,0));
	// rep(i,0,N+1) nCk[i][0] = 1;
	// nCk[1][1] = 1;
	// rep(i,2,N+1) rep(j,1,N+1) nCk[i][j] = nCk[i-1][j-1] + nCk[i-1][j];
/***************************************************/
void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }
void No() { std::cout << "No\n"; }
void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }
void NO() { std::cout << "NO\n"; }
template <typename T>
bool chmax(T &a, const T& b) {
	if (a < b) { a = b; return true; }
	return false; }
template <typename T>
bool chmin(T &a, const T& b) {
	if (a > b) { a = b; return true; }
	return false;
}
// 桁数を数える ex. 100 -> 3
ll digitnum(ll x, ll b = 10){ ll ret = 0; for(; x; x /= b) ret++; return ret; }
// 各桁の数字の合計 ex. 123 -> 6
ll digitsum(ll x, ll b = 10){ ll ret = 0; for(; x; x /= b) ret += x % b; return ret;}
template <class T>
T pow(T a, long long n) {
	T ret = 1;
	while(n) { if(n & 1) ret *= a; a *= a; n >>= 1; }
	return ret;
}
ll modpow(ll a, ll n, ll mod_){
	if(n == 0) return 1;
	if(n % 2) return ((a%mod_) * (modpow(a, n-1, mod_)%mod_)) % mod_;
	else return modpow((a*a)%mod_, n/2, mod_) % mod_;
}
// mod mでのa の逆元を返す 例：ans = x * modinv(a,m); ans %= m;
	// long long modinv(long long a, long long m) {
    // 	long long b = m, u = 1, v = 0;
    // 	while (b) {
    // 	    long long t = a / b;
    // 	    a -= t * b; swap(a, b);
    // 	    u -= t * v; swap(u, v);
    // 	}
    // 	u %= m; 
    // 	if (u < 0) u += m;
    // 	return u;
	// }
// 素因数分解した結果の因子数
	// long long factrization_cnt( long long N ){
	// 	long long cnt = 0;
	// 	rep(i,2,1e6+10) {
	// 		if( i * i > N  ) break;
	// 		if( N % i != 0 ) continue;
	// 		while( N % i == 0 ){ cnt++; N /= i; }
	// 	}
	// 	if( N != 1 ) cnt++;
	// 	return cnt;
	// }
// 等差数列の和  (初項, 差, 項数)
ll tousa_sum(ll first,ll diff,ll num){
	return (first+first+diff*(num-1))*num/2;
}
// 1 以上 N 以下の整数が素数かどうかを返す
	// 	vector<bool> sosu = Eratosthenes(n);
	// 	vector<bool> Eratosthenes(int N) {
	// 	    vector<bool> isprime(N+1, true);
	// 	    isprime[0] = isprime[1] = false;
	// 	    for (int p = 2; p <= N; ++p) {
	// 	        if (!isprime[p]) continue;
	// 	        for (int q = p * 2; q <= N; q += p) isprime[q] = false;
	// 	    }
	// 	    return isprime;
	// 	}
/* https://algo-logic.info/union-find-tree/
		UnionFind：素集合系管理の構造体(union by size)
		same(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
		unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
		treeSize(x): x を含む集合の要素数。 */
	struct UnionFind {
		vector<int> size, parents;
		UnionFind() {}
		UnionFind(int n) {  // make n trees.
				size.resize(n, 0);
				parents.resize(n, 0);
				for (int i = 0; i < n; i++) makeTree(i);
		}
		void makeTree(int x) {
				parents[x] = x;  // the parent of x is x
				size[x] = 1;
		}
		bool same(int x, int y) { return findRoot(x) == findRoot(y); }
		bool unite(int x, int y) {
				x = findRoot(x);
				y = findRoot(y);
				if (x == y) return false;
				if (size[x] > size[y]) {
						parents[y] = x;
						size[x] += size[y];
				} else {
						parents[x] = y;
						size[y] += size[x];
				}
				return true;
		}
		int findRoot(int x) {
				if (x != parents[x]) {
						parents[x] = findRoot(parents[x]);
				}
				return parents[x];
		}
		int treeSize(int x) { return size[findRoot(x)]; }
};
// DFS
	// struct Graph{
	// 	vector<vector<int>> edge;
	// 	vector<int> seen;
	// 	vector<int> first;
	// 	int fcnt;
	// 	vector<int> last;
	// 	int lcnt;
	// 	int cnt;
	// 	deque<int> deq;
	// 	bool ok = false;

	// 	Graph(int n){
	// 		edge.resize(n);
	// 		seen.resize(n,-1);
	// 		first.resize(n,0);
	// 		fcnt = 0;
	// 		last.resize(n,0);
	// 		lcnt = 0;
	// 	}
	// };
	// void dfs(Graph &g, int crr){
	// 	g.seen[crr] = 1;
	// 	g.first[crr] = g.fcnt++;
	// 	for( auto nxt: g.edge[crr] ){
	// 		if( g.seen[nxt] != -1 ) continue;
	// 		dfs( g, nxt);
	// 	}
	// 	g.seen[crr] = -1;
	// 	g.last[crr] = g.lcnt++;
	// }

// グリッドのDFS
	// struct Grid{
	// 	vector<vector<int>> field;
	// 	set<int> a;

	// 	Grid(ll n){
	// 		field.resize(n+10);
	// 		rep(i,0,n+10) field[i].resize(n+10,-1); // 0は壁などの行けないところ
	// 	}
	// };
	// void dfsgrid(Grid &g, int h, int w){
	// 	// g.field[h][w] = 0;
	// 	if( g.field[h][w] == -1 ) return;
	// 	if( g.a.count(g.field[h][w])){
	// 		return;
	// 	}
	// 	// cout << h-4 << " " << w-4 << endl;
	// 	if( h == H+4 && w == W+4 ){
	// 		ans++;
	// 		return;
	// 	}
	// 	g.a.insert(g.field[h][w]);

	// 	dfsgrid(g,h+1,w);
	// 	dfsgrid(g,h,w+1);
	// 	g.a.erase(g.field[h][w]);
	// }
/********* dijkstra **********/
	// vector<vector<pair<int,ll>>> graph(200010);
	// vector<ll> dist(200010,inf);
	// priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	// dist.assign(200010,inf);
	// dist[s] = 0;
	// q.push(make_pair(0,s));

	// while(!q.empty()){
	// 	int pos = q.top().second; q.pop();
	// 	for( auto v: graph[pos] ){
	// 		int to = v.first;
	// 		ll cost = v.second;
	// 		if( dist[to] > dist[pos] + cost ){
	// 			dist[to] = dist[pos] + cost;
	// 			q.push(make_pair(dist[to],to));
	// 		}
	// 	}
	// }
//BFS
	// queue<ll> que;
	// vector<ll> dist(n,-1);
	// dist[0] = 0;
	// que.push(0);

	// while(!que.empty()){
	// 	ll v = que.front(); que.pop();
	// 	for(auto nv: g[v]){
	// 		if( dist[nv] == -1 ){
	// 			dist[nv] = dist[v] + 1;
	// 			que.push(nv);
	// 		}
	// 	}
	// }
//
	ll n,m,q,w,h,H,W,N,L,Q,k,K,R;
	string s;
	// vector<int> a(200100),b(200100),c(200100);
string ac(ll a){
	string x = s;
	rep(i,0,n){
		if( x[i] == '?' ){
			if( i < a ) x[i] = 'A';
			else x[i] = 'C';
		}
	}
	return x;
}
ll f(ll a){
	string x = ac(a);
	ll ans = 0;
	ll sum = 0;
	rep(i,0,n){
		if( x[i] == 'A' ) sum++;
		if( x[i] == 'C' ) ans += sum;
	}
	return ans;
}
////////////////////////////////////////////////////////
int main() {
	cin.tie(0);
	cin >> n >> s;
	// vector<ll> a(n);
	// rep(i,0,n) cin >>a[i];

	ll l = 0, r = n;
    while (r - l > 2) {
        ll m1 = (l * 2 + r) / 3;
        ll m2 = (l + r * 2) / 3;
        if (f(m1) > f(m2)) r = m2;
        else l = m1;
    }
	ll ans = max(f(l),f(l+1));
	ans = max(ans,f(r));
	cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード