結果

問題 No.2276 I Want AC
コンテスト
ユーザー とりゐ
提出日時 2023-04-21 22:59:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 691 bytes
コンパイル時間 306 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 258,632 KB
最終ジャッジ日時 2024-11-06 16:27:49
合計ジャッジ時間 30,521 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 52 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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(max(L,0),min(R+1,m)):
    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