精進メモ 2021/07/19~ - ツバサの備忘録

そろそろ大学のチーム練が始まりそうで楽しみです(出られるかは置いといてですが…)

ABC211
ARC124

ABC211

順位は良かったのですが、Fで思いのほかてこずってしまったので少し悔しいです。

D - Number of Shortest paths

これのBFS版ですね。つまりこれと全く同じです。

最短経路を計算しながら数え上げもしていきます。

E - Red Polyomino

サンプルが答えです。
個数が多くないので、dfsで探索していけば終わります。bitで持つのが楽でした。

F - Rectilinear Polygons

考察自体はシンプルな気がしました。実装を頑張る問題。
平面捜査をしていけばよいです。
x軸の向きで見ていくとき、ある多角形について、縦の直線が、その範囲の座標で奇数回目に登場していれば直線の座標すべてに+1を、偶数回目であれば-1をします。
少し近い？考え方として、これがあります。
点のクエリに対する答えは、+されている現在の回数を見ればよいです。
いもすでやっていましたが、バグったので遅延セグ木に変えました。それでも結局かなりバグらせて、時間を食ってしまいました…

ARC124

苦しい結果です。

A - LR Constraints

可能なカードの枚数をそれぞれメモすれば良いです。二乗が間に合うので愚直でOKでした。
文字のLRの判定を間違えて数字の入力で判断していたため、実装に時間がかかりました。

B - XOR Matching 2

$A_{0}$ を固定して、それに合わせる $B_{i}$ を愚直に試せばOKです。
必要な数の個数と、 $B_{i}$ のカウントがあっていればOKです。

C - LCM of GCDs

まず、全体を全ての要素の $\gcd$ で割って問題ありません。これは最後にかければ答えになります。
すると、2択を選んでいき、それぞれの集合の $\gcd$ の掛け算が最大になっていればＯＫです。
あとは、愚直に2択を選んでいけばいいです。 $\gcd$ のペアの個数は少ないです。

D - Yet Another Sorting Problem

初手で実験を選んだのは大正解でした。デバッグでも大活躍しました。
割とはやめに考察は終わっていたのに、コーナーケースの処理がきちんとできていなくて40分ほど時間を溶かしました…パフォが200ほど落ちているので厳しいです。
実験をすると、 $i = p_{i}$ という操作を繰り返して行くループそれぞれ独立にまず数えればOKということがわかります。
どちらかの値一方しか入っていない場合、両方を行き来する場合があります。
前者は、(長さ + 1)を足します。これは、1度反対側の適当な箇所とスワップをして、列の値を揃えていき、最後に元に戻すという操作です。
後者は、(長さ - 1)を足します。これは素直に、1つずつ戻せる箇所を戻していけば良いです。
コーナーケースは、左側のみのケースおよび右側のみのケースが複数個存在していた場合、 $2 \times \min(左の個数, 右の個数)$ を答えから引くことです。これは、左と右のみのループの列について、その中から1つずつ最初に選ぶことで、最初の適当な箇所をスワップする、という操作の無駄がなくなり、(長さ-1)のケースに帰着させることができるからです。
以上をまとめて数えれば、答えとなります。