ABC172 参加メモ - tinumu's reminder

勤勉ではありません(悲痛)
ABCD4完 520th Perf=1795 (1916->1904(-12))
冷えが青程度に収まってるから良いものの、上限を上げる努力をしましょう

A - Calc

気をつけて書く a + a*a + a*a*a

B - Minor Change

こういうのってfor使わない方法とかあったっけ
cnt += S[i] != T[i]

C - Tsundoku

机Aを読む数 $i$ を決めたら机Bをできるだけ読もうとしてできる読む数 $j$ が決まるので尺取りっぽくやって $\mathrm{O}(N+M)$ で処理可能

D - Sum of Divisors

$j$ の倍数についてカウントするだけでも $\mathrm{O}(N \log N)$ で通るけどちょっと怖いっぽい。 $\mathrm{O}(N)$ 解がある。
$j$ の倍数を $i (i \leq N)$ とすると、 $\sum_{j=1}^{N} \sum_{i} i$ で答えが出てくる。
$i$ は $j, 2j, \cdots nj \left(n = \left\lfloor \frac{N}{j} \right\rfloor \right)$ の和になっているので等差級数の和である。つまりこれは $\mathrm{O}(1)$ で計算できて、 $\sum_{i} i = \frac{jn(n+1)}{2}$ となる。
最終的な答えは $\sum_{j=1}^{N} \frac{jn(n+1)}{2}$ となり、 $\mathrm{O}(N)$ である。
通りそうなら通しちゃうのもコンテストの中では大事だとは思うけどこういうのもちゃんとやらないと

E - NEQ

事象 $P_i$ を $A_i = B_i$ であることとする。
すると今回の $A_i \neq B_i$ というのは $\overline{P_1} \cap \overline{P_2} \cap \cdots \cap \overline{P_N}$ ということになる。
これはド・モルガンで $\overline{P_1 \cup P_2 \cup \cdots \cup P_N}$ となっていて、どうやら事象の和事象の形になるようである。

事象 $P_i$ を $A_i = B_i$ の条件にしたのも、こっちのほうが求めやすいわけで、事象の和事象を包除原理を用いて積事象たちを使って解こうという魂胆である。

今回の事象を包除原理で表すと以下の形になる。
$\displaystyle |\overline{P_1 \cup P_2 \cup \cdots \cup P_N}| = |U| - |P_1 \cup P_2 \cup \cdots P_N|$ ( $U$ は全体集合, $|A|$ は事象 $A$ の起こりうる数)
$\displaystyle = |U| - \sum_{i} |P_i| + \sum_{i \lt j} |P_i \cap P_j| - \sum_{i \lt j \lt k} |P_i \cap P_j \cap P_k| + \cdots$

ここで出てくる積事象たちについて、この問題ではどのように表すかを考える。

各要素が $1$ 以上 $N$ 以下の整数である、ある集合 $S$ がある。 (例えば $N=3$ だったら $S = \{1, 3\}$ とか)
このときの $i \in S$ である $i$ について $A_i = B_i$ である。
このようなものの個数は数え上げできて、 $_{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$ 個となる。
これが $1$ 要素である。
足し上げる時には上記の包除原理の式に則ると $S$ の要素数が偶数の時には +, 奇数の時には - になっている必要があるので、この要素の項は $(-1)^{|S|} \ _{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$ ということになる。

これを全ての $S$ について数えると。すると、次のような式になる。
$\displaystyle ans = \sum_{S \in 2^{ \{1, 2, \cdots N \} }} (-1)^{|S|} \ _{M} P _{|S|} \times (_{M-|S|} P _{N-|S|})^2$
しかしこれだと $2^N$ 回計算してしまうのでそのままだと計算できない。
考えてみると、各項で使っているのは $|S|$ だけであるので、要素数が一致していれば全て同じ答えを出すということが分かる。では要素数が $K$ であるような $S$ の数というのは $_{N} C _{K}$ 個だけあるので、各要素数についてまとめて計算できる。
すると、式は、
$\displaystyle ans = \sum_{K=0}^{N} \ (-1)^K \ _{N}C_{K} \times \ _{M} P _{K} \times (_{M-K} P _{N-K})^2$
となって、無事に数え上げることが出来た。

積事象を考えるときには余事象についての部分的な積事象が高速に求まらないかを考えていく必要がありそう

F - Unfair Nim

解説のpdfとほぼ一緒かも…
これは通常のNimなので、この問題で高橋くんが勝つというのは $A_1 \oplus A_2 \oplus \cdots \oplus A_N = 0$ であることを言う。
操作に置いて $A_3$ 以降は値は変わらないので一つにまとめてしまってもよい。 $A_3 \oplus \cdots \oplus A_N = X$ と置いておく。
$A_1 + A_2 = S$ とおくと、 $a+b = S (0 \lt a \leq A_1)$ であるような $a, b$ で、 $a \oplus b \oplus X = 0$ つまり $a \oplus b = X$ であるような最大の $a$ を見つければこの問題が解ける。
まとめると条件は $3$ つになる。

$a+b = S$
$a \oplus b = X$
$0 \lt a \leq A_1$

ここで $a+b = a \oplus b + 2 \times (a \& b)$ であることを利用すると、
$X + 2 \times (a \& b) = S$ より、 $a \& b = (S-X)/2$ となる。
すると、 $S-X$ が奇数の場合や負になっている場合は答えが無しになる。
新たに $(S-X)/2 = D$ と置くとする。

すると、次のような条件になる。

$a \& b = D$
$a \oplus b = X$
$0 \lt a \leq A_1$

これによってビットごとに独立の計算になったことが良い性質である。ここで色々なことが分かる。
$a \oplus b = X$ との兼ね合いを考えると、 $X, D$ の同じビットが同時に $1$ になっていることはありえない。そのため、 $X \& D > 0$ である場合も答えは無しである。

ここで具体的に解いていく。
まず $D$ のbitで $1$ が立っているところは $a, b$ のどちらも $1$ が立っていないといけないので予め立てておく。
そうしたら $X$ の bitで $1$ が立っているところが気になる。このとき、 $a, b$ のどちらかに $1$ を立てるということをする。
このとき、 $a \leq A_1$ ギリギリのところまで bit を立てれば最大化出来そう。
そのため、上のビットから貪欲に $1$ が立てられるまで立てると、 $a$ を最大化させられる。
ここで最大化した結果として $a=0$ になるのならば、-1を出力する。