結果

問題 No.2276 I Want AC
ユーザー kuro_Bkuro_B
提出日時 2023-05-10 16:35:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 726 ms / 2,000 ms
コード長 2,421 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 152,732 KB
最終ジャッジ日時 2024-11-26 21:39:32
合計ジャッジ時間 26,268 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
83,072 KB
testcase_01 AC 129 ms
82,688 KB
testcase_02 AC 122 ms
82,432 KB
testcase_03 AC 125 ms
82,816 KB
testcase_04 AC 129 ms
82,944 KB
testcase_05 AC 130 ms
83,200 KB
testcase_06 AC 125 ms
82,688 KB
testcase_07 AC 152 ms
83,072 KB
testcase_08 AC 122 ms
82,816 KB
testcase_09 AC 122 ms
82,304 KB
testcase_10 AC 121 ms
83,200 KB
testcase_11 AC 276 ms
97,920 KB
testcase_12 AC 581 ms
128,532 KB
testcase_13 AC 277 ms
97,152 KB
testcase_14 AC 210 ms
93,440 KB
testcase_15 AC 367 ms
103,424 KB
testcase_16 AC 334 ms
100,864 KB
testcase_17 AC 568 ms
123,660 KB
testcase_18 AC 443 ms
111,360 KB
testcase_19 AC 171 ms
89,600 KB
testcase_20 AC 644 ms
141,436 KB
testcase_21 AC 300 ms
99,968 KB
testcase_22 AC 224 ms
94,208 KB
testcase_23 AC 627 ms
135,056 KB
testcase_24 AC 624 ms
133,928 KB
testcase_25 AC 638 ms
134,056 KB
testcase_26 AC 663 ms
140,208 KB
testcase_27 AC 615 ms
137,688 KB
testcase_28 AC 535 ms
130,744 KB
testcase_29 AC 520 ms
130,964 KB
testcase_30 AC 658 ms
139,724 KB
testcase_31 AC 486 ms
125,192 KB
testcase_32 AC 640 ms
137,568 KB
testcase_33 AC 663 ms
139,980 KB
testcase_34 AC 633 ms
139,112 KB
testcase_35 AC 161 ms
93,952 KB
testcase_36 AC 163 ms
94,208 KB
testcase_37 AC 586 ms
134,628 KB
testcase_38 AC 284 ms
107,380 KB
testcase_39 AC 263 ms
106,496 KB
testcase_40 AC 239 ms
107,728 KB
testcase_41 AC 263 ms
107,344 KB
testcase_42 AC 686 ms
147,168 KB
testcase_43 AC 646 ms
140,520 KB
testcase_44 AC 175 ms
99,968 KB
testcase_45 AC 648 ms
139,036 KB
testcase_46 AC 632 ms
134,684 KB
testcase_47 AC 282 ms
110,788 KB
testcase_48 AC 253 ms
104,540 KB
testcase_49 AC 645 ms
137,872 KB
testcase_50 AC 672 ms
139,476 KB
testcase_51 AC 668 ms
133,148 KB
testcase_52 AC 726 ms
152,732 KB
testcase_53 AC 633 ms
139,408 KB
testcase_54 AC 562 ms
133,344 KB
testcase_55 AC 525 ms
127,352 KB
testcase_56 AC 516 ms
128,340 KB
testcase_57 AC 486 ms
125,224 KB
testcase_58 AC 451 ms
127,964 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

###スニペット始まり###
import sys, re
from copy import copy, deepcopy
from math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations, accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce, lru_cache
from string import ascii_uppercase, ascii_lowercase
from decimal import Decimal, ROUND_HALF_UP #四捨五入用

def input(): return sys.stdin.readline().rstrip('\n')
#easy-testのpypyでは再帰数を下げる。
if __file__=='prog.py':
    sys.setrecursionlimit(10**5)
else:
    sys.setrecursionlimit(10**6)

def lcm(a, b): return a * b // gcd(a, b)

#3つ以上の最大公約数/最小公倍数。Nを要素数、Mを数値の大きさとして、O(NlogM)
def gcd_v2(l: list): return reduce(gcd, l)
def lcm_v2(l: list): return reduce(lcm, l)

#nPk
def nPk(n, k): return factorial(n) // factorial(n - k)

#逆元
def modinv(a, mod=10**9+7): return pow(a, mod-2, mod)
INF = float('inf')
MOD = 10 ** 9 + 7
###スニペット終わり###

N=int(input())
S=list(input())
hatena_idx=[]
for i, s in enumerate(S):
    if s=='?':
        hatena_idx.append(i)

def is_ok(mid):

    #一つ目
    s=S.copy()
    for i, idx in enumerate(hatena_idx):
        if i<mid:
            s[idx]='A'
        else:
            s[idx]='C'
    counter=Counter()
    cnt1=0
    for i in range(N):
        if s[-(i+1)]=='A':
            cnt1+=counter['C']
        counter[s[-(i+1)]]+=1
    #二つ目
    s=S.copy()
    for i, idx in enumerate(hatena_idx):
        if i<mid-1:
            s[idx]='A'
        else:
            s[idx]='C'
    counter=Counter()
    cnt2=0
    for i in range(N):
        if s[-(i+1)]=='A':
            cnt2+=counter['C']
        counter[s[-(i+1)]]+=1
    return cnt2<=cnt1

def meguru_bisect(ng, ok):

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans=meguru_bisect(len(hatena_idx)+1, 0)
s=S.copy()
for i, idx in enumerate(hatena_idx):
    if i<ans:
        s[idx]='A'
    else:
        s[idx]='C'
counter=Counter()
cnt1=0
for i in range(N):
    if s[-(i+1)]=='A':
        cnt1+=counter['C']
    counter[s[-(i+1)]]+=1
print(cnt1)
0