結果

問題 No.2276 I Want AC
ユーザー とりゐとりゐ
提出日時 2023-04-21 23:02:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,063 ms / 2,000 ms
コード長 737 bytes
コンパイル時間 281 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 258,460 KB
最終ジャッジ日時 2024-11-06 16:29:28
合計ジャッジ時間 29,406 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

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=[]
  if mid==-1:
    x=-1
  elif mid==m:
    x=n
  else:
    x=B[mid]
  for i in range(n):
    if s[i]=='A' or (s[i]=='?' and i<=x):
      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):
    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