ABC186 kansou - knzkkkkkkkkkk

f:id:knzk398:20201219232817p:plain

うーん、ゴミ！wwwwww

かなしい

A.Brick

はい

https://atcoder.jp/contests/abc186/submissions/18893700

B.Blocks on Grid

最小値を求めて全体から引くのを愚直にやった

和と最小値だけもってれば答えは求められるので

$\sum_{i=1}^{H}\sum_{j=1}^{W}A_{i,j}-(A_{min})*H*W$

グリッドを陽に持つ必要はなかった

https://atcoder.jp/contests/abc186/submissions/18893793

C.Unlucky 7

愚直にやればいい

8進数へ変換するときに

x%8==0 hoge

x /= 8

とするべきところを

x%8==0 hoge

x -= x%8

としてしまいバグらせた　情報系学生失格か？

https://atcoder.jp/contests/abc186/submissions/18893891

D.Sum of diference

$\begin{eqnarray}\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i - A_j |\end{eqnarray}$

を求める。

$N\leq 2e5,|A_i|\leq 1e8$ なので $O(N^2)$ は厳しい。

こういうのは式変形して $A_i$ を定数として前に出して累積和でホイしか考えられないので、

$A_i \geq A_j$ のとき $|A_i - A_j| = A_i-A_j$ なのでAを大きい順のソートする。

勝手にソートして答えが壊れないかというのは、どうせnC2個の組み合わせの和を求めるのはかわらないのでAを並び替えてもよいのがわかる。

$\begin{eqnarray}\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} A_i - A_j &=& \sum_{i=1}^{N-1}(\sum_{j=i+1}^{N}A_i-\sum_{j=i+1}^{N}A_J)\\ &=& \sum_{i=1}^{N-1}(A_i*(N-(i+1))-\sum_{j=i+1}^{N}A_j)\end{eqnarray}$

となり、 $\sum_{j=i+1}^{N}A_j$ は累積和で $O(1)$ で求められるので

それぞれのiについて求めて足せば解ける。

https://atcoder.jp/contests/abc186/submissions/18893989

E.Throne

むっっっっっっっっっっっっっっっっず

非本質的なことを100年考えていたら

$kx+s \equiv 0 (mod. n)$ となる最小のxを求めればいいことがわかる。

"合同式　解き方"などでググって何の益にもならない記事を眺める。

カスカスカスカスカスカスカス簡単にプログラムに落とせるやり方を書けやと思いながら眺めていると"逆元をかける"みたいな記事をみつける。

そのとおりすぎてそのとおりになった。

$x\equiv - \frac{s}{k} (mod.n)$ で、s/kが整数じゃないともとめれんなあといっていた自分を殴りたい　mod nでkで割るというのはkの逆元をかけるという操作と同じ(nとkが互いに素)なので、やる

ここでkの逆元を $k^{n-2}$ で求めるとダメで拡張ユークリッドの互除法でもとめないといけない。

拡張ユークリッドの互除法はかいたことあるけどどっかいってしまったのでググってコピペして

$((-s*k^{-1})%n+n)%n$ が答え

https://atcoder.jp/contests/abc186/submissions/18894138

F.Rook on Grid

縦は普通に数えて横は重なってるとこだけ数えれば解けそうで重なってる数はセグ木でできそうとおもったが時間も足りず、書いてもWAだった

レート減少streakを順調にのばしていて、つらい