SRM628Div1Medium
問題
サイズNの文字列とサイズMの数列が与えられる。文字列は'A','B','X'の3文字で構成され、'A'と'B'には以下の操作する。
'X'には数列の要素が入る。
'X'に適切に数字を割り当てることで返される最大の数字を求めよ。
解法
与えられる文字列からASTを構成する。正しくASTが構築できることは保証されている。可能な演算は最大値を取るか加算をするかのどちらかなので、加算の回数を最大にすることで答えが求まる。回数に注目するので'X'を1として、計算を行い回数を求める。数列を降順にソートして、求めた回数分の加算を行うことで答えが求まる。
計算量
探索:O(N)
ソート:O(M log M)
