結果
問題 | No.3061 Cut and Maximums |
ユーザー |
![]() |
提出日時 | 2024-10-12 19:00:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,101 ms / 2,000 ms |
コード長 | 2,753 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 396,760 KB |
最終ジャッジ日時 | 2024-10-12 19:33:58 |
合計ジャッジ時間 | 19,635 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
""" https://yukicoder.me/problems/11171 黒がない場合は自明に0回で可能。取り除く 不可能な場合を考える 1. Nが白の場合は不可能 2. それ以外は全部可能。黒にした値以外をNと接続して、孤立させればいいので。 効率よく行うことを考える。 N-1を考える。黒の場合は、Nと常に分離しておいてOK 白の場合は、Nと常に接続しておく必要がある solve関数を考える。 solve(L,R) = 区間内が全部白で、区間の端の一つ外の値が区間無いのどの値よりも大きいとき、最小回数 区間内の最大値の位置をMとすると M が 黒の場合 solve(L,R) = max( solve(L,M-1) , solve(M+1,R) , 1 ) Mが白の場合 solve(L,R) = solve(L,M-1) + solve(M+1,R) これで行ける? """ import sys sys.setrecursionlimit(300100) #0-indexed , 半開区間[a,b) #calc変更で演算変更 class SegTree: def __init__(self,N,first): self.NO = 2**(N-1).bit_length() self.First = first self.data = [first] * (2*self.NO) def calc(self,l,r): return max(l,r) def update(self,ind,x): ind += self.NO - 1 self.data[ind] = x while ind >= 0: ind = (ind - 1)//2 self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2]) def query(self,l,r): L = l + self.NO R = r + self.NO s = self.First while L < R: if R & 1: R -= 1 s = self.calc(s , self.data[R-1]) if L & 1: s = self.calc(s , self.data[L-1]) L += 1 L >>= 1 R >>= 1 return s def get(self , ind): ind += self.NO - 1 return self.data[ind] import sys from sys import stdin from collections import deque N = int(stdin.readline()) P = list(map(int,stdin.readline().split())) P = deque(P) while P[-1] != N: P.append(P.popleft()) P = list(P) S = list(stdin.readline()[:-1]) revP = [None] * N for i in range(N): P[i] -= 1 revP[P[i]] = i seg = SegTree(N,0) for i in range(N): seg.update(i,P[i]) if "B" not in S: print (0) sys.exit() elif ("B" in S) and S[-1] == "W": print (-1) sys.exit() def solve(L,R): if L > R: return 0 elif L == R: if S[P[L]] == "B": ans = 1 else: ans = 0 else: # 区間の最大値を求める maxp = None maxp = seg.query(L,R+1) M = revP[maxp] if S[maxp] == "B": ans = max( solve(L, M-1) , solve(M+1,R) , 1 ) else: ans = solve(L, M-1) + solve(M+1,R) return ans print ( max( 1,solve( 0, N-2 )) )