精進メモ 2021/08/02~ - ツバサの備忘録

ABC212 G - Power Pair
ABC212 H - Nim Counting
The 15th Chinese Northeast Collegiate Programming Contest
ABC213

ABC212 G - Power Pair

提出
途中まで解説を読んだので、ほぼ解説通りです。
位数の総和を求める問題ですが、原子根を持ってきて肩の数字の比較で条件をつくります。
$an \equiv b \mod{p-1}$ を満たす $(a,b)$ を数える問題になります。
ある $a$ に対して、 $b$ が $x$ 個となるのは、 $p-1$ との $\gcd$ が $(p-1)/x$ となるときです。
位数は、 $p-1$ の約数個しか種類として登場しません。
逆に、 $(p-1)/x \times k$ となるような、 $x$ と互いに素な $k$ は、これを満たします。
よって、あとは $x \times (kの個数)$ を数えればよく、これはオイラーのΦ関数で求めることができます。
原子根、Φ関数あたりは知っていますが、活かしきることがいつもできないですね。

ABC212 H - Nim Counting

提出
 アダマール変換とダブリングです。
アダマール変換さえ書ければあとは…というところでした。未履修だったのでコンテスト中は解けずじまいです。

The 15th Chinese Northeast Collegiate Programming Contest

チーム練です。suzuken君と二人でした。
自分はA,E,C,D,Hを担当しました。suzuken君がI,K,M,Jです。
~~嫌な問題を全て押し付けました~~

A. Matrix

$N^{2}! \times N - N \times _{N^{2} - N}P_N \times (N^{2}-N)!$
が答えです。前計算の配列サイズを間違えてREしました。

E. Easy Math Problem

$6p$ として、 $p,2p,3p$ を部分集合として選べばOKです。

C. Vertex Deletion

頑張って木DPをします。今見ている頂点が、ひとりぼっちになっているか、子のいずれかと連結か、見ている頂点自身を消すかの3通りで場合分けです。

D. Lowbit

解法は好きです。
立っているビットが1つずつ減っていき、1になると、それ以降は常に2倍になります。
立っているビットは数十個以内なので、その部分だけは愚直に計算してあげて、ビットが1つになったら、区間更新でまとめてあげます。

H. Loneliness

初手で一周を考えたのが正解でした。
時計回り、反時計回りで+1および-1が作れるので、下にいった場合の2倍と組み合わせて、目標の数字に作り上げていくいつもの構築をすればよいです(奇数は作れません)。
右端の方に寄せてあげるパートでとてつもない回数を食ってしまうのですが、この部分はsuzuken君が回数を減らす方法を考えてくれました。
少し下に移動してから上に戻ると、回数がかなり抑えられます。
2が作れないと思い込んでいましたが、上記の方法を使えば2も作れました。

ABC213

頭が疲れていて全然まわらなかったです。F通せないのは悔しいですね。

C - Reorder Cards

座圧だけであれば特に苦手としていなかったのですが、まわりがはやすぎてびっくりしました。

D - Takahashi Tour

DFSをすればOKです。

E - Stronger Takahashi

01BFSです。上下左右はコスト0で、パンチを1回使った際に移動できる範囲はコスト1で移動します。綺麗な書き方が思いつかなかったので適当にコピペしたら、バグりました。

F - Common Prefixes

Suffix Arrayを使って、LCP配列を求めた後、累積minの総和を求めるのはすぐにわかりましたが、それぞれの計算を行う部分をまとめてやる方法が思いつきませんでした。
stackを使って処理を行う感じでやればいけるかなぁと思いついたのが残り3分だったので間に合いませんでした。
体力が残ってないので後日に…