結果

問題 No.2276 I Want AC
ユーザー とりゐ
提出日時 2023-04-21 22:57:49
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 677 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 258,628 KB
最終ジャッジ日時 2024-11-06 16:25:20
合計ジャッジ時間 30,136 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46 WA * 3 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count(t):
  A=0
  res=0
  for i in t:
    if i=='A':
      A+=1
    else:
      res+=A
  return res


def calc(mid):
  t=[]
  for i in range(n):
    if s[i]=='A' or (s[i]=='?' and i<=B[mid]):
      t.append('A')
    else:
      t.append('C')
  return count(t)
 

def ternary_search(L,R):
  # 準下凸関数の最小値
  while L+2<R:
    c1=L+(R-L)//3
    c2=R-(R-L)//3
    if calc(c1)>calc(c2):
      R=c2
    else:
      L=c1
  
  ans=0
  for i in range(L,R+1):
    ans=max(ans,calc(i))
  
  return ans

n=int(input())
s=list(input())
B=[]
for i in range(n):
  if s[i]=='?':
    B.append(i)

if len(B)==0:
  print(count(s))
  exit()

m=len(B)
print(ternary_search(-1,m))
0