ABCEの四完。Dは、問題の意味がぱっと理解できなかったから飛ばしたけど、分かっても難しかった。
No.3143 Colorless Green Parentheses Sleep Furiously
WAが出た後、テストケースを見てAC。
カッコ列が正しくなければダメ、というのはOK。その上で、
できるだけ少ない個数の1を加えたとき、何個加えることになるかを知りたい。
()なら、(1+1)+1にしなくてはいけないが、
()()なら(1+1)+(1+1)で良い。
(())なら、((1+1)+1)+1にしなくてはいけないが、
(()())なら、((1+1)+(1+1))にする。
カッコ列の対応を考えて、その対象範囲に自分のカッコだけしかないときは、()+1としなければならない、というのがなかなか気付きにくいポイント。
実装では、最初に、どの"("がどの")"と対応しているかindexの対応を調べておき、((...))となっているようなら、後ろか前かに+1を置けば良い。
No.3145 Astral Parentheses Sequence
解説AC。難しい。
括弧列の個数（カタラン数）をDPで求める方法を応用するとこの問題のDPも導ける。ただ、括弧列の個数を求めるDPがそれほど明らかではないため、それと似た方法でこれもいけるというのは直感的に分かりづらい。
No.3146 RE: Parentheses Counting
解説AC。難しい。
解説の最初にある漸化式（三乗の計算量になるやつ）を自力で出そうとしていたが、それすらできなかった。
ネストの深さが0の部分がカタラン数の積になるっていうところが思いつかない。ここは主客転倒で考えているのか。
その後の、計算量削減の式変形も難しい。カタラン数が満たす漸化式を知っていればいけるかもしれないが。
自力で解くには、実験→oeisしかなかった気がする。
No.3147 Parentheses Modification and Rotation (RM Ver.)
解説AC。
解説を見てしまったけど、これは自力で解けて良かった。括弧列の累積和（いつものやつ）を使い、最大値・最小値から答えが導ける。
タイプ1が右回転なのがちょっと引っ掛けな気がした。S[1:]+S[0]だった方が直感的に分かりやすい。
0 件のコメント:
コメントを投稿