精進メモ 2021/05/17~

圧倒的睡眠不足になりました。毎日10時間は寝たいです。

競プロ典型 90 問

042 - Multiple of 9（★4）

最終的に作成した数が9の倍数になるかどうかは、が9の倍数かどうかで決まります。
が小さいので、桁和がになるような数のパターン
としてDPできます。

043 - Maze Challenge with Lack of Sleep（★4）

一つ前は縦、横どっちから来たか、を添え字に持ってDPです。
01BFSになります。

045 - Simple Grouping（★6）

ある集合に対して部分集合を列挙するのを高速にすると、任意の集合に対して部分集合を走査するのがで収まるテクを使います。
グループ数と、既に決めた点の集合を持ったDPです。

046 - I Love 46（★3）

modでまとめて、個数の配列に直すテクを使います。
あとは雑に3重ループでも大丈夫です。

047 - Monochromatic Diagonal（★7）

対角線は、縦のprefixと横のsuffix、もしくはその逆で長さが同じものを列挙するのと同じです。
縦のprefixに対して、それを用いた対角線が最終的にある色になると決め打つと、横のsuffixが満たすべき文字列は一意に定まります。
満たすべき文字列は、一番長い対角線上に対するものさえ求めておけば、あとは連続部分文字列になります。
連続部分文字列と、横のpre(suf)fixの一致はローリングハッシュを使えばOKです。これを全ての色に対してチェックします。

ABC202

D - aab aba baa

パスカルの三角形を利用して、を求めておけば、前から決まっていきます。
a , b がそれぞれ個のとき、を満たしていれば、 a を選べばよいです。、もしくは上の条件を満たさない時は b を選びます。

E - Count Descendants

すごい好きです。
オイラーツアーをします。というクエリがあった際、オイラーツアー中にに入ったタイミングで、(それまでに通った、根から距離の頂点の個数)を引きます。
から出るタイミングで、(それまでに通った、根から距離の頂点の個数)を足します。すると、に対する答えが求まっています。
はパターンしかないですから、クエリを先読みし、1回のDFSで上記の計算を全部やってしまえば間に合います。
オイラーツアーとは言いましたが、オイラーツアーのライブラリは全く必要ない(ただDFSするだけ)ので、実装も軽いです。他のいろいろなライブラリを使う必要もありませんでした。

ARC120

A,C,Dの速度は良かったのですが、Bで詰まりすぎました。

A - Max Add

まず、の最大値が回足されます。
あとは、がに対して足されます。
あとは、足される数の総和を、前から累積和を取りつつ計算していけば良いです。

B - Uniformly Distributed

まわりが全員通していたのですごい焦りました。
左下から右上に線を引いていくと、その斜線上で色が統一されていなければなりません。
あとは、そこで違う色が含まれていたら0、そうでなければ、全て色が決まっていない個数に対してが答えです。

RやBと.が混在していても2倍をしていて、ペナを出しました。

C - Swaps 2

と置き換えます。も同様です。
こうすると、与えられた操作は隣接2点のswapです。
数列の要素が異なる場合-1です。 それ以外の場合、転倒数を求める問題に帰着できます。

D - Bracket Score 2

上から番目に大きい値までに +、そうでない方に -を割り振るよう、括弧列を作れば理論値になります。
先頭は ( にしなければならないため、 (とします。その際、+ と- どちらだったかをメモします。
それ以降、閉じカッコが対応していない開き括弧が存在する限り、メモした符号と同じであれば (を追加し、そうでなければ)を追加して開き括弧を一つ消します。
対応していない開き括弧がなくなったら、最初の操作に戻ります。
これを繰り返すだけで理論値に対応する括弧列が作成できます。
一か所だけ配列サイズを間違えてにしてしまい、1ペナしました。