結果

問題 No.2276 I Want AC
ユーザー kuro_Bkuro_B
提出日時 2023-05-10 16:35:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 698 ms / 2,000 ms
コード長 2,421 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 153,364 KB
最終ジャッジ日時 2024-05-05 04:07:52
合計ジャッジ時間 25,937 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
83,328 KB
testcase_01 AC 127 ms
83,072 KB
testcase_02 AC 121 ms
82,944 KB
testcase_03 AC 123 ms
83,200 KB
testcase_04 AC 121 ms
83,072 KB
testcase_05 AC 121 ms
83,200 KB
testcase_06 AC 121 ms
82,944 KB
testcase_07 AC 125 ms
83,200 KB
testcase_08 AC 126 ms
82,944 KB
testcase_09 AC 119 ms
83,200 KB
testcase_10 AC 119 ms
83,072 KB
testcase_11 AC 272 ms
98,176 KB
testcase_12 AC 574 ms
128,912 KB
testcase_13 AC 261 ms
97,536 KB
testcase_14 AC 198 ms
93,696 KB
testcase_15 AC 362 ms
104,064 KB
testcase_16 AC 328 ms
100,864 KB
testcase_17 AC 542 ms
124,696 KB
testcase_18 AC 433 ms
111,744 KB
testcase_19 AC 160 ms
89,984 KB
testcase_20 AC 624 ms
141,556 KB
testcase_21 AC 287 ms
100,224 KB
testcase_22 AC 216 ms
94,464 KB
testcase_23 AC 610 ms
135,700 KB
testcase_24 AC 611 ms
134,052 KB
testcase_25 AC 615 ms
134,308 KB
testcase_26 AC 626 ms
140,332 KB
testcase_27 AC 599 ms
137,828 KB
testcase_28 AC 535 ms
131,124 KB
testcase_29 AC 513 ms
131,220 KB
testcase_30 AC 645 ms
140,232 KB
testcase_31 AC 476 ms
125,568 KB
testcase_32 AC 637 ms
137,692 KB
testcase_33 AC 645 ms
140,100 KB
testcase_34 AC 610 ms
139,236 KB
testcase_35 AC 153 ms
94,080 KB
testcase_36 AC 152 ms
94,336 KB
testcase_37 AC 564 ms
134,896 KB
testcase_38 AC 292 ms
108,144 KB
testcase_39 AC 252 ms
106,552 KB
testcase_40 AC 234 ms
107,852 KB
testcase_41 AC 253 ms
108,116 KB
testcase_42 AC 634 ms
147,040 KB
testcase_43 AC 631 ms
141,156 KB
testcase_44 AC 179 ms
99,840 KB
testcase_45 AC 660 ms
139,424 KB
testcase_46 AC 624 ms
134,688 KB
testcase_47 AC 275 ms
110,916 KB
testcase_48 AC 254 ms
104,916 KB
testcase_49 AC 632 ms
137,748 KB
testcase_50 AC 648 ms
139,472 KB
testcase_51 AC 638 ms
133,156 KB
testcase_52 AC 698 ms
153,364 KB
testcase_53 AC 619 ms
139,284 KB
testcase_54 AC 538 ms
133,464 KB
testcase_55 AC 495 ms
127,616 KB
testcase_56 AC 504 ms
128,848 KB
testcase_57 AC 467 ms
125,348 KB
testcase_58 AC 437 ms
128,480 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