結果
問題 | No.2276 I Want AC |
ユーザー | FromBooska |
提出日時 | 2023-04-22 07:01:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 1,914 bytes |
コンパイル時間 | 828 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 75,904 KB |
最終ジャッジ日時 | 2024-04-24 13:42:27 |
合計ジャッジ時間 | 11,319 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
51,968 KB |
testcase_01 | AC | 37 ms
51,840 KB |
testcase_02 | AC | 37 ms
51,712 KB |
testcase_03 | AC | 36 ms
52,224 KB |
testcase_04 | AC | 41 ms
52,224 KB |
testcase_05 | AC | 39 ms
51,712 KB |
testcase_06 | AC | 40 ms
51,712 KB |
testcase_07 | AC | 39 ms
52,096 KB |
testcase_08 | AC | 34 ms
52,096 KB |
testcase_09 | AC | 36 ms
51,584 KB |
testcase_10 | AC | 35 ms
51,712 KB |
testcase_11 | AC | 118 ms
75,392 KB |
testcase_12 | AC | 231 ms
75,776 KB |
testcase_13 | AC | 111 ms
74,880 KB |
testcase_14 | AC | 89 ms
75,008 KB |
testcase_15 | AC | 142 ms
75,264 KB |
testcase_16 | AC | 135 ms
75,008 KB |
testcase_17 | AC | 214 ms
75,520 KB |
testcase_18 | AC | 178 ms
75,392 KB |
testcase_19 | AC | 64 ms
68,736 KB |
testcase_20 | AC | 250 ms
75,392 KB |
testcase_21 | AC | 119 ms
75,008 KB |
testcase_22 | AC | 82 ms
74,752 KB |
testcase_23 | AC | 245 ms
75,648 KB |
testcase_24 | AC | 247 ms
75,648 KB |
testcase_25 | AC | 258 ms
75,648 KB |
testcase_26 | AC | 249 ms
75,392 KB |
testcase_27 | AC | 247 ms
75,648 KB |
testcase_28 | AC | 207 ms
75,264 KB |
testcase_29 | AC | 165 ms
75,648 KB |
testcase_30 | AC | 234 ms
75,264 KB |
testcase_31 | AC | 147 ms
75,648 KB |
testcase_32 | AC | 249 ms
75,392 KB |
testcase_33 | AC | 221 ms
75,776 KB |
testcase_34 | AC | 257 ms
75,776 KB |
testcase_35 | AC | 42 ms
58,624 KB |
testcase_36 | AC | 41 ms
59,136 KB |
testcase_37 | AC | 207 ms
75,136 KB |
testcase_38 | AC | 54 ms
59,776 KB |
testcase_39 | AC | 52 ms
59,392 KB |
testcase_40 | AC | 61 ms
59,392 KB |
testcase_41 | AC | 62 ms
60,288 KB |
testcase_42 | AC | 213 ms
75,392 KB |
testcase_43 | AC | 215 ms
75,264 KB |
testcase_44 | AC | 46 ms
59,776 KB |
testcase_45 | AC | 252 ms
75,520 KB |
testcase_46 | AC | 252 ms
75,648 KB |
testcase_47 | AC | 84 ms
75,648 KB |
testcase_48 | AC | 89 ms
75,136 KB |
testcase_49 | AC | 250 ms
75,392 KB |
testcase_50 | AC | 251 ms
75,520 KB |
testcase_51 | AC | 251 ms
75,776 KB |
testcase_52 | AC | 244 ms
75,264 KB |
testcase_53 | AC | 271 ms
75,264 KB |
testcase_54 | AC | 185 ms
75,904 KB |
testcase_55 | AC | 175 ms
75,520 KB |
testcase_56 | AC | 143 ms
75,264 KB |
testcase_57 | AC | 105 ms
75,264 KB |
testcase_58 | AC | 197 ms
75,264 KB |
ソースコード
# ?の数を数えて、前半何個までをAとするかで全探索したらTLE # 半分前後だけを調べてもWA # 三分探索してみる、ただし最低値を求めるやり方なのでマイナスにして最低値を求める N = int(input()) S = input() q_count = S.count('?') if q_count == 0: ans = 0 A_count = 0 for i in range(N): if S[i] == 'A': A_count += 1 elif S[i] == 'C': ans += A_count print(ans) exit() def calc_point(q): # 三分探索が最低値を探すようにできているのでcalcはマイナスになるようにした calc = 0 A_count = 0 used = 0 for i in range(N): if S[i] == 'A': A_count += 1 elif S[i] == 'C': calc += A_count elif S[i] == '?': if used < q: # treat as A used += 1 A_count += 1 else: # treat as C calc += A_count return -calc # 谷、つまり1極値を求める三分探索での解き方 # https://roiti46.hatenablog.com/entry/2015/04/29/yukicoder_No.198_%E3%82%AD%E3%83%A3%E3%83%B3%E3%83%87%E3%82%A3%E3%83%BC%E3%83%BB%E3%83%9C%E3%83%83%E3%82%AF%E3%82%B9%EF%BC%92 # https://qiita.com/ganyariya/items/1553ff2bf8d6d7789127 # 範囲に注意、ギリギリありえない値とする left, right = -1, q_count+1 while right-left > 2: left_mid, right_mid = (2*left+right)//3, (left+2*right)//3 if calc_point(left_mid) <= calc_point(right_mid): # 右midの方が大きいから右を右midに変える right = right_mid else: left = left_mid #print(left_mid, right_mid) ans = min(calc_point(left_mid), calc_point(right_mid)) # leftとrightの間も入れる必要あるのか? print(-ans) # マイナスにして最低値を探したが、答えはプラスの最大値だから