ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

精進メモ 2021/04/12~

精進記

先週もモンハンしていたら一週間が終わりました。
MY FIRST STORYをにハマりました、気に入った数曲をヘビロテしていますが良いですね。

形式的べき級数

勉強を始めました。

読み終わったもの:

今年中に理解する！多項式、母関数、形式的べき級数の競プロでの実践的使い方 - はまやんはまやんはまやん

[多項式・形式的べき級数]（１）数え上げとの対応付け | maspyのHP

[多項式・形式的べき級数]（２）式変形による解法の導出 | maspyのHP

[多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 | maspyのHP

どれもわかりやすいです。

ACL contest 1 E - Shuffle Window

問題
提出コード
当時はさっぱりわかりませんでしたが今は少し考えたらあっさり解けました。成長です。
まず、K = Nを考えます。
p_{i}とp_{j}について考えると、iが前に来る確率がちょうど1/2になります。よって、\frac{N(N-1)}{2} \times \frac{1}{2} が答えです。
そうでない場合について考えます。
i,j番目の要素がどちらも、ランダムに選ばれる要素の候補に含まれるようになったら、それ以降、i,jによる転倒数の増加確率は1/2になります。
なので、i \lt jとすると、jが候補に入る前に、iの場所が確定しない確率pを求めれば、

  • 先に確定しなかった: p \times \frac{1}{2}の確率で転倒数が1増加

  • 先に確定した: 確率1-pで転倒数の増加は一意に決まる( p_{i} > p_{j}であれば増加)

となるので答えがわかります。
jが候補に含まれるまでに、iがランダムに選ばれる試行をする回数は、j - i - k + 1回となります。
1回あたりの試行で、選ばれない確率は\frac{k-1}{k}なので、
p = \left(\frac{k-1}{k}\right)^{j-i-k+1}
となります。
全ての(i,j)に対して計算を行うことはできませんが、\frac{k-1}{k}のべき乗を考えているので、区間更新が掛け算、区間取得が総和の遅延セグ木を用いることで、jに対するpの総和を高速に求められます。

第二回日本最強プログラマー学生選手権

C - Max GCD 2

実はちょっとハマっていました。
GCD(x,y) = iが存在するには、iの倍数がA以上Bの中に2つある必要があります。A以上のiの倍数はO(1)で求まるので、iについて全探索できます。

D - Nowhere P

累積和 mod Pを考えると、この値がどうなっていても、次に選ぶことができる値はP - 2パターンです。なので、P-2のべき乗を考えれば良いです。初項のみP-1パターンです。

E - Level K Palindrome

再帰的に考えていくと、レベルiの回文について、5つめの条件を適用したか、4つめの条件を適用したかは|S|で一意に決まっています。
Kは多くても20程度であり、それより大きい場合はそもそも答えが impossible になります。
あとは、レベル0の文字列が2^{K}通りほど出てきて、それらが全て一致するかつ回文でないようになる必要があります。この部分は、1か所でも反転したときに文字が一致しない箇所があればいいので、それを適当に決め打ちすると、他はだいたい貪欲に決めてOKです。
奇数長の場合、真ん中は決め打ちで使えないので注意です。

F - Max Matrix

変更箇所に対する値の差分を計算しようとすると、
数列のxより小さい値の個数および、x以上の値の総和が求まればいいことがわかります。
どちらも、セグ木に乗ります。要素の値は10^{8}まであるので、座標圧縮が必要になりますが、ここを頑張って実装すれば通ります。

G - Spanning Tree

行列木定理らしいです。
辺を張らなければならない部分を先に張り、連結成分ごとに頂点を圧縮すると、上の定理そのもので問題の答えを計算できます。

AtCoder Regular Contest 117

久々の橙です。highest復帰までもう少しです。

A - God Sequence

正の序盤は1,2...として、最後の項を10^{8}にしておくと、負の序盤は-1,-2...として、こちらの最後の項で適宜調整できます。順位表が開始直後ペナまみれだったので丁寧にやりましたが、少し丁寧すぎた気もします。

B - ARC Wrecker

並び替えを好きにしても答えは変わらないので、昇順に並べます。
ある初期の高さi,jについて、階のある/なしの分布が一致していると、それらはどちらを選んでも全く同じ結果になります。
一方、分布が一致してない場合、iとjどちらを選ぶかで結果が変わります。 ので、それぞれの分布について、何回選ぶかで答えが変わります。
これは、階差 + 1の積を求めればよいです。

C - Tricolor Pyramid

見た時点で二項係数っぽいなぁという気になります(参考問題1 , 参考問題2)。
RBWに012を割り当て、これらの演算がどのようになっているかを見ると、x,yのブロックの上には、
(x \oplus 3) + (y \oplus 3) \mod 3
であることがわかります( -x + -y \mod 3でもいいです )
初期位置が左からi番目のブロックは、1番上の段には、_{N-1}C_{i-1}回影響するので、
x \times _{N-1}C_{i-1}
を答えに足してあげればよいです。
Nが偶数のときは、x \oplus 3で置き換えてあげましょう。
\mod 3での二項係数は、3だけ別処理をして、今どれだけ3がかかっているか数えてあげればよいです。

D - Miracle Tree

初期値1のカウンターを用意し、ある頂点からDFSをはじめて、他の頂点に移動するたびにカウントを1増やします。そして、DFSをしていて、まだ値が書き込まれていない頂点にたどり着いたとき、カウンターの値を書き込みます。
こうすると、問題の条件を満たす木ができあがります。
N個目の頂点に書き込まれた値が最大値です。
この最大値は、オイラーツアーで辿る距離から、任意の一つのパスの長さを引いたものになります。パスの長さが最大になるには、直径を選べばよいので、(オイラーツアーの長さ)- (直径) + 1が答えになります。
ということで(↑だけだとこれが最適解の証明になっていませんが)、後は直径の端点からDFSを開始して、もう片方の端点が最後にくるようにDFSをすれば答えが求まります。