結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,444 KB
testcase_01 AC 39 ms
53,372 KB
testcase_02 AC 39 ms
53,004 KB
testcase_03 AC 39 ms
52,704 KB
testcase_04 AC 41 ms
53,476 KB
testcase_05 AC 39 ms
52,480 KB
testcase_06 WA -
testcase_07 AC 40 ms
53,200 KB
testcase_08 AC 40 ms
52,872 KB
testcase_09 AC 39 ms
52,832 KB
testcase_10 AC 40 ms
53,004 KB
testcase_11 AC 270 ms
130,584 KB
testcase_12 AC 774 ms
208,644 KB
testcase_13 AC 256 ms
124,580 KB
testcase_14 AC 147 ms
92,928 KB
testcase_15 AC 449 ms
173,964 KB
testcase_16 AC 375 ms
145,908 KB
testcase_17 AC 691 ms
198,676 KB
testcase_18 AC 513 ms
181,820 KB
testcase_19 AC 70 ms
75,784 KB
testcase_20 AC 850 ms
215,576 KB
testcase_21 AC 321 ms
140,212 KB
testcase_22 AC 164 ms
103,876 KB
testcase_23 AC 879 ms
217,020 KB
testcase_24 AC 819 ms
215,220 KB
testcase_25 AC 879 ms
215,376 KB
testcase_26 AC 866 ms
203,888 KB
testcase_27 AC 796 ms
241,292 KB
testcase_28 AC 717 ms
191,012 KB
testcase_29 AC 636 ms
258,608 KB
testcase_30 AC 1,093 ms
240,452 KB
testcase_31 AC 546 ms
258,528 KB
testcase_32 AC 836 ms
201,488 KB
testcase_33 AC 1,104 ms
240,596 KB
testcase_34 AC 744 ms
216,228 KB
testcase_35 AC 51 ms
69,468 KB
testcase_36 AC 51 ms
70,128 KB
testcase_37 AC 695 ms
163,412 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 263 ms
180,316 KB
testcase_41 AC 303 ms
207,548 KB
testcase_42 AC 723 ms
218,376 KB
testcase_43 AC 697 ms
222,608 KB
testcase_44 AC 55 ms
71,884 KB
testcase_45 AC 864 ms
202,000 KB
testcase_46 AC 877 ms
241,484 KB
testcase_47 AC 301 ms
193,552 KB
testcase_48 AC 305 ms
193,924 KB
testcase_49 AC 830 ms
200,920 KB
testcase_50 AC 904 ms
243,072 KB
testcase_51 AC 799 ms
241,668 KB
testcase_52 AC 822 ms
241,260 KB
testcase_53 AC 913 ms
203,812 KB
testcase_54 AC 622 ms
202,540 KB
testcase_55 AC 590 ms
202,676 KB
testcase_56 AC 602 ms
201,188 KB
testcase_57 WA -
testcase_58 AC 754 ms
187,028 KB
権限があれば一括ダウンロードができます

ソースコード

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