Arrays別解が面白かった。特殊なstackがあり、以下の一点だけ通常のstackと異なる。topと現在挿入し要素している数字が同じとき、その2つの数字は削除される長さ$n$の自然数列$a$が与えられるので、このstackに順に入れると空になるような連続部分列の個数を求めよ。n$)解法1Editorialの方針。言葉で説明するよりも図のほうがわかりやすい気がしたので図を載せておきます。空になる区間ごとにまとめて考えれば良くて、左から愚直にたどっていくと最悪ケースで$\mathcal{O}(n^2)$かかりますが、以下のようにhashmapとcountの累積を考えると$\mathcal{O}(n)$になります。a[r]\}が空になるようなrの個数$$実装いくつかに枝分かれしているような遷移について、mapのその時点の先頭までの累積を計算したいだけだったらmoveを使うと効率的にできる。Rangesと同じ言い換えをします。いう言い換えができます(便宜的に先頭に空文字列の要素を追加したものを考えています)。簡単な証明は末尾に記載していますが、直感的に成り立ちそうなのはわかると思います。Hashでhash化して個数をカウントしていけば良いことがわかります。e$とします($e$は単位元とする)。成り立つ条件を考えます。$\Rightarrow$は明らかに成り立ち、$\Leftarrow$が成り立つ条件はモノイドが(左)簡約可能($ab=ac$ならば$b=c$)なことです。成り立つことがわかりました。Rangesでも成り立つことがわかると思います。与えられた文字列に対して、連続する同じ文字2つを選んで消去することを繰り返すという操作はどこからやっても同じ結果になることが帰納法などによって証明できることから、2つの文字列をconcatしたあとにその操作を行うことを考えてもモノイドになっていることがわかります。簡約律は明らかに成立することから、今回の問題設定でも成立することがわかりました。