精進メモ 2021/10/04~ - ツバサの備忘録

書き忘れてました。

MojaCoder Random Xor Division
ABC222

MojaCoder Random Xor Division

リンク
$O(N^{2})$ が想定っぽい？ですが、 $O(N \log A_{i})$ で解けました。
ビットごとに見ます。すると、累積和の偶奇で右端を固定したときの相方の候補が出せます。
数日前のABC-E問題同様、2の冪乗の累積和を計算して、右端より右側で自由に切れる部分、左端より左側で自由に切れる部分のパターン数が計算できます。
あとは、ビットごとに上記を計算していき、総和を取って、全体のパターン数である $2^{N-1}$ で割れば答えです。

ABC222

C - Swiss-System Tournament

毎回愚直に対戦させ、勝利数を計算してからソートしなおしていけばOKです。

D - Between Two Arrays

DPをいもすで高速化します。

E - Red and Blue Tree

辺ごとに通る回数をメモしてから、差が問題の条件を満たすようDPすればOKです。一回も通らないものは素直に2倍していきます。

F - Expensive Expense

全方位木DPです。
$dp[v] = v$ を根とする部分木で、 $v$ からどこかへ観光しに行ったときにかかるコストの最大値、として計算します。

G - 222

離散対数問題のライブラリがバグっていてコンテスト中に通せませんでした。
漸化式の解き方をググって解くと、 $a_{i} = \frac{2}{9}(10^{i} - 1)$ という式が出てきます。
これが $K$ の倍数になれば良いです。
少し変形すると、
$2 \times 10^{i} \equiv 2 \mod{9K}$
となります。
あとはこれを満たす最小の $i$ を求めればOKです。